A Probabilistic Two-Pile Game

Ho-Hon Leung Department of Mathematical Sciences United Arab Emirates University Al Ain, 15551 United Arab Emirates

                hohon.leung@uaeu.ac.ae

Thotsaporn “Aek” Thanatipanonda Science Division Mahidol University International College Nakornpathom Thailand

                 thotsaporn@gmail.com

Abstract

We consider a game with two piles in which two players take turns adding a or b chips, randomly and independently, to their respective piles. Here a, b are not necessarily positive. The player who collects at least n chips first wins the game. We derive general formulas for p_{n}, the probability of the second player winning the game by collecting n chips first, and give the calculation for the cases {a, b} = {−1, 1} and {−1, 2}. The latter case was considered by Wong and Xu. At the end, we derive a general formula for p_{n_{1},n_{2}}, the probability of the second player winning the game by collecting n_{2} chips before the first player collects n_{1} chips.

1 Introduction

Games are a source of motivation to do mathematics. The will to win a game is a motivation to determine the mathematics behind it. There is evidence that pile games have been played since ancient times. For example, Nim, Wythoff, and their variants are some of the classical pile games. In such games, two players take turns removing chips from the existing pile(s). The rule for removing chips from the pile(s) varies with the game. In Nim, a game with multiple piles, each player may remove any number of chips from one of the available piles, and the player who takes the last chip loses the game (misére play). In some other games, the player who takes the last chip wins the game (normal play). In Wythoff, a game with two piles, a player is allowed to remove any number of chips from one or both piles. When removing chips from both piles, the number of chips removed from each pile must be equal. The player who takes the last chip (remove any chip) wins the game. These games are quite well known and well studied. For example, the “bible of combinatorial game theory”, Winning Ways for Your Mathematical Plays, written by Berlekamp, Conway, and Guy [1] is a good reference for a mathematical introduction to these games.

Recently, Wong and Xu [6] studied a game where two players take turns collecting a specific number of chips, randomly and independently, to build their own piles. The player who collects n chips first is the winner, where n is a non-negative integer. In this paper, we consider a more general version of the game investigated by them. Formally speaking, both players start to play without any chips. At every turn, each player flips a fair coin to decide whether to add a or b chips, where a, b are not necessarily positive, to their own piles. Piles can contain a negative number of chips. The player who collects n chips first is the winner.

Let the random variable S_{k} be the number of chips collected by a player on his k^{th} move, and let A be the first player and B be the second player. The chance that B wins the game by collecting n chips first is

p_{n} = ∑_{k=1}^{∞} P (A does not win on his k^{th} move) · P (B wins on his k^{th} move).  (1)

1.1 Important notation

• p_{n} = the probability of the second player winning the game by collecting n chips first.

• q(n, k) = the probability that a player does not win the game on his k^{th} move, i.e., he never collects n chips on or before his k^{th} move.

• r(n, k) = the probability that a player collects n chips for the first time on his k^{th} move.

The equation (1) can be written as follows:

p_{n} = ∑_{k=1}^{∞} q(n, k) · r(n, k)  (2)

where q(n, k) = P (S_{j} < n for all j = 0, 1, …, k) and r(n, k) = P (S_{k} ≥ n and S_{j} < n for all j = 0, 1, …, k − 1).

A nice connection between the probabilities q(n, k) and r(n, k) is as follows:

Lemma 1. For any positive integer n,

r(n, k) = q(n, k − 1) − q(n, k), k ≥ 1.

Proof. We prove the lemma by the following computation:

r(n, k) = P (S_{k} ≥ n and S_{j} < n, for all j = 0, 1, …, k − 1)
= P (S_{k} ≥ n) − P (S_{k−1} ≥ n)
= (1 − q(n, k)) − (1 − q(n, k − 1))
= q(n, k − 1) − q(n, k).

Remark 2. By Lemma 1 and the fact that q(n, 0) = 1 for all n ≥ 1, we write q(n, k) where k ≥ 1, by

q(n, k) = 1 − ∑_{j=1}^{k} r(n, j).  (3)

The following lemma holds under the condition that the game does not continue indefinitely (the probability that either one of the players wins the game is 1).

Lemma 3. Let n be a fixed positive integer. If lim_{k→∞} q(n, k) = 0 (i.e., a + b ≥ 0; otherwise there is a positive chance that the game will not end), then

