A Probabilistic Take-Away Game

Tony W. H. Wong and Jiao Xu Department of Mathematics Kutztown University of Pennsylvania Kutztown, PA 19530 USA

                       wong@kutztown.edu
                   jxu399@live.kutztown.edu

Abstract

Alice and Bob are playing a very simple game. Each of them starts with a pile of n chips, and they take turns to remove 1 or 2 chips from their own pile randomly and independently with equal probability. The first player who removes all chips from their pile is the winner. In this paper, we find the winning probability for Bob and analyze a new integer sequence. We also show that this game is highly disadvantageous to the second player, which is counter-intuitive. Furthermore, we study several variations of this game and determine the winning probability for Bob in each case.

1 Introduction

Take-away games are mathematical games that involve two players, who take turns to remove items from a pile or multiple piles of objects. The winner is the first player achieving a certain predefined goal.

Here is a classical single-pile take-away game: Alice and Bob take turns to remove 1 or 2 chips from a pile of finitely many chips, with Alice going first. Whoever removes the last chip is the winner. Such a game and many variations are well-studied, for example by Schwenk [4].

Another similar take-away game is the game of Nim. It involves multiple piles, and each player may remove one or more chips from one of the piles. Again, whoever removes the last chip is the winner. Berlekamp, Conway, and Guy [2] as well as Bouton [3] thoroughly discussed the strategies of this game.

In recent years, mathematicians revisited many well-studied deterministic problems in a probabilistic setting. In this paper, we begin with a basic version of a probabilistic take-away game: Alice and Bob each have a pile of n chips, and they take turns to remove 1 or 2 chips from their pile, with Alice going first. Whether to remove 1 or 2 chips is decided by flipping a fair coin. In other words, every move is independent, and the probability of removing 1 or

2 chips is \frac{1}{2} each. If there is only 1 chip left in the pile, then it is removed with probability 1 in the next move. The first player who removes all chips from their pile is the winner. Equivalently, the game can be played in the following manner: Alice and Bob start with no chips, and they take turns to collect 1 or 2 chips randomly and independently with equal probability. The first person who collects at least n chips is the winner. This model of the game avoids the complication when there is only 1 chip left, thus it is preferred and will be adopted in this paper.

Let p_{n} denote the probability that Bob wins by collecting at least n chips before Alice

does. At first glance, one may suggest that p_{n} = \frac{1}{2} since the game seems to be fair to

both Alice and Bob. With more thought, one may realize that p_{n} ≤ \frac{1}{2} since Bob is in a disadvantageous position by having one fewer move half the time. It is also reasonable to

predict that p_{n} converges to \frac{1}{2} as n goes to infinity. In this paper, we study precisely what p_{n} is for each n, and how this sequence behaves.

It is apparent that p_{1} = 0, since Alice wins on the first move. When n = 2, Bob can only win if Alice collects 1 chip in her first move and Bob collects 2 in his first move, implying

that p_{2} = \frac{1}{4}. To study p_{n} in general, we need some formal definitions.

Let X_{1}, X_{2}, …, X_{n}, Y_{1}, Y_{2}, …, Y_{n} be independent identically distributed random variables

such that ℙ(X_{i} = 1) = ℙ(X_{i} = 2) = ℙ(Y_{i} = 1) = ℙ(Y_{i} = 2) = \frac{1}{2}, where X_{i} and Y_{i} represent the number of chips collected by Alice and Bob in the i-th move respectively.

Before we proceed to derive the formula, let us first study the initial terms of p_{n}. As

mentioned, p_{1} = 0 and p_{2} = \frac{1}{4}. The following calculations find p_{n} when n = 3, 4, 5, 6, and 7. When n = 3,

p_{3} = ℙ((X_{1}, X_{2}) = (1, 1)) · ℙ((Y_{1}, Y_{2}) = (1, 2), (2, 1), or (2, 2))

= \frac{1}{4} · \frac{3}{4} = \frac{3}{16}.

When n = 4,

p_{4} = ℙ((X_{1}, X_{2}) = (1, 1), (1, 2), or (2, 1)) · ℙ((Y_{1}, Y_{2}) = (2, 2))

+ ℙ((X_{1}, X_{2}, X_{3}) = (1, 1, 1))

· ℙ((Y_{1}, Y_{2}, Y_{3}) = (1, 1, 2), (1, 2, 1), (2, 1, 1), (1, 2, 2), or (2, 1, 2))

= \frac{3}{4} · \frac{1}{4} + \frac{1}{8} · \frac{5}{8} = \frac{17}{64}.

When n = 5,

p_{5} = ℙ((X_{1}, X_{2}, X_{3}) = (1, 1, 1), (1, 1, 2), (1, 2, 1), or (2, 1, 1))