∑_{k=1}^{∞} (q(n, k − 1) + q(n, k)) · r(n, k) = 1.

Proof. We prove the lemma by the following computation:

∑_{k=1}^{∞} (q(n, k − 1) + q(n, k)) · r(n, k)

= ∑_{k=1}^{∞} (q(n, k − 1) + q(n, k)) · (q(n, k − 1) − q(n, k)) from Lemma 1

= ∑_{k=1}^{∞} (q(n, k − 1)^{2} − q(n, k)^{2})

= q(n, 0)^{2} − lim_{k→∞} q(n, k)^{2} = 1.

Remark 4. Alternatively, Lemma 3 can also be proven combinatorially as follows:

1 = P ( first player wins) + P ( second player wins) + P ( nobody wins)

= ∑_{k=1}^{∞} r(n, k)q(n, k − 1) + ∑_{k=1}^{∞} q(n, k)r(n, k) + lim_{k→∞} q(n, k)^{2}.

In Theorem 5 below, we write the probability p_{n} in terms of the probabilities r(n, k) only.

Theorem 5. If lim_{k→∞} q(n, k) = 0, then p_{n} = \frac{1}{2} − \frac{1}{2} ∑_{k=1}^{∞} r(n, k)^{2}.

Proof. By definition,

p_{n} = ∑_{k=1}^{∞} q(n, k) · r(n, k).

On the other hand, based on Lemma 3, we have

p_{n} = 1 − ∑_{k=1}^{∞} q(n, k − 1) · r(n, k).

By combining the two equations above, we obtain

p_{n} = \frac{1}{2} − \frac{1}{2} ∑_{k=1}^{∞} (q(n, k − 1) − q(n, k)) · r(n, k).

Then the result follows by applying Lemma 1.

In order to find p_{n}, by Theorem 5, we just need to compute the probabilities r(n, k) and find their sum of squares. For the case {a, b} = {1, 2}, Wong and Xu [6, Theorem 3] obtained the following expression for the probability r(n, k):

r(n, k) = \frac{1}{2^{k}} (\binom{k}{n − k} + \binom{k − 1}{n − k}).

Although it can be shown that the expression ∑_{k=1}^{∞} r(n, k)^{2} does not have a closed-form formula

(strictly speaking, the sum is not Gosper-summable; we refer to Chapter 8 of the book of Petkovsek, Wilf and Zeilberger [3]), nevertheless, an approximation for it was computed by Wong and Xu [6, p. 12]. In particular, they showed that

∑_{k=1}^{∞} r(n, k)^{2} ∼ \sqrt{\frac{27}{8πn}}

when n is large.

Furthermore, they worked on the cases a > 0, b > 0 and asked the readers to investigate the case {a, b} = {−1, 2}. Here we will attempt to answer their question and similarly provide an answer to the case {a, b} = {−1, 1}.

This paper comes with the Maple program Piles which can be found on the second author’s website: www.thotsaporn.com.

2 The case {a, b} = {−1, 1}

Each player adds or removes one chip with a probability 1/2 to or from his pile. The pile is allowed to have a negative number of chips. The first player who collects n chips wins the game.

If n = 0, then the first player will always win the game as both players start to play without any chip. The probability for the second player to win the game is 0, i.e., p_{0} = 0.

2.1 The winning probability for the first non-trivial case: n = 1

In this subsection, we simplify our notation slightly. The probabilities q(1, k) and r(1, k) defined in Section 1 are abbreviated to q(k) and r(k) respectively.

Let C(k) be the number of ways for a player to have no chip on his k^{th} move without ever collecting one chip (so the game still continues). At this point, the reader may notice that the number C(k) is related to the well-known Catalan numbers. In fact, for m ≥ 1, we have

C(2m − 1) = 0

and

C(2m) = \frac{\binom{2m}{m}}{m + 1}.

The probability that the second player collects one chip for the first time on his k^{th} move is

r(k) = \frac{C(k − 1)}{2^{k}}

because the player has no chip on his (k − 1)^{th} move; and on his next move he is required to collect one chip to win the game. Hence, for m ≥ 1, we have

r(2m) = 0

and

r(2m − 1) = \frac{(2m − 2)!}{m!(m − 1)!} · \frac{2}{4^{m}} .

We therefore applied Theorem 5 to find p_{1}, the probability of the second player winning the game by collecting one chip first. Firstly, we needed to verify that the condition lim_{k→∞} q(k) = 0 is true, i.e., the probability that one of the players wins the game by collecting one chip is 1. Equivalently, by (3), we needed to show that

∑_{k=1}^{∞} r(k) = 1.  (4)

There are, however, a number of ways to evaluate this sum. The second author’s favorite tool for evaluating geometric sums (the binomial sum is a geometric sum) is Gosper’s algorithm. The algorithm’s details were beautifully explained in Chapter 5 of Petkovsek, Wilf, and Zeilberger’s [3]. This algorithm has been implemented in all major symbolic computation programs such as Maple and Mathematica. For example, when one types in

                   sum( (2*m-2)!/m!/(m-1)!*2/4^m, m=1..M);

in Maple, it will then return the expression 1 − \frac{(2M)!}{M!M!4^{M}}. By an application of the Stirling

formula: n! ≈ \sqrt{2πn} (\frac{n}{e})^{n}, we note that

1 − \frac{(2M)!}{M!M!4^{M}} → 1 as M → ∞.

Hence, the equation (4) is true.

We are ready to find p_{1} by Theorem 5. To evaluate

∑_{k=1}^{∞} r(k)^{2},

in Maple, we type

            sum( ( (2*m-2)!/m!/(m-1)!*2/4^m )^2, m=1..infinity);

in Maple, it will then return \frac{4}{π} − 1. By Theorem 5,

p_{1} = \frac{1}{2} − \frac{1}{2} (\frac{4}{π} − 1) ≈ 0.3633802277.

Hence, we easily obtained the value of p_{1} by applying Theorem 5 and the summation tools in Maple.

2.2 The winning probabilities for the cases n ≥ 2

Analogously, let C(n, k) be the number of ways for a player to have n − 1 chips on his k^{th} move without ever collecting n chips.

Lemma 6. For n ≥ 0, k ≥ 1 such that n − k ≡ 0 (mod 2), we have

C(n, k) = 0.

Otherwise, for s ≥ 0, we have

C(2s + 1, 2m) = \frac{2s + 1}{m + s + 1}\binom{2m}{m − s}, for m ≥ 0,
C(2s, 2m − 1) = \frac{s}{m}\binom{2m}{m − s}, for m ≥ 1.

Proof. The main recurrence relation for the numbers C(n, k) is

C(n, k) = C(n − 1, k − 1) + C(n + 1, k − 1), n ≥ 1, k ≥ 1.

If the first move is 1, then the number of ways for a player to have n − 1 chips on his k^{th} move is C(n − 1, k − 1). On the other hand, if the first move is −1, then this number is C(n + 1, k − 1). We rearranged the terms and shifted the variables to obtain

C(n, k) = C(n − 1, k + 1) − C(n − 2, k), n ≥ 2, k ≥ 0.  (5)

Then, the results follow by induction on n where base cases are given by

C(0, k) = 0, C(1, 2m − 1) = 0 and C(1, 2m) = \frac{\binom{2m}{m}}{m + 1}.

It is also important to note that C(n, 0) = 0 for all n ≥ 0 except C(1, 0) = 1.

We proceed in the same manner as in Section 2.1. The following relation between the numbers r(n, k) and C(n, k − 1) is true for n ≥ 0:

r(n, k) = \frac{C(n, k − 1)}{2^{k}}.  (6)

By Lemma 6, for n ≥ 0, k ≥ 1 and n − k ≡ 1 (mod 2), we have

r(n, k) = 0.  (7)

Otherwise, for s ≥ 0, we have

r(2s + 1, 2m + 1) = \frac{C(2s + 1, 2m)}{2^{2m+1}} = \frac{2s + 1}{(m + s + 1) · 2 · 4^{m}} \binom{2m}{m − s}, for m ≥ 0,
r(2s, 2m) = \frac{C(2s, 2m − 1)}{2^{2m}} = \frac{s}{m · 4^{m}} \binom{2m}{m − s}, for m ≥ 1.

To apply Theorem 5, it is necessary to prove the following lemma.

Lemma 7. For each n ≥ 1, the probability that one of the players wins the game (by collecting n chips first) is 1, i.e.,