· ℙ((Y_{1}, Y_{2}, Y_{3}) = (1, 2, 2), (2, 1, 2), (2, 2, 1), or (2, 2, 2)) + ℙ((X_{1}, X_{2}, X_{3}, X_{4}) = (1, 1, 1, 1)) · ℙ((Y_{1}, Y_{2}, Y_{3}, Y_{4}) = (1, 1, 1, 2), (1, 1, 2, 1), (1, 2, 1, 1), (2, 1, 1, 1), (1, 1, 2, 2), (1, 2, 1, 2),

or (2, 1, 1, 2))

= \frac{1}{2} · \frac{1}{2} + \frac{1}{16} · \frac{7}{16} = \frac{71}{256}.

When n = 6,

p_{6} = ℙ((X_{1}, X_{2}, X_{3}) ≠ (2, 2, 2)) · ℙ((Y_{1}, Y_{2}, Y_{3}) = (2, 2, 2))

+ ℙ((X_{1}, X_{2}, X_{3}, X_{4}) = (1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 2, 1), (1, 2, 1, 1), or (2, 1, 1, 1)) · ℙ((Y_{1}, Y_{2}, Y_{3}, Y_{4}) = (1, 1, 2, 2), (1, 2, 1, 2), (1, 2, 2, 1), (2, 1, 1, 2), (2, 1, 2, 1), (2, 2, 1, 1),

(1, 2, 2, 2), (2, 1, 2, 2) or (2, 2, 1, 2))

+ ℙ((X_{1}, X_{2}, X_{3}, X_{4}, X_{5}) = (1, 1, 1, 1, 1)) · ℙ((Y_{1}, Y_{2}, Y_{3}, Y_{4}, Y_{5}) = (1, 1, 1, 1, 2), (1, 1, 1, 2, 1), (1, 1, 2, 1, 1), (1, 2, 1, 1, 1), (2, 1, 1, 1, 1),

(1, 1, 1, 2, 2), (1, 1, 2, 1, 2), (1, 2, 1, 1, 2), or (2, 1, 1, 1, 2))

= \frac{7}{8} · \frac{1}{8} + \frac{5}{16} · \frac{9}{16} + \frac{1}{32} · \frac{9}{32} = \frac{301}{1024}.

p_{7} = ℙ((X_{1}, X_{2}, X_{3}, X_{4}) ≠ (1, 2, 2, 2), (2, 1, 2, 2), (2, 2, 1, 2), (2, 2, 2, 1), and (2, 2, 2, 2))

· ℙ((Y_{1}, Y_{2}, Y_{3}, Y_{4}) = (1, 2, 2, 2), (2, 1, 2, 2), (2, 2, 1, 2), (2, 2, 2, 1), or (2, 2, 2, 2)) + ℙ((X_{1}, X_{2}, X_{3}, X_{4}, X_{5}) = (1, 1, 1, 1, 1), (1, 1, 1, 1, 2), (1, 1, 1, 2, 1), (1, 1, 2, 1, 1),

(1, 2, 1, 1, 1), or (2, 1, 1, 1, 1))

· ℙ((Y_{1}, Y_{2}, Y_{3}, Y_{4}, Y_{5}) = (1, 1, 1, 2, 2), (1, 1, 2, 1, 2), (1, 1, 2, 2, 1), (1, 2, 1, 1, 2),

(1, 2, 1, 2, 1), (1, 2, 2, 1, 1), (2, 1, 1, 1, 2), (2, 1, 1, 2, 1),
(2, 1, 2, 1, 1), (2, 2, 1, 1, 1), (1, 1, 2, 2, 2), (1, 2, 1, 2, 2),
(1, 2, 2, 1, 2), (2, 1, 1, 2, 2), (2, 1, 2, 1, 2), or (2, 2, 1, 1, 2))

+ ℙ((X_{1}, X_{2}, X_{3}, X_{4}, X_{5}, X_{6}) = (1, 1, 1, 1, 1, 1))

· ℙ((Y_{1}, Y_{2}, Y_{3}, Y_{4}, Y_{5}, Y_{6}) = (1, 1, 1, 1, 1, 2), (1, 1, 1, 1, 2, 1), (1, 1, 1, 2, 1, 1), (1, 1, 2, 1, 1, 1),

(1, 2, 1, 1, 1, 1), (2, 1, 1, 1, 1, 1), (1, 1, 1, 1, 2, 2), (1, 1, 1, 2, 1, 2),
(1, 1, 2, 1, 1, 2), (1, 2, 1, 1, 1, 2), or (2, 1, 1, 1, 1, 2))

= \frac{11}{16} · \frac{5}{16} + \frac{6}{32} · \frac{16}{32} + \frac{1}{64} · \frac{11}{64} = \frac{1275}{4096}.

From these calculations, it seems that the denominator of p_{n} is 4^{n−1}. As for the numerator, we observe that the sequence 3, 17, 71, 301, 1275 satisfies the recurrence relation x_{n+2} = 4x_{n+1} + x_{n}. However, when we use these two observations to project p_{100}, we get p_{100} ≈ 64.4353, which is absurd since p_{n} ≤ 1. In other words, the pattern developed from small cases is not helpful, so we need to generalize our calculations to obtain a formula for p_{n}. Nevertheless, the fact that these five terms satisfy an elegant recurrence relation is interesting.

In Section 2, we present a complete solution for this basic probabilistic take-away game. In Section 3, we discuss two integer sequences obtained from this result. In Section 4, we extend our calculations to some general versions of this probabilistic take-away game. Finally, in Section 5, we discuss some numerical computations and approximations of the probabilities, as well as some open questions.

2 Results for the basic version

Let S_{k} = ∑_{i=1}^{k} X_{i}, and T_{k} = ∑_{i=1}^{k} Y_{i}. It is clear that

p_{n} = ∑_{k=1}^{n} (ℙ(S_{k} < n) · ℙ(T_{k} ≥ n and T_{k−1} < n)).  (1)

Let s_{k} = |{i : X_{i} = 2, 1 ≤ i ≤ k}|, and let t_{k} = |{i : Y_{i} = 2, 1 ≤ i ≤ k}|. Notice that s_{k} + k = S_{k} and t_{k} + k = T_{k}. Hence, equation (1) becomes

p_{n} = ∑_{k=1}^{n} (ℙ(s_{k} < n − k) · ℙ(t_{k} ≥ n − k and t_{k−1} < n − (k − 1))).

Note that ℙ(s_{k} < n − k) = \frac{1}{2^{k}} ∑_{i=0}^{n−k−1} \binom{k}{i}. Let h_{k} = ∑_{i=0}^{n−k−1} \binom{k}{i}, so ℙ(s_{k} < n − k) = \frac{h_{k}}{2^{k}}.

Then

ℙ(t_{k} ≥ n − k and t_{k−1} < n − (k − 1)) = ℙ(t_{k} ≥ n − k) − ℙ(t_{k−1} ≥ n − (k − 1))

= \frac{1}{2^{k}} ∑_{i=n−k}^{k} \binom{k}{i} − \frac{1}{2^{k−1}} ∑_{i=n−(k−1)}^{k−1} \binom{k − 1}{i}

= 1 − \frac{h_{k}}{2^{k}} − (1 − \frac{h_{k−1}}{2^{k−1}} ) = \frac{2h_{k−1} − h_{k}}{2^{k}} .

Hence, p_{n} = ∑_{k=1}^{n} \frac{h_{k}(2h_{k−1} − h_{k})}{4^{k}}. If we rearrange the terms, we have

p_{n} = \frac{2h_{1}h_{0}}{4} + ∑_{k=2}^{n} \frac{−4h_{k−1}^{2} + 2h_{k−1}h_{k}}{4^{k}} − \frac{h_{n}^{2}}{4^{n}} = 1 + ∑_{k=2}^{n} \frac{2h_{k−1}(h_{k} − 2h_{k−1})}{4^{k}},

since h_{0} = 1, h_{1} = 2, and h_{n} = 0. By adding the two expressions for p_{n} obtained in the last two lines and dividing the sum by 2, we have

p_{n} = \frac{1}{2} − \frac{1}{2} ∑_{k=2}^{n} \frac{(2h_{k−1} − h_{k})^{2}}{4^{k}} = \frac{1}{2} − \frac{1}{2} ∑_{k=1}^{n} \frac{(2h_{k−1} − h_{k})^{2}}{4^{k}} .  (2)

Finally, we have the following lemma.

Lemma 1. Let h_{k} = ∑_{i=0}^{n−k−1} \binom{k}{i}. Then 2h_{k−1} − h_{k} = \binom{k}{n − k} + \binom{k − 1}{n − k}.

Proof.

2h_{k−1} − h_{k} = 2 ∑_{i=0}^{n−(k−1)−1} \binom{k − 1}{i} − ∑_{i=0}^{n−k−1} \binom{k}{i}

= 2 ∑_{i=0}^{n−k} \binom{k − 1}{i} − ∑_{i=1}^{n−k−1} (\binom{k − 1}{i} + \binom{k − 1}{i − 1}) − \binom{k}{0}

= \binom{k − 1}{0} + 2\binom{k − 1}{n − k} + \binom{k − 1}{n − k − 1} − \binom{k}{0} = \binom{k − 1}{n − k} + \binom{k}{n − k}.

Remark 2. The above proof of Lemma 1 is purely algebraic. Here is an alternate proof that is more combinatorial.

\frac{2h_{k−1} − h_{k}}{2^{k}} = ℙ(t_{k} ≥ n − k and t_{k−1} < n − (k − 1))

= ℙ(T_{k} ≥ n and T_{k−1} < n)

= ℙ(T_{k} = n or (T_{k−1} = n − 1 and X_{k} = 2)) = ℙ(t_{k} = n − k or (t_{k−1} = n − k and X_{k} = 2))