∑_{k=1}^{∞} r(n, k) = 1.

Proof. This can be done by induction on n. By (5) and (6), we have the following recurrence relation for the numbers r(n, k):

r(n, k) = \frac{C(n, k − 1)}{2^{k}} = \frac{C(n − 1, k)}{2^{k}} − \frac{C(n − 2, k − 1)}{2^{k}}
= 2r(n − 1, k + 1) − r(n − 2, k).  (8)

By (4), we note that

∑_{k=1}^{∞} r(1, k) = 1.  (9)

For n = 2, by (8) and (9), we get

∑_{k=1}^{∞} r(2, k) = ∑_{k=1}^{∞} (2r(1, k + 1) − r(0, k)) = 2 ∑_{k=1}^{∞} r(1, k + 1) + 2r(1, 1) − 2r(1, 1)

= 2 ∑_{k=1}^{∞} r(1, k) − 2r(1, 1) = 2 − 1 = 1

since r(0, k) = 0 for all k ≥ 1.

For the cases n ≥ 3, by (8) and the inductive hypothesis, we have

∑_{k=1}^{∞} r(n, k) = ∑_{k=1}^{∞} (2r(n − 1, k + 1) − r(n − 2, k))

= 2 ∑_{k=1}^{∞} r(n − 1, k) − ∑_{k=1}^{∞} r(n − 2, k) = 2 − 1 = 1

since r(n − 1, 1) = 0 for all n ≥ 3.

Finally, we are in the position to apply Theorem 5 for each value of n. For example, to

evaluate ∑_{k=1}^{∞} r(2, k)^{2}, we type

              sum( (binomial(2*m,m-1)/m/4^m)^2 ,m=1..infinity);

and then Maple will return \frac{16}{π} − 5. By Theorem 5,

p_{2} = \frac{1}{2} − \frac{1}{2}(\frac{16}{π} − 5) ≈ 0.4535209109.

For n ≥ 3, we list some values of ∑_{k=1}^{∞} r(n, k)^{2} as follows:

∑_{k=1}^{∞} r(3, k)^{2} = \frac{236}{3π} − 25,

∑_{k=1}^{∞} r(4, k)^{2} = \frac{1216}{3π} − 129,

∑_{k=1}^{∞} r(5, k)^{2} = \frac{32092}{15π} − 681,

∑_{k=1}^{∞} r(6, k)^{2} = \frac{172144}{15π} − 3653.

The corresponding values of p_{n} are

p_{3} ≈ 0.4798111434,
p_{4} ≈ 0.4891964033,
p_{5} ≈ 0.4933044576,
p_{6} ≈ 0.4954322531.

There is an interesting pattern for the values of ∑_{k=1}^{∞} r(n, k)^{2} for n ≥ 1. In fact, let T_{n} be

∑_{k=1}^{∞} r(n, k)^{2}. The terms T_{n} appear to satisfy a recurrence relation with polynomial coeffi-

cients:

(n + 3)T_{n+3} − (7n + 16)T_{n+2} + (7n + 5)T_{n+1} − nT_{n} = 0.  (10)

(The guessing recurrence relation was found by a holonomic ansatz, i.e., we assume that the sequence T_{n} satisfies a relation of the form

(a_{0}n + b_{0})T_{n} + (a_{1}n + b_{1})T_{n+1} + ⋯ + (a_{N}n + b_{N})T_{n+N} = 0

for some specific N. Then, by plugging in values of n, T_{n}, T_{n+1}, …, T_{n+N}, say, for n = 1, 2, …, 30, we can solve the system of linear equations for the unknowns a_{i} and b_{i}.) The authors believe that it can be shown formally by Zeilberger’s algorithm [3, Chapter 6] and Zeilberger’s Maple package Ekhad. However, since the terms T_{n} are separated into two cases (n is odd or n is even), the proof may not be straightforward.

Based on the recurrence relation (10), we obtain the asymptotic approximation of T_{n} (see Wimp and Zeilberger [5]) as follows:

T_{n} = \frac{1}{πn^{2}} (1 + \frac{1}{n^{2}} + \frac{19}{4n^{4}} + \frac{107}{2n^{6}} + …) + O(α^{n})

for some α such that |α| < 1.

2.3 The winning probability within k moves