= \frac{\binom{k}{n−k}}{2^{k}} + \frac{\binom{k−1}{n−k}}{2^{k−1}} · \frac{1}{2} = \frac{\binom{k}{n−k} + \binom{k−1}{n−k}}{2^{k}},

which yields our desired result.

Applying Lemma 1 to equation (2), we obtain the following theorem.

Theorem 3. Alice and Bob take turns to collect 1 or 2 chips randomly and independently with equal probability. The probability that Bob collects at least n chips before Alice is

p_{n} = \frac{1}{2} − \frac{1}{2} ∑_{k=1}^{n} \frac{1}{4^{k}} (\binom{k}{n − k} + \binom{k − 1}{n − k})^{2} .

It is worth noting that the summation can start from k = ⌈\frac{n}{2}⌉, since all the summands

are zero when k < \frac{n}{2}. However, we decide to start the summation from k = 1 since it is more elegant.

3 Observations on the sequences

Let p_{n} = \frac{c_{n}}{d_{n}}, where c_{n} and d_{n} are nonnegative integers that are relatively prime. Notice that

4^{n−1}p_{n} = \frac{4^{n−1}}{2} − \frac{1}{2} ∑_{k=1}^{n} 4^{n−k−1} (\binom{k}{n − k} + \binom{k − 1}{n − k})^{2} is an odd integer, since

\frac{1}{2} ∑_{k=n−1}^{n} 4^{n−k−1} (\binom{k}{n − k} + \binom{k − 1}{n − k})^{2}

= \frac{1}{2} ((\binom{n − 1}{1} + \binom{n − 2}{1})^{2} + 4^{−1} (\binom{n}{0} + \binom{n − 1}{0})^{2})

= \frac{1}{2}((2n − 3)^{2} + 1) = 2n^{2} − 6n + 5

is an odd integer, and all other summands are even. In other words, d_{n} = 4^{n−1}, and

c_{n} = \frac{1}{8} (4^{n} − ∑_{k=1}^{n} 4^{n−k} (\binom{k}{n − k} + \binom{k − 1}{n − k})^{2}). As mentioned in Section 1, we observed that c_{3}, c_{4}, c_{5}, c_{6}, and c_{7} satisfy the recurrence relation x_{n+2} = 4x_{n+1}+x_{n}, but this recurrence relation does not hold from c_{8} onwards. The integer sequence c_{n} is added to the On-Line Encyclopedia of Integer Sequences (OEIS), listed as \underline{A265919}. The integer sequence formed by the numerators of the winning probabilities for Alice is listed as \underline{A265920}.

Apart from the integer sequences that we discovered, we are also very interested in the sequence of fractions p_{n}. The disadvantage that Bob has due to Alice going first should be less significant as n increases, so it is reasonable to believe that p_{n} should increase with n. This trend is mostly true: with the exception of n = 3, p_{n−1} < p_{n} for all n up to 5000.

Another interesting observation about p_{n} is that its convergence rate towards \frac{1}{2} is slow. For example, p_{100} ≈ 44.83%, which is very surprising since most people would believe that the disadvantage of Bob is insignificant by the time n reaches 100. In fact, p_{1000} ≈ 48.36%, p_{10000} ≈ 49.48%, and p_{100000} ≈ 49.84%. In other words, the fact that Bob starts second puts him in a significantly disadvantageous position, which is counter-intuitive.

Theorem 3 solves this basic probabilistic take-away game, but there are several variations of the game that one can study. For instance, what is the winning probability for Bob in the following scenarios?

1. Alice and Bob take turns to collect a or b chips randomly and independently with equal probability, where a < b are positive integers.

2. Alice and Bob take turns to collect a or b chips randomly and independently with probabilities p and 1 − p respectively, where a < b are positive integers and p ∈ [0, 1].

3. Alice and Bob take turns to collect a_{1}, a_{2}, …, or a_{m} chips randomly and independently with probabilities p_{1}, p_{2}, …, p_{m} respectively, where a_{1} < a_{2} < ⋯ < a_{m} are positive integers, p_{1}, p_{2}, …, p_{m} ∈ [0, 1], and p_{1} + p_{2} + ⋯ + p_{m} = 1.

4 Results for general cases

Before we proceed, let us introduce a different proof of Theorem 3. This proof is due to Taoye Zhang (personal communication, October 2015). Let X_{1}, X_{2}, …, X_{n}, Y_{1}, Y_{2}, …, Y_{n} be independent identically distributed integer-valued random variables, where X_{i} and Y_{i} represent the number of chips collected by Alice and Bob in the i-th move respectively. Let S_{k} = ∑_{i=1}^{k} X_{i}, and T_{k} = ∑_{i=1}^{k} Y_{i}. Let r_{k} = ℙ(S_{k} ≥ n and S_{k−1} < n), and let a be the minimum positive integer such that ℙ(X_{1} = a) > 0.

Lemma 4. The probability that Bob wins the game is \frac{1}{2} − \frac{1}{2} ∑_{k=1}^{⌈ \frac{n}{a} ⌉} r_{k}^{2}.