The case {a, b} = {−1, 1} is unique in the sense that we were able to provide response to more questions than initially asked. In this subsection, for a fixed positive integer n, we find the probability that the second player wins the game within k moves. Similarly, it can be resolved by employing Gosper’s algorithm!

First, we demonstrate it for the case n = 1. The other cases can be carried out in the same manner, but case by case. We recall from Section 2.1 that

r(2m) = 0

and

r(2m − 1) = \frac{(2m − 2)!}{m!(m − 1)!} · \frac{2}{4^{m}} .

By Remark 2, we have

q(2m) = q(2m − 1) = 1 − ∑_{j=1}^{m} r(2j − 1) = 1 − ∑_{j=1}^{m} \frac{(2j − 2)!}{j!(j − 1)!} · \frac{2}{4^{j}} .

This finite sum is Gosper-summable. In Maple, we type

            simplify( 1-sum( (2*j-2)!*2/j!/(j-1)!/4^j ,j=1..m));

and the output is \frac{\binom{2m}{m}}{4^{m}}. (The expression is so nice! It is screaming for a combinatorial explanation!)

Lastly, the probability that the second player wins the game within k moves (the partial sum of (2)) is

∑_{i=1}^{k} q(i)r(i) = \begin{matrix}⌊ & \frac{k+1}{2} & ⌋ \\ ∑ \\ j=1 \end{matrix} q(2j − 1)r(2j − 1)

= \begin{matrix}⌊ & \frac{k+1}{2} & ⌋ \\ ∑ \\ j=1 \end{matrix} \frac{\binom{2j}{j}}{4^{j}} \frac{(2j − 2)!}{j!(j − 1)!} · \frac{2}{4^{j}}

= \begin{matrix}⌊ & \frac{k+1}{2} & ⌋ \\ ∑ \\ j=1 \end{matrix} \binom{2j}{j}^{2} · \frac{1}{16^{j}} · \frac{1}{2j − 1}.

In Maple, we type

                sum(binomial(2*j,j)^2/16^j/(2*j-1),j=1..L);

and then we again have a closed-form solution. The probability that the second player wins the game within k moves is

1 − \frac{2L + 1}{16^{L}} \binom{2L}{L}^{2}, where L = ⌊\frac{k + 1}{2}⌋ .

2.4 Average duration of a game

The work in the previous section now raises a question on the duration of a game. Hence, suggesting a potential research topic looking into the average duration of different games. As a reference, we refer to the work carried out by Robinson and Vijay [4] on the duration of the game Dreidel.

Let the random variable X be the number of moves required to end the game.

Theorem 8. For any take-away move {a, b} where a and b are not necessarily positive, the

average duration of the game is ∑_{k=0}^{∞} q(n, k)^{2}.

Proof. We compute E[X] as follows:

E[X] = ∑_{k=1}^{∞} k · P ( the game ends at the k^{th} turn)

= ∑_{k=1}^{∞} k · (q(n, k − 1)r(n, k) + q(n, k)r(n, k))

= ∑_{k=1}^{∞} k · (q(n, k − 1)^{2} − q(n, k)^{2})

= ∑_{k=1}^{∞} q(n, k − 1)^{2}.

The result follows by shifting the index k by 1.

Corollary 9. For the case {a, b} = {−1, 1}, E[X] = ∞ for any n ≥ 1.

Proof. For n = 1, by our computation of the probability q(k) in Section 2.3, we have

E[X] = ∑_{k=0}^{∞} q(k)^{2} = 1 + 2 · ∑_{m=1}^{∞} (\frac{\binom{2m}{m}}{4^{m}})^{2} = ∞.

The last equality was found by Maple. But we can also show that it is true by the following approximation:

(\frac{\binom{2m}{m}}{4^{m}})^{2} ≈ \frac{1}{πm} as m → ∞.

The sum indeed diverges, but the rate of divergence is as slow as the harmonic series. For n > 1, it is clear that the average duration of the game will be longer than the average duration of the game for the case n = 1. Therefore, E[X] = ∞ holds true for n > 1.

3 The case {a, b} = {−1, 2}

For this case, each player is allowed to add two chips to his pile or remove one chip from his pile; each with probability 1/2. The pile is allowed to have a negative number of chips. The first player who collects n chips wins the game.