Proof. Since \{S_{k} ≥ n and S_{k−1} < n\}_{1≤k≤⌈ \frac{n}{a} ⌉} are mutually exclusive events and their union covers the entire sample space, we have

∑_{1≤k≤⌈ \frac{n}{a} ⌉} r_{k} = 1.

Hence, the probability that Bob wins the game is

∑_{k=1}^{⌈ \frac{n}{a} ⌉} ℙ(S_{k} < n)ℙ(T_{k} ≥ n and T_{k−1} < n)

= ∑_{k=1}^{⌈ \frac{n}{a} ⌉} (1 − ∑_{i=1}^{k} r_{i}) r_{k} = ∑_{k=1}^{⌈ \frac{n}{a} ⌉} ( ∑_{i=k+1}^{⌈ \frac{n}{a} ⌉} r_{i}) r_{k}

= ∑_{1≤k<i≤⌈ \frac{n}{a} ⌉} r_{i}r_{k} = \frac{1}{2} ((∑_{k=1}^{⌈ \frac{n}{a} ⌉} r_{k})^{2} − ∑_{k=1}^{⌈ \frac{n}{a} ⌉} r_{k}^{2})

= \frac{1}{2} − \frac{1}{2} ∑_{k=1}^{⌈ \frac{n}{a} ⌉} r_{k}^{2}.

Second Proof of Theorem 3. Since Alice and Bob collect 1 or 2 chips randomly and indepen-

dently with equal probability, ℙ(X_{i} = 1) = ℙ(X_{i} = 2) = ℙ(Y_{i} = 1) = ℙ(Y_{i} = 2) = \frac{1}{2}. Let s_{k} = |{i : X_{i} = 2, 1 ≤ i ≤ k}|, and let t_{k} = |{i : Y_{i} = 2, 1 ≤ i ≤ k}|. Notice that s_{k} + k = S_{k} and t_{k} + k = T_{k}. Hence,

r_{k} = ℙ(S_{k} = n) + ℙ(S_{k−1} = n − 1 and X_{k} = 2)

= ℙ(s_{k} = n − k) + ℙ(s_{k−1} = n − k and X_{k} = 2)

= \frac{1}{2^{k}} \binom{k}{n − k} + \frac{1}{2^{k−1}} \binom{k − 1}{n − k} · \frac{1}{2}

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

Substituting this into the winning probability for Bob in Lemma 4 with a = 1 yields the desired result.

Next, we consider the three scenarios listed in Section 3. Let \binom{x}{y}_{int} = \binom{x}{y} if y is a

nonnegative integer, and \binom{x}{y}_{int} = 0 otherwise.

Theorem 5. Alice and Bob take turns to collect a or b chips randomly and independently with probabilities p and q = 1−p respectively, where a < b are positive integers and p ∈ [0, 1]. Then the probability that Bob collects at least n chips before Alice is

\frac{1}{2} − \frac{1}{2} · \begin{matrix}⌈ & \frac{n}{a} & ⌉ \\ ∑ \\ k=1 \end{matrix} (\binom{k}{\frac{n−ak}{b−a}}_{int}p^{\frac{bk−n}{b−a}} q^{\frac{n−ak}{b−a}} + ∑_{i=1}^{a−1} \binom{k − 1}{\frac{n−a(k−1)−i}{b−a}}_{int}p^{\frac{b(k−1)−n+i}{b−a}} q^{\frac{n−a(k−1)−i}{b−a}}

+ ∑_{i=a}^{b−1} \binom{k − 1}{\frac{n−a(k−1)−i}{b−a}}_{int}p^{\frac{b(k−1)−n+i}{b−a}} q^{\frac{n+b−ak−i}{b−a}} )^{2} .

Proof. In this case, ℙ(X_{i} = a) = ℙ(Y_{i} = a) = p and ℙ(X_{i} = b) = ℙ(Y_{i} = b) = 1 − p = q. Let s_{k} = |{i : X_{i} = b, 1 ≤ i ≤ k}|, and let t_{k} = |{i : Y_{i} = b, 1 ≤ i ≤ k}|. Notice that s_{k}(b − a) + ka = S_{k} and t_{k}(b − a) + ka = T_{k}. Hence,

r_{k} = ℙ(S_{k} = n) + ∑_{i=1}^{a−1} ℙ(S_{k−1} = n − i) + ∑_{i=a}^{b−1} ℙ(S_{k−1} = n − i and X_{k} = b)

= ℙ (s_{k} = \frac{n − ak}{b − a} ) + ∑_{i=1}^{a−1} ℙ (s_{k−1} = \frac{n − a(k − 1) − i}{b − a})

+ ∑_{i=a}^{b−1} ℙ (s_{k−1} = \frac{n − a(k − 1) − i}{b − a} and X_{k} = b)