Let D(n, k) be the number of ways for a player to have n − 1 or n − 2 chips on his k^{th} move without ever collecting n chips (thus allowing the game to continue).

Lemma 10. The numbers D(n, k) satisfy the following recurrence relation:

D(n, k) = D(n − 1, k + 1) − D(n − 3, k)

with base cases D(−1, k) = D(0, k) = 0 and

D(1, 3m) = \frac{\binom{3m}{m}}{2m + 1}, D(1, 3m + 1) = \frac{\binom{3m+1}{m+1}}{2m + 1}, D(1, 3m + 2) = 0.

Proof. The recurrence relation arises from whether the first move is +2 or −1, i.e.,

D(n, k) = D(n − 2, k − 1) + D(n + 1, k − 1).

After shifting indexes and rearranging terms, we obtained the desired recurrence relation.

For the base cases, the sequence of non-negative integers D(1, 3m) is a generalization of Catalan numbers. More precisely, the number D(1, 3m) is the number of ways for the permutation of 2m copies of −1 and m copies of 2 such that the partial sum is never greater than 0. It is the sequence \underline{A001764} in OEIS and was named 3-Raney sequences [2, Section 7.5]. Similarly, the number D(1, 3m+1) is the number of ways for the permutation of 2m+1 copies of −1 and m copies of 2 such that the partial sum is never greater than 0. It is the sequence \underline{A006013} in OEIS.

We have the following relation

r(n, k) = \frac{D(n, k − 1)}{2^{k}}

because the player has n − 1 or n − 2 chips on his (k − 1)^{th} move; and on his next move he is required to collect two chips to win the game. Also, it is intuitively clear that the number q(n, k) in this case is less than or equal to q(n, k) for the case {a, b} = {−1, 1} for any fixed

n and k. Therefore, lim_{k→∞} q(n, k) = 0 for each n ≥ 0. For each n ≥ 1, we evaluate ∑_{k=1}^{∞} r(n, k)^{2}

and apply Theorem 5 to find the winning probability of the second player. However, this sum is not Gosper-summable, i.e., there is no nice closed-form formula for the partial sum; and these sums do not appear to converge to any famous constant either. We list some of their numerical values in Table 1 below.

\begin{matrix}n & ∑_{k=1}^{∞} r(n, k)^{2} & p_{n} \\ 1 & 0.3221721826105... & 0.33891390869471156... \\ 2 & 0.2886887304423... & 0.35565563477884626... \\ 3 & 0.1547549217692... & 0.42262253911538507... \\ 4 & 0.1241072133089... & 0.43794639334553199... \\ 5 & 0.0941564190484... & 0.45292179047578731... \\ 10 & 0.047917368748... & 0.47604131562562199... \\ 20 & 0.028469734522... & 0.48576513273891113... \\ 100 & 0.010952807500... & 0.49452359624969611... \end{matrix}

Table 1: The values of ∑_{k=1}^{∞} r(n, k)^{2} and p_{n} for some n

4 A remark on Theorem 5

We would like to find an analog of Theorem 5 when players have the same set of moves (add a or b chips); but now the first player wins the game if he collects n_{1} chips first and the second player wins the game if he collects n_{2} chips first.

For a fixed set of moves {a, b}, let p_{n_{1},n_{2}} be the probability that the second player collects n_{2} chips before the first player collects n_{1} chips. Then

p_{n_{1},n_{2}} = ∑_{k=1}^{∞} q(n_{1}, k) · r(n_{2}, k).  (11)

Similarly, the probability that the first player collects n_{1} chips before the second player collects n_{2} chips is

∑_{k=1}^{∞} q(n_{2}, k − 1) · r(n_{1}, k).

Assuming that the game will not continue indefinitely (the probability that either one of the players wins the game is 1), i.e., a + b ≥ 0, we have

∑_{k=1}^{∞} q(n_{2}, k − 1) · r(n_{1}, k) + ∑_{k=1}^{∞} q(n_{1}, k) · r(n_{2}, k) = 1.

By Lemma 1, we have a generalization of Theorem 5 as follows:

Proposition 11. For a fixed set of moves {a, b}, let p_{n_{1},n_{2}} be the probability that the second player collects n_{2} chips before the first player collects n_{1} chips. If the probability that either one of the players wins the game is 1, then