= \binom{k}{\frac{n−ak}{b−a}}_{int}p^{\frac{bk−n}{b−a}} q^{\frac{n−ak}{b−a}} + ∑_{i=1}^{a−1} \binom{k − 1}{\frac{n−a(k−1)−i}{b−a}}_{int}p^{\frac{b(k−1)−n+i}{b−a}} q^{\frac{n−a(k−1)−i}{b−a}}

+ ∑_{i=a}^{b−1} \binom{k − 1}{\frac{n−a(k−1)−i}{b−a}}_{int}p^{\frac{b(k−1)−n+i}{b−a}} q^{\frac{n−a(k−1)−i}{b−a}} · q

= \binom{k}{\frac{n−ak}{b−a}}_{int}p^{\frac{bk−n}{b−a}} q^{\frac{n−ak}{b−a}} + ∑_{i=1}^{a−1} \binom{k − 1}{\frac{n−a(k−1)−i}{b−a}}_{int}p^{\frac{b(k−1)−n+i}{b−a}} q^{\frac{n−a(k−1)−i}{b−a}}

+ ∑_{i=a}^{b−1} \binom{k − 1}{\frac{n−a(k−1)−i}{b−a}}_{int}p^{\frac{b(k−1)−n+i}{b−a}} q^{\frac{n+b−ak−i}{b−a}} .

Substituting this into the winning probability for Bob in Lemma 4 yields the desired result.

In particular, if p = \frac{1}{2}, then we have the following corollary.

Corollary 6. If Alice and Bob take turns to collect a or b chips randomly and independently with equal probability, where a < b are positive integers, then the probability that Bob collects at least n chips before Alice is

\frac{1}{2} − \frac{1}{2} · \begin{matrix}⌈ & \frac{n}{a} & ⌉ \\ ∑ \\ k=1 \end{matrix} \frac{1}{4^{k}} (\binom{k}{\frac{n−ak}{b−a}}_{int} + 2 · ∑_{i=1}^{a−1} \binom{k − 1}{\frac{n−a(k−1)−i}{b−a}}_{int} + ∑_{i=a}^{b−1} \binom{k − 1}{\frac{n−a(k−1)−i}{b−a}}_{int})^{2} .

Proof. Substituting p = q = \frac{1}{2} into the probability found in Theorem 5, we have

\frac{1}{2} − \frac{1}{2} ·\begin{matrix}⌈ & \frac{n}{a} & ⌉ \\ ∑ \\ k=1 \end{matrix} (\binom{k}{\frac{n−ak}{b−a}}_{int} (\frac{1}{2})^{k} + ∑_{i=1}^{a−1} \binom{k − 1}{\frac{n−a(k−1)−i}{b−a}}_{int} (\frac{1}{2})^{k−1} + ∑_{i=a}^{b−1} \binom{k − 1}{\frac{n−a(k−1)−i}{b−a}}_{int} (\frac{1}{2})^{k})^{2} .

This yields our desired result.

Theorem 7. Alice and Bob take turns to collect a_{1}, a_{2}, …, or a_{m} chips randomly and independently with probabilities p_{1}, p_{2}, …, p_{m} respectively, where a_{1} < a_{2} < ⋯ < a_{m} are positive integers, p_{1}, p_{2}, …, p_{m} ∈ [0, 1], and p_{1} + p_{2} + ⋯ + p_{m} = 1. The probability that Bob collects at least n chips before Alice is

\frac{1}{2} − \frac{1}{2} · \begin{matrix}⌈ & \frac{n}{a_{1}} & ⌉ \\ ∑ \\ k=1 \end{matrix} ( ∑_{\begin{matrix}(s_{k1},s_{k2},...,s_{km})∈ℤ_{≥0}^{m}: \\ ∑_{g=1}^{m} s_{kg}a_{g}=n \\ ∑_{g=1}^{m} s_{kg}=k \end{matrix}} \binom{k}{s_{k1}, s_{k2}, …, s_{km}} ∏_{ℓ=1}^{m} p_{ℓ}^{s_{kℓ}}

+ ∑_{j=1}^{m} ∑_{i=a_{j−1}}^{a_{j}−1} ∑_{\begin{matrix}(s_{k1},s_{k2},...,s_{km})∈ℤ_{≥0}^{m}: \\ ∑_{g=1}^{m} s_{kg}a_{g}=n−i \\ ∑_{g=1}^{m} s_{kg}=k−1 \end{matrix}} \binom{k − 1}{s_{k1}, s_{k2}, …, s_{km}} ∏_{ℓ=1}^{m} p_{ℓ}^{s_{kℓ}} (∑_{α=j}^{m} p_{α}))^{2} .

Proof. In this case, ℙ(X_{i} = a_{j}) = ℙ(Y_{i} = a_{j}) = p_{j} for all j = 1, 2, …, m. Let s_{kj} = |{i : X_{i} = a_{j}, 1 ≤ i ≤ k}|, and let t_{kj} = |{i : Y_{i} = a_{j}, 1 ≤ i ≤ k}|, where j = 1, 2, …, m. Define a_{0} = 1. Notice that ∑_{j=1}^{m} s_{kj}a_{j} = S_{k} and ∑_{j=1}^{m} t_{kj}a_{j} = T_{k}. Hence,

r_{k} = ℙ(S_{k} = n) + ∑_{j=1}^{m} ∑_{i=a_{j−1}}^{a_{j}−1} ℙ(S_{k−1} = n − i and X_{k} = a_{j}, a_{j+1}, …, or a_{m})

= ∑_{\begin{matrix}(s_{k1},s_{k2},...,s_{km})∈ℤ_{≥0}^{m}: \\ ∑_{g=1}^{m} s_{kg}a_{g}=n \\ ∑_{g=1}^{m} s_{kg}=k \end{matrix}} \binom{k}{s_{k1}, s_{k2}, …, s_{km}} ∏_{ℓ=1}^{m} p_{ℓ}^{s_{kℓ}}

+ ∑_{j=1}^{m} ∑_{i=a_{j−1}}^{a_{j}−1} ∑_{\begin{matrix}(s_{k1},s_{k2},...,s_{km})∈ℤ_{≥0}^{m}: \\ ∑_{g=1}^{m} s_{kg}a_{g}=n−i \\ ∑_{g=1}^{m} s_{kg}=k−1 \end{matrix}} \binom{k − 1}{s_{k1}, s_{k2}, …, s_{km}} ∏_{ℓ=1}^{m} p_{ℓ}^{s_{kℓ}} (∑_{α=j}^{m} p_{α}) .

Substituting this into the winning probability for Bob in Lemma 4 with a = a_{1} yields the desired result.

5 Further observations and open questions

The numerical results given by the formulae in Theorems 3, 5, and 7 can also be computed by using recursive formulae and dynamic programming. This is particularly useful for the case in Theorem 7, since it significantly reduces the computational complexity.

Let position (i, j) denote the instance when Alice and Bob have already collected n − i and n − j chips respectively. In other words, Alice and Bob need to collect i and j chips respectively to win the game. Let

P_{i,j} = ℙ(Bob wins from position (i, j) | Alice starts).

Then ℙ(Alice wins from position (i, j) | Alice starts) = 1 − P_{i,j},

ℙ(Alice wins from position (i, j) | Bob starts) = P_{j,i},

and ℙ(Bob wins from position (i, j) | Bob starts) = 1 − P_{j,i}.

In each case, the winning probability for Bob is given by P_{n,n}.

Under the conditions given in Theorem 3, P_{i,j} satisfies the recurrence relation

P_{i,j} = \frac{1}{2}(1 − P_{j,i−1}) + \frac{1}{2}(1 − P_{j,i−2}) = 1 − \frac{1}{2}(P_{j,i−1} + P_{j,i−2}).

Under the conditions given in Theorem 5, P_{i,j} satisfies the recurrence relation

P_{i,j} = p(1 − P_{j,i−a}) + q(1 − P_{j,i−b}) = 1 − (pP_{j,i−a} + qP_{j,i−b}).

Finally, under the conditions given in Theorem 7, P_{i,j} satisfies the recurrence relation

P_{i,j} = ∑_{g=1}^{m} p_{g}(1 − P_{j,i−a_{g}}) = 1 − ∑_{g=1}^{m} p_{g}P_{j,i−a_{g}}.

In all three cases, the initial conditions for P_{i,j} are

1. P_{i,j} = 0 for all i, j ∈ ℤ such that i ≤ a and j ≥ 1;

2. P_{i,j} = 1 for all i, j ∈ ℤ such that i ≥ 1 and j ≤ 0,

where a is the least number of chips that Alice or Bob can collect in one move. Note that we do not need to specify P_{i,j} if i, j ≤ 0.

Another observation is related to the numerical approximation of p_{n} in the basic probabilistic take-away game. Recall from Theorem 3 that

p_{n} = \frac{1}{2} − \frac{1}{2} ∑_{k=1}^{n} \frac{1}{4^{k}} (\binom{k}{n − k} + \binom{k − 1}{n − k})^{2} .

The following nonrigorous arguments suggest that

p_{n} ∼ \frac{1}{2} − \sqrt{\frac{27}{32πn}}.  (3)

First,

\frac{1}{2} ∑_{k=1}^{n} \frac{1}{4^{k}} (\binom{k}{n − k} + \binom{k − 1}{n − k})^{2} = \frac{1}{2} ∑_{k=⌈ \frac{n}{2} ⌉}^{n} \frac{1}{4^{k}} (\frac{k!}{(n − k)!(2k − n)!} (1 + \frac{2k − n}{k}))^{2} .

By Stirling’s approximation, when n is large, this is approximately

\frac{1}{2} ∑_{k=⌈ \frac{n}{2} ⌉}^{n} \frac{1}{4^{k}} (\begin{matrix}\sqrt{2πk} & (\frac{k}{e}) & k \\ \sqrt{2π(n − k)} & (\frac{n−k}{e}) & n−k & \sqrt{2π(2k − n)} & (\frac{2k−n}{e}) & 2k−n \end{matrix} (\frac{3k − n}{k}))^{2} ,