p_{n_{1},n_{2}} + p_{n_{2},n_{1}} + ∑_{k=1}^{∞} r(n_{1}, k) · r(n_{2}, k) = 1.

4.1 The probability p_{n_{1},n_{2}} for the case {a, b} = {−1, 1}

We list some values of p_{n_{1},n_{2}} obtained by the equation (11) in Table 2 below. Note again that, for any fixed n, the probability q(n, k) exhibits a nice closed-form expression in k. For example, in Section 2.3, we obtained

q(1, 2m) = q(1, 2m − 1) = \frac{\binom{2m}{m}}{4^{m}}.

Based on the closed-form expression of q(n, k) and Lemma 1, we can simplify the infinite sums in the equation (11) nicely for different values of n_{1} and n_{2}. For more values of p_{n_{1},n_{2}}, one can use the function Win2(n_{1}, n_{2}) in the accompanied Maple program.

\begin{matrix}n_{1} \ n_{2} & 1 & 2 & 3 & 4 & 5 \\ 1 & \frac{π − 2}{π} & \frac{4 − π}{π} & \frac{10 − 3π}{π} & \frac{3π − 8}{3π} & \frac{15π − 46}{3π} \\ 2 & \frac{2(π − 2)}{π} & \frac{3π − 8}{π} & \frac{2(10 − 3π)}{π} & \frac{3(16 − 5π)}{π} & \frac{2(15π − 46)}{3π} \\ 3 & \frac{3π − 2}{3π} & \frac{7π − 20}{π} & \frac{39π − 118}{3π} & \frac{296 − 93π}{3π} & \frac{5(142 − 45π)}{3π} \\ 4 & \frac{8}{3π} & \frac{16 − 3π}{3π} & \frac{8(12π − 37)}{3π} & \frac{195π − 608}{3π} & \frac{8(63 − 20π)}{π} \\ 5 & \frac{5π − 2}{5π} & \frac{92 − 27π}{3π} & \frac{926 − 285π}{15π} & \frac{7(23π − 72)}{π} & \frac{5115π − 16046}{15π} \end{matrix}

Table 2: The winning probability of the second player, p_{n_{1},n_{2}}

5 Future Work

Based on our work above, we suggest the following open problems:

1. Formally prove that the guessed recurrence relation (10) for the terms ∑_{k=1}^{∞} r(n, k)^{2}

(where n ≥ 0) for the case {a, b} = {−1, 1} is correct.

2. Find a recurrence relation for the terms ∑_{k=1}^{∞} r(n, k)^{2} (where n ≥ 0) for the case {a, b} =

{−1, 2}, and then find an asymptotic approximation for it.

3. In this paper, we allow the number of chips in the pile to be negative. As an alternative way to play the game, one may investigate the scenario where the players are not allowed to have a negative number of chips, i.e., the number of chips stays at 0 when the player gets to take a negative number of chips.

6 Acknowledgments

We are grateful to the editor-in-chief and to the referee(s) for their useful comments and suggestions. We are also grateful to Ramesh Boonratana for his generous assistance in proofreading the article.

References

[1] E. Berlekamp, J. Conway, and R. Guy, Winning Ways for Your Mathematical Plays. Vol. 2, 2nd edition, A. K. Peters, 2001.

[2] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.

[3] M. Petkovsek, H. Wilf, and D. Zeilberger, A = B, 1st edition, A. K. Peters, 1996.

[4] T. Robinson and S. Vijay, Dreidel lasts O(N^{2}) spins, Adv. in Appl. Math. 36 (2006), 85–94.

[5] J. Wimp and D. Zeilberger, Resurrecting the asymptotics of linear recurrences, J. Math. Anal. Appl. 111 (1985), 162–177 .

[6] T. W. H. Wong and J. Xu, A probabilistic take-away game, J. Integer Sequences 21 (2018), Article 18.6.3.

2010 Mathematics Subject Classification: Primary 91A60; Secondary 05A10, 11Y55, 60C05. Keywords: take-away game, probability, Gosper’s algorithm.

(Concerned with sequences \underline{A000108}, \underline{A001764}, and \underline{A006013}.)

Received March 22 2019; revised versions received May 19 2019; June 29 2019. Published in Journal of Integer Sequences, August 19 2019.

Return to Journal of Integer Sequences home page.