which can be simplified to

\frac{1}{π} ∑_{k=⌈ \frac{n}{2} ⌉}^{n} \frac{k^{2k+2}}{2^{2k+2}} · \frac{1}{k(n − k)^{2(n−k)+1}(2k − n)^{2(2k−n)+1}} · \frac{(3k − n)^{2}}{k^{2}} ,

and can be transformed into

\frac{1}{π} ∑_{k=⌈ \frac{n}{2} ⌉}^{n} \frac{(3 − \frac{n}{k})^{2}}{k (\frac{2n}{k} − 2)^{2(n−k)+1} (4 − \frac{2n}{k})^{2(2k−n)+1}} .

We are going to approximate the last sum by turning it into an integral, with the discrete variable k replaced by a continuous variable u. The integral is

\frac{1}{π} ∫ n_{\frac{n}{2}} \frac{(3 − \frac{n}{u})^{2}}{u (\frac{2n}{u} − 2)^{2(n−u)+1} (4 − \frac{2n}{u})^{2(2u−n)+1}} du.

We can perform a substitution x = \frac{2n}{u}, which yields

\frac{1}{π} ∫_{4}^{2} \frac{(3 − \frac{x}{2})^{2}}{\frac{2n}{x}(x − 2)^{2(n− \frac{2n}{x})+1}(4 − x)^{2(2 \frac{2n}{x} −n)+1}} (−\frac{2n}{x^{2}}) dx.

This integral simplifies to

\frac{1}{4π} ∫_{2}^{4} \frac{(6 − x)^{2}}{x(x − 2)^{\frac{2n}{x} (x−2)+1}(4 − x)^{\frac{2n}{x} (4−x)+1}} dx,

and we further transform it into

\frac{1}{4π} ∫_{2}^{4} \frac{(6 − x)^{2}}{x(x − 2)(4 − x)} · e^{n· \frac{−2}{x} ln((x−2)^{x−2}(4−x)^{4−x})}dx.  (4)

Let

I(n) = ∫_{2}^{4} f(x)e^{nϕ(x)}dx,

where f(x) = \frac{(6 − x)^{2}}{x(x − 2)(4 − x)} and ϕ(x) = \frac{−2}{x} ln ((x − 2)^{x−2}(4 − x)^{4−x}). This is a Laplace

integral. Note that ϕ′(x) = \frac{2}{x^{2}} ln ((x − 2)^{−2}(4 − x)^{4}), whose only zero on the interval (2, 4)

is x = 3. Note also that f(3) = 3 ≠ 0 and ϕ′′(3) = −\frac{4}{3} < 0. Although I(n) is an improper

integral, since lim_{x→2} ϕ(x) = − ln 4 and lim_{x→4} ϕ(x) = −\frac{ln 4}{2}, the techniques on a Laplace integral [1, pp. 261–267] still apply. Hence, we have

I(n) ∼ \frac{\sqrt{2π}f(3)e^{nϕ(3)}}{\sqrt{−nϕ′′(c)}} = \frac{\sqrt{2π} · 3 · 1}{\sqrt{−n · (−\frac{4}{3})}} = \sqrt{\frac{27π}{2n}} .  (5)

Substituting (5) into (4) yields (3).

Finally, after studying various scenarios in Section 4, there are still some related open questions. One such question is the following.

Question 8. Find the winning probability for Bob if Alice and Bob take turns to lose 1 chip (i.e., collect −1 chip) or collect 2 chips randomly and independently with equal probability.

6 Acknowledgement

The authors would like to thank the referee for their extensive help and useful suggestions, especially on the dynamic programming and numerical approximation of the probabilities. We would also like to thank Brooks Emerick for his help with the approximation of the Laplace integral. The second author, Jiao Xu, was supported by the Carole and Ray Neag Undergraduate Research Fund at Kutztown University of Pennsylvania.

References

[1] Carl M. Bender and Steven A. Orszag, Advanced Mathematical Methods for Scientists and Engineers: Asymptotic Methods and Perturbation Theory, Springer, 1999.

[2] Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy, Winning Ways for Your Mathematical Plays, Academic Press, 1982.

[3] Charles L. Bouton, Nim, a game with a complete mathematical theory, Ann. of Math. (2) 3 (1901), 35–39.

[4] Allen J. Schwenk, Take-away games, Fibonacci Quart. 8 (1970), 225–234.

2010 Mathematics Subject Classification: Primary 97A20; Secondary 11Y55, 05A10. Keywords: take-away game, probability.

(Concerned with sequences \underline{A265919} and \underline{A265920}.)

Received May 11 2016; revised versions received May 30 2017; January 21 2018. Published in Journal of Integer Sequences, August 22 2018.

Return to Journal of Integer Sequences home page.