\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\renewcommand{\P}{\mathbb{P}}
\newcommand{\Z}{\mathbb{Z}}

\begin{center}
\vskip 1cm{\LARGE\bf 
A Probabilistic Take-Away Game\\
}
\vskip 1cm
\large
Tony W.\ H.\ Wong and Jiao Xu\\
Department of Mathematics\\
Kutztown University of Pennsylvania\\
Kutztown, PA 19530\\
USA\\
\href{mailto:wong@kutztown.edu}{\tt wong@kutztown.edu}\\
\href{mailto:jxu399@live.kutztown.edu}{\tt jxu399@live.kutztown.edu}\\
\end{center}

\vskip .2 in



\begin{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.\\
\end{abstract}







\section{Introduction}\label{intro}

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 \cite{schwenk}.

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 \cite{bcg} as well as Bouton \cite{bouton} 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 $\dfrac{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=\dfrac{1}{2}$ since the game seems to be fair to both Alice and Bob. With more thought, one may realize that $p_n\leq\dfrac{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 $\dfrac{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=\dfrac{1}{4}$. To study $p_n$ in general, we need some formal definitions.

Let $X_1,X_2,\dotsc,X_n,Y_1,Y_2,\dotsc,Y_n$ be independent identically distributed random variables such that $\P(X_i=1)=\P(X_i=2)=\P(Y_i=1)=\P(Y_i=2)=\dfrac{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=\dfrac{1}{4}$. The following calculations find $p_n$ when $n=3,4,5,6,$ and $7$.

When $n=3$,
\begin{align*}
p_3 &= \P\big((X_1,X_2)=(1,1)\big)\cdot\P\big((Y_1,Y_2)=(1,2),(2,1),\,\text{or }(2,2)\big)\\
&= \dfrac{1}{4}\cdot\dfrac{3}{4}=\dfrac{3}{16}.
\end{align*}

When $n=4$,
\begin{align*}
p_4&=\P\big((X_1,X_2)=(1,1),(1,2),\,\text{or }(2,1)\big)\cdot\P\big((Y_1,Y_2)=(2,2)\big)\\
&+\P\big((X_1,X_2,X_3)=(1,1,1)\big)\\
&\cdot\P\big((Y_1,Y_2,Y_3)=(1,1,2),(1,2,1),(2,1,1),(1,2,2),\text{ or }(2,1,2)\big)\\
&=\frac{3}{4}\cdot\frac{1}{4}+\frac{1}{8}\cdot\frac{5}{8}=\frac{17}{64}.
\end{align*}

When $n=5$,
\begin{align*}
p_5&=\P\big((X_1,X_2,X_3)=(1,1,1),(1,1,2),(1,2,1),\text{ or }(2,1,1)\big)\\
&\cdot\P\big((Y_1,Y_2,Y_3)=(1,2,2),(2,1,2),(2,2,1),\text{ or }(2,2,2)\big)\\
&+\P\big((X_1,X_2,X_3,X_4)=(1,1,1,1)\big)\\
&\cdot\P\big((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),\\
&\hspace{108pt}\text{or }(2,1,1,2)\big)\\
&=\frac{1}{2}\cdot\frac{1}{2}+\frac{1}{16}\cdot\frac{7}{16}=\frac{71}{256}.
\end{align*}

When $n=6$,
\begin{align*}
p_6&=\P\big((X_1,X_2,X_3)\neq(2,2,2)\big)\cdot\P\big((Y_1,Y_2,Y_3)=(2,2,2)\big)\\
&+\P\big((X_1,X_2,X_3,X_4)=(1,1,1,1),(1,1,1,2),(1,1,2,1),(1,2,1,1),\text{ or }(2,1,1,1)\big)\\
&\cdot\P\big((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),\\
&\hspace{108pt}(1,2,2,2),(2,1,2,2)\text{ or }(2,2,1,2)\big)\\
&+\P\big((X_1,X_2,X_3,X_4,X_5)=(1,1,1,1,1)\big)\\
&\cdot\P\big((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),\\
&\hspace{125pt}(1,1,1,2,2),(1,1,2,1,2),(1,2,1,1,2),\text{ or }(2,1,1,1,2)\big)\\
&=\frac{7}{8}\cdot\frac{1}{8}+\frac{5}{16}\cdot\frac{9}{16}+\frac{1}{32}\cdot\frac{9}{32}=\frac{301}{1024}.
\end{align*}

When $n=7$,
\begin{align*}
p_7&=\P\big((X_1,X_2,X_3,X_4)\neq(1,2,2,2),(2,1,2,2),(2,2,1,2),(2,2,2,1),\text{ and }(2,2,2,2)\big)\\
&\cdot\P\big((Y_1,Y_2,Y_3,Y_4)=(1,2,2,2),(2,1,2,2),(2,2,1,2),(2,2,2,1),\text{ or }(2,2,2,2)\big)\\
&+\P\big((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),\\
&\hspace{146pt}(1,2,1,1,1),\text{ or }(2,1,1,1,1)\big)\\
&\cdot\P\big((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),\\
&\hspace{125pt}(1,2,1,2,1),(1,2,2,1,1),(2,1,1,1,2),(2,1,1,2,1),\\
&\hspace{125pt}(2,1,2,1,1),(2,2,1,1,1),(1,1,2,2,2),(1,2,1,2,2),\\
&\hspace{125pt}(1,2,2,1,2),(2,1,1,2,2),(2,1,2,1,2),\text{ or }(2,2,1,1,2)\big)\\
&+\P\big((X_1,X_2,X_3,X_4,X_5,X_6)=(1,1,1,1,1,1)\big)\\
&\cdot\P\big((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),\\
&\hspace{141pt}(1,2,1,1,1,1),(2,1,1,1,1,1),(1,1,1,1,2,2),(1,1,1,2,1,2),\\
&\hspace{141pt}(1,1,2,1,1,2),(1,2,1,1,1,2),\text{ or }(2,1,1,1,1,2)\big)\\
&=\frac{11}{16}\cdot\frac{5}{16}+\frac{6}{32}\cdot\frac{16}{32}+\frac{1}{64}\cdot\frac{11}{64}=\frac{1275}{4096}.
\end{align*}

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}\approx64.4353$, which is absurd since $p_n\leq1$. 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 \ref{basic}, we present a complete solution for this basic probabilistic take-away game. In Section \ref{seq}, we discuss two integer sequences obtained from this result. In Section \ref{general}, we extend our calculations to some general versions of this probabilistic take-away game. Finally, in Section \ref{furtherandopen}, we discuss some numerical computations and approximations of the probabilities, as well as some open questions.







\section{Results for the basic version}\label{basic}

Let $S_k=\sum_{i=1}^kX_i$, and $T_k=\sum_{i=1}^kY_i$. It is clear that
\begin{equation}\label{pn1}
p_n=\sum_{k=1}^n\big(\P(S_k<n)\cdot\P(T_k\geq n\text{ and }T_{k-1}<n)\big).
\end{equation}

Let $s_k=|\{i:X_i=2,1\leq i\leq k\}|$, and let $t_k=|\{i:Y_i=2,1\leq i\leq k\}|$. Notice that $s_k+k=S_k$ and $t_k+k=T_k$. Hence, equation \eqref{pn1} becomes
$$p_n=\sum_{k=1}^n\big(\P(s_k<n-k)\cdot\P(t_k\geq n-k\text{ and }t_{k-1}<n-(k-1))\big).$$

Note that $\P(s_k<n-k)=\displaystyle\frac{1}{2^k}\sum_{i=0}^{n-k-1}\binom{k}{i}$. Let $h_k=\displaystyle\sum_{i=0}^{n-k-1}\binom{k}{i}$, so $\P(s_k<n-k)=\dfrac{h_k}{2^k}$. Then
\begin{align*}
\P(t_k\geq n-k\text{ and }t_{k-1}<n-(k-1))&=\P(t_k\geq n-k)-\P(t_{k-1}\geq n-(k-1))\\
&=\frac{1}{2^k}\sum_{i=n-k}^k\binom{k}{i}-\frac{1}{2^{k-1}}\sum_{i=n-(k-1)}^{k-1}\binom{k-1}{i}\\
&=1-\frac{h_k}{2^k}-\left(1-\frac{h_{k-1}}{2^{k-1}}\right)=\frac{2h_{k-1}-h_k}{2^k}.
\end{align*}

Hence, $p_n=\displaystyle\sum_{k=1}^n\frac{h_k(2h_{k-1}-h_k)}{4^k}$. If we rearrange the terms, we have
$$p_n=\frac{2h_1h_0}{4}+\sum_{k=2}^n\frac{-4h_{k-1}^2+2h_{k-1}h_k}{4^k}-\frac{h_n^2}{4^n}=1+\sum_{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
\begin{equation}\label{pnresult}
p_n=\frac{1}{2}-\frac{1}{2}\sum_{k=2}^n\frac{(2h_{k-1}-h_k)^2}{4^k}=\frac{1}{2}-\frac{1}{2}\sum_{k=1}^n\frac{(2h_{k-1}-h_k)^2}{4^k}.
\end{equation}

Finally, we have the following lemma.

\begin{lemma}\label{binomial}
Let $h_k=\displaystyle\sum_{i=0}^{n-k-1}\binom{k}{i}$. Then $2h_{k-1}-h_k=\dbinom{k}{n-k}+\dbinom{k-1}{n-k}$.
\end{lemma}

\begin{proof}
\begin{align*}
2h_{k-1}-h_k&=2\sum_{i=0}^{n-(k-1)-1}\binom{k-1}{i}-\sum_{i=0}^{n-k-1}\binom{k}{i}\\
&=2\sum_{i=0}^{n-k}\binom{k-1}{i}-\sum_{i=1}^{n-k-1}\left(\binom{k-1}{i}+\binom{k-1}{i-1}\right)-\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}.
\end{align*}
\end{proof}

\begin{remark}
The above proof of Lemma \ref{binomial} is purely algebraic. Here is an alternate proof that is more combinatorial.
\begin{align*}
\frac{2h_{k-1}-h_k}{2^k}&=\P(t_k\geq n-k\text{ and }t_{k-1}<n-(k-1))\\
&=\P(T_k\geq n\text{ and }T_{k-1}<n)\\
&=\P\big(T_k=n\text{ or }(T_{k-1}=n-1\text{ and }X_k=2)\big)\\
&=\P\big(t_k=n-k\text{ or }(t_{k-1}=n-k\text{ and }X_k=2)\big)\\
&=\frac{\binom{k}{n-k}}{2^k}+\frac{\binom{k-1}{n-k}}{2^{k-1}}\cdot\frac{1}{2}=\frac{\binom{k}{n-k}+\binom{k-1}{n-k}}{2^k},
\end{align*}
which yields our desired result.
\end{remark}

Applying Lemma \ref{binomial} to equation \eqref{pnresult}, we obtain the following theorem.

\begin{theorem}\label{case0}
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=\displaystyle\frac{1}{2}-\frac{1}{2}\sum_{k=1}^n\frac{1}{4^k}\left(\binom{k}{n-k}+\binom{k-1}{n-k}\right)^2.$$
\end{theorem}

It is worth noting that the summation can start from $k=\left\lceil\dfrac{n}{2}\right\rceil$, since all the summands are zero when $k<\dfrac{n}{2}$. However, we decide to start the summation from $k=1$ since it is more elegant.







\section{Observations on the sequences}\label{seq}

Let $p_n=\dfrac{c_n}{d_n}$, where $c_n$ and $d_n$ are nonnegative integers that are relatively prime. Notice that $4^{n-1}p_n=\displaystyle\frac{4^{n-1}}{2}-\frac{1}{2}\sum_{k=1}^n4^{n-k-1}\left(\binom{k}{n-k}+\binom{k-1}{n-k}\right)^2$ is an odd integer, since
\begin{align*}
&\,\displaystyle\frac{1}{2}\sum_{k=n-1}^n4^{n-k-1}\left(\binom{k}{n-k}+\binom{k-1}{n-k}\right)^2\\
&=\,\frac{1}{2}\left(\left(\binom{n-1}{1}+\binom{n-2}{1}\right)^2+4^{-1}\left(\binom{n}{0}+\binom{n-1}{0}\right)^2\right)\\
&=\,\frac{1}{2}\big((2n-3)^2+1\big)=2n^2-6n+5
\end{align*}
is an odd integer, and all other summands are even. In other words, $d_n=4^{n-1}$, and $c_n=\displaystyle\frac{1}{8}\left(4^n-\sum_{k=1}^n4^{n-k}\left(\binom{k}{n-k}+\binom{k-1}{n-k}\right)^2\right)$. As mentioned in Section \ref{intro}, 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 \seqnum{A265919}. The integer sequence formed by the numerators of the winning probabilities for Alice is listed as \seqnum{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 $\dfrac{1}{2}$ is slow. For example, $p_{100}\approx44.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}\approx48.36\%$, $p_{10000}\approx49.48\%$, and $p_{100000}\approx49.84\%$. In other words, the fact that Bob starts second puts him in a significantly disadvantageous position, which is counter-intuitive.

Theorem \ref{case0} 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?

\begin{enumerate}
\item Alice and Bob take turns to collect $a$ or $b$ chips randomly and independently with equal probability, where $a<b$ are positive integers.
\item 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\in[0,1]$.
\item Alice and Bob take turns to collect $a_1$, $a_2$, $\dotsc$, or $a_m$ chips randomly and independently with probabilities $p_1,p_2,\dotsc,p_m$ respectively, where $a_1<a_2<\dotsb<a_m$ are positive integers, $p_1,p_2,\dotsc,p_m\in[0,1]$, and $p_1+p_2+\dotsb+p_m=1$.
\end{enumerate}







\section{Results for general cases}\label{general}

Before we proceed, let us introduce a different proof of Theorem \ref{case0}. This proof is due to Taoye Zhang (personal communication, October 2015). Let $X_1,X_2,\dotsc,X_n,Y_1,Y_2,\dotsc,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=\sum_{i=1}^kX_i$, and $T_k=\sum_{i=1}^kY_i$. Let $r_k=\P(S_k\geq n\text{ and }S_{k-1}<n)$, and let $a$ be the minimum positive integer such that $\P(X_1=a)>0$.

\begin{lemma}\label{rk}
The probability that Bob wins the game is $\displaystyle\frac{1}{2}-\frac{1}{2}\sum_{k=1}^{\lceil\frac{n}{a}\rceil}r_k^2$.
\end{lemma}

\begin{proof}
Since
$\{S_k\geq n\text{ and }S_{k-1}<n\}_{1 \leq k \leq {\lceil\frac{n}{a}\rceil}}$ are mutually exclusive
events and their union covers the entire sample space, we have
$$\sum_{1 \leq k \leq {\lceil\frac{n}{a}\rceil}} r_k = 1 .$$
Hence, the probability that Bob wins the game is
\begin{align*}
&\,\sum_{k=1}^{\lceil\frac{n}{a}\rceil}\P(S_k<n)\P(T_k\geq n\text{ and }T_{k-1}<n)\\
&=\,\sum_{k=1}^{\lceil\frac{n}{a}\rceil}\left(1-\sum_{i=1}^kr_i\right)r_k=\sum_{k=1}^{\lceil\frac{n}{a}\rceil}\left(\sum_{i=k+1}^{\lceil\frac{n}{a}\rceil}r_i\right)r_k\\
&=\,\sum_{1\leq k<i\leq\lceil\frac{n}{a}\rceil}r_ir_k=\frac{1}{2}\left(\left(\sum_{k=1}^{\lceil\frac{n}{a}\rceil}r_k\right)^2-\sum_{k=1}^{\lceil\frac{n}{a}\rceil}r_k^2\right)\\
&=\,\frac{1}{2}-\frac{1}{2}\sum_{k=1}^{\lceil\frac{n}{a}\rceil}r_k^2.
\end{align*}
\end{proof}

\begin{proof}[Second Proof of Theorem $\ref{case0}$]
Since Alice and Bob collect $1$ or $2$ chips randomly and independently with equal probability, $\P(X_i=1)=\P(X_i=2)=\P(Y_i=1)=\P(Y_i=2)=\dfrac{1}{2}$. Let $s_k=|\{i:X_i=2,1\leq i\leq k\}|$, and let $t_k=|\{i:Y_i=2,1\leq i\leq k\}|$. Notice that $s_k+k=S_k$ and $t_k+k=T_k$. Hence,
\begin{align*}
r_k&=\P(S_k=n)+\P(S_{k-1}=n-1\text{ and }X_k=2)\\
&=\P(s_k=n-k)+\P(s_{k-1}=n-k\text{ and }X_k=2)\\
&=\frac{1}{2^k}\binom{k}{n-k}+\frac{1}{2^{k-1}}\binom{k-1}{n-k}\cdot\frac{1}{2}\\
&=\frac{1}{2^k}\left(\binom{k}{n-k}+\binom{k-1}{n-k}\right).
\end{align*}

Substituting this into the winning probability for Bob in Lemma \ref{rk} with $a=1$ yields the desired result.
\end{proof}

Next, we consider the three scenarios listed in Section \ref{seq}. Let $\dbinom{x}{y}_{int}=\dbinom{x}{y}$ if $y$ is a nonnegative integer, and $\dbinom{x}{y}_{int}=0$ otherwise.

\begin{theorem}\label{abpq}
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\in[0,1]$. Then the probability that Bob collects at least $n$ chips before Alice is
\begin{align*}
&\frac{1}{2}-\frac{1}{2}\cdot\sum_{k=1}^{\left\lceil\frac{n}{a}\right\rceil}\left(\binom{k}{\frac{n-ak}{b-a}}_{int}p^{\frac{bk-n}{b-a}}q^{\frac{n-ak}{b-a}}+\sum_{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}}\right.\\
&\hspace{160pt}\left.+\sum_{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}}\right)^2.
\end{align*}
\end{theorem}

\begin{proof}
In this case, $\P(X_i=a)=\P(Y_i=a)=p$ and $\P(X_i=b)=\P(Y_i=b)=1-p=q$. Let $s_k=|\{i:X_i=b,1\leq i\leq k\}|$, and let $t_k=|\{i:Y_i=b,1\leq i\leq k\}|$. Notice that $s_k(b-a)+ka=S_k$ and $t_k(b-a)+ka=T_k$. Hence,
\begin{align*}
r_k&=\P(S_k=n)+\sum_{i=1}^{a-1}\P(S_{k-1}=n-i)+\sum_{i=a}^{b-1}\P(S_{k-1}=n-i\text{ and }X_k=b)\\
&=\P\left(s_k=\frac{n-ak}{b-a}\right)+\sum_{i=1}^{a-1}\P\left(s_{k-1}=\frac{n-a(k-1)-i}{b-a}\right)\\
&\hspace{13pt}+\sum_{i=a}^{b-1}\P\left(s_{k-1}=\frac{n-a(k-1)-i}{b-a}\text{ and }X_k=b\right)\\
&=\binom{k}{\frac{n-ak}{b-a}}_{int}p^{\frac{bk-n}{b-a}}q^{\frac{n-ak}{b-a}}+\sum_{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}}\\
&\hspace{13pt}+\sum_{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}}\cdot q\\
&=\binom{k}{\frac{n-ak}{b-a}}_{int}p^{\frac{bk-n}{b-a}}q^{\frac{n-ak}{b-a}}+\sum_{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}}\\
&\hspace{13pt}+\sum_{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}}.
\end{align*}

Substituting this into the winning probability for Bob in Lemma \ref{rk} yields the desired result.
\end{proof}

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

\begin{corollary}\label{ab1/2}
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}\cdot\sum_{k=1}^{\left\lceil\frac{n}{a}\right\rceil}\frac{1}{4^k}\left(\binom{k}{\frac{n-ak}{b-a}}_{int}+2\cdot \sum_{i=1}^{a-1}\binom{k-1}{\frac{n-a(k-1)-i}{b-a}}_{int}+\sum_{i=a}^{b-1}\binom{k-1}{\frac{n-a(k-1)-i}{b-a}}_{int}\right)^2.$$
\end{corollary}

\begin{proof}
Substituting $p=q=\dfrac{1}{2}$ into the probability found in Theorem \ref{abpq}, we have
$$\frac{1}{2}-\frac{1}{2}\cdot\sum_{k=1}^{\left\lceil\frac{n}{a}\right\rceil}\left(\binom{k}{\frac{n-ak}{b-a}}_{int}\left(\frac{1}{2}\right)^k+\sum_{i=1}^{a-1}\binom{k-1}{\frac{n-a(k-1)-i}{b-a}}_{int}\left(\frac{1}{2}\right)^{k-1}+\sum_{i=a}^{b-1}\binom{k-1}{\frac{n-a(k-1)-i}{b-a}}_{int}\left(\frac{1}{2}\right)^k\right)^2.$$
This yields our desired result.
\end{proof}

\begin{theorem}\label{a1an}
Alice and Bob take turns to collect $a_1$, $a_2$, $\dotsc$, or $a_m$ chips randomly and independently with probabilities $p_1,p_2,\dotsc,p_m$ respectively, where $a_1<a_2<\dotsb<a_m$ are positive integers, $p_1,p_2,\dotsc,p_m\in[0,1]$, and $p_1+p_2+\dotsb+p_m=1$. The probability that Bob collects at least $n$ chips before Alice is
\begin{align*}
&\frac{1}{2}-\frac{1}{2}\cdot\sum_{k=1}^{\left\lceil\frac{n}{a_1}\right\rceil}\left(\sum_{\substack{(s_{k1},s_{k2},\dotsc,s_{km})\in\Z_{\geq0}^m:\\\sum_{g=1}^ms_{kg}a_g=n\\\sum_{g=1}^ms_{kg}=k}}\binom{k}{s_{k1},s_{k2},\dotsc,s_{km}}\prod_{\ell=1}^mp_\ell^{s_{k\ell}}\right.\\
&\hspace{13pt}\left.+\sum_{j=1}^m\sum_{i=a_{j-1}}^{a_j-1}\sum_{\substack{(s_{k1},s_{k2},\dotsc,s_{km})\in\Z_{\geq0}^m:\\\sum_{g=1}^ms_{kg}a_g=n-i\\\sum_{g=1}^ms_{kg}=k-1}}\binom{k-1}{s_{k1},s_{k2},\dotsc,s_{km}}\prod_{\ell=1}^mp_\ell^{s_{k\ell}}\left(\sum_{\alpha=j}^mp_\alpha\right)\right)^2.
\end{align*}
\end{theorem}

\begin{proof}
In this case, $\P(X_i=a_j)=\P(Y_i=a_j)=p_j$ for all $j=1,2,\dotsc,m$. Let $s_{kj}=|\{i:X_i=a_j,1\leq i\leq k\}|$, and let $t_{kj}=|\{i:Y_i=a_j,1\leq i\leq k\}|$, where $j=1,2,\dotsc,m$. Define $a_0=1$. Notice that $\sum_{j=1}^ms_{kj}a_j=S_k$ and $\sum_{j=1}^mt_{kj}a_j=T_k$. Hence,
\begin{align*}
r_k&=\P(S_k=n)+\sum_{j=1}^m\sum_{i=a_{j-1}}^{a_j-1}\P(S_{k-1}=n-i\text{ and }X_k=a_j,a_{j+1},\dotsc,\,\text{or }a_m)\\
&=\sum_{\substack{(s_{k1},s_{k2},\dotsc,s_{km})\in\Z_{\geq0}^m:\\\sum_{g=1}^ms_{kg}a_g=n\\\sum_{g=1}^ms_{kg}=k}}\binom{k}{s_{k1},s_{k2},\dotsc,s_{km}}\prod_{\ell=1}^mp_\ell^{s_{k\ell}}\\
&\hspace{13pt}+\sum_{j=1}^m\sum_{i=a_{j-1}}^{a_j-1}\sum_{\substack{(s_{k1},s_{k2},\dotsc,s_{km})\in\Z_{\geq0}^m:\\\sum_{g=1}^ms_{kg}a_g=n-i\\\sum_{g=1}^ms_{kg}=k-1}}\binom{k-1}{s_{k1},s_{k2},\dotsc,s_{km}}\prod_{\ell=1}^mp_\ell^{s_{k\ell}}\left(\sum_{\alpha=j}^mp_\alpha\right).
\end{align*}

Substituting this into the winning probability for Bob in Lemma \ref{rk} with $a=a_1$ yields the desired result.
\end{proof}







\section{Further observations and open questions}\label{furtherandopen}

The numerical results given by the formulae in Theorems \ref{case0}, \ref{abpq}, and \ref{a1an} can also be computed by using recursive formulae and dynamic programming. This is particularly useful for the case in Theorem \ref{a1an}, 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}=\P(\text{Bob wins from position $(i,j)$ $|$ Alice starts}).$$
Then
$$\P(\text{Alice wins from position $(i,j)$ $|$ Alice starts})=1-P_{i,j},$$
$$\P(\text{Alice wins from position $(i,j)$ $|$ Bob starts})=P_{j,i},$$
and
$$\P(\text{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 \ref{case0}, $P_{i,j}$ satisfies the recurrence relation
$$P_{i,j}=\dfrac{1}{2}(1-P_{j,i-1})+\dfrac{1}{2}(1-P_{j,i-2})=1-\dfrac{1}{2}(P_{j,i-1}+P_{j,i-2}).$$
Under the conditions given in Theorem \ref{abpq}, $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 \ref{a1an}, $P_{i,j}$ satisfies the recurrence relation
$$P_{i,j}=\sum_{g=1}^mp_g(1-P_{j,i-a_g})=1-\sum_{g=1}^mp_gP_{j,i-a_g}.$$
In all three cases, the initial conditions for $P_{i,j}$ are
\begin{enumerate}
\item $P_{i,j}=0$ for all $i,j\in\Z$ such that $i\leq a$ and $j\geq1$;
\item $P_{i,j}=1$ for all $i,j\in\Z$ such that $i\geq1$ and $j\leq0$,
\end{enumerate}
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\leq0$.

Another observation is related to the numerical approximation of $p_n$ in the basic probabilistic take-away game. Recall from Theorem \ref{case0} that
$$p_n=\frac{1}{2}-\frac{1}{2}\sum_{k=1}^n\frac{1}{4^k}\left(\binom{k}{n-k}+\binom{k-1}{n-k}\right)^2.$$
The following nonrigorous arguments suggest that
\begin{equation}\label{pnapprox}
p_n\sim\frac{1}{2}-\sqrt{\frac{27}{32\pi n}}.
\end{equation}

First,
$$\frac{1}{2}\sum_{k=1}^n\frac{1}{4^k}\left(\binom{k}{n-k}+\binom{k-1}{n-k}\right)^2=\frac{1}{2}\sum_{k=\lceil\frac{n}{2}\rceil}^n\frac{1}{4^k}\left(\frac{k!}{(n-k)!(2k-n)!}\left(1+\frac{2k-n}{k}\right)\right)^2.$$
By Stirling's approximation, when $n$ is large, this is approximately
$$\frac{1}{2}\sum_{k=\lceil\frac{n}{2}\rceil}^n\frac{1}{4^k}\left(\frac{\sqrt{2\pi k}\left(\frac{k}{e}\right)^k}{\sqrt{2\pi(n-k)}\left(\frac{n-k}{e}\right)^{n-k}\sqrt{2\pi(2k-n)}\left(\frac{2k-n}{e}\right)^{2k-n}}\left(\frac{3k-n}{k}\right)\right)^2,$$
which can be simplified to
$$\frac{1}{\pi}\sum_{k=\lceil\frac{n}{2}\rceil}^n\frac{k^{2k+2}}{2^{2k+2}}\cdot\frac{1}{k(n-k)^{2(n-k)+1}(2k-n)^{2(2k-n)+1}}\cdot\frac{(3k-n)^2}{k^2},$$
and can be transformed into
$$\frac{1}{\pi}\sum_{k=\lceil\frac{n}{2}\rceil}^n\frac{\left(3-\frac{n}{k}\right)^2}{k\left(\frac{2n}{k}-2\right)^{2(n-k)+1}\left(4-\frac{2n}{k}\right)^{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}{\pi}\int_{\frac{n}{2}}^n\frac{\left(3-\frac{n}{u}\right)^2}{u\left(\frac{2n}{u}-2\right)^{2(n-u)+1}\left(4-\frac{2n}{u}\right)^{2(2u-n)+1}}du.$$
We can perform a substitution $x=\dfrac{2n}{u}$, which yields
$$\frac{1}{\pi}\int_4^2\frac{\left(3-\frac{x}{2}\right)^2}{\frac{2n}{x}(x-2)^{2(n-\frac{2n}{x})+1}(4-x)^{2\left(2\frac{2n}{x}-n\right)+1}}\left(-\frac{2n}{x^2}\right)dx.$$
This integral simplifies to
$$\frac{1}{4\pi}\int_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
\begin{equation}\label{integral}
\frac{1}{4\pi}\int_2^4\frac{(6-x)^2}{x(x-2)(4-x)}\cdot e^{n\cdot\frac{-2}{x}\ln\left((x-2)^{x-2}(4-x)^{4-x}\right)}dx.
\end{equation}

Let
$$I(n)=\int_2^4f(x)e^{n\phi(x)}dx,$$
where $f(x)=\dfrac{(6-x)^2}{x(x-2)(4-x)}$ and $\phi(x)=\dfrac{-2}{x}\ln\left((x-2)^{x-2}(4-x)^{4-x}\right)$. This is a Laplace integral. Note that $\phi'(x)=\dfrac{2}{x^2}\ln\left((x-2)^{-2}(4-x)^4\right)$, whose only zero on the interval $(2,4)$ is $x=3$. Note also that $f(3)=3\neq0$ and $\phi''(3)=-\dfrac{4}{3}<0$. Although $I(n)$ is an improper integral, since $\displaystyle\lim_{x\to2}\phi(x)=-\ln4$ and $\displaystyle\lim_{x\to4}\phi(x)=-\dfrac{\ln4}{2}$, the techniques on a Laplace integral \cite[pp.~261--267]{bo} still apply. Hence, we have
\begin{equation}\label{In}
I(n)\sim\frac{\sqrt{2\pi}f(3)e^{n\phi(3)}}{\sqrt{-n\phi''(c)}}=\frac{\sqrt{2\pi}\cdot3\cdot1}{\sqrt{-n\cdot\left(-\frac{4}{3}\right)}}=\sqrt{\frac{27\pi}{2n}}.
\end{equation}
Substituting \eqref{In} into \eqref{integral} yields \eqref{pnapprox}.

Finally, after studying various scenarios in Section \ref{general}, there are still some related open questions. One such question is the following.

\begin{question}
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.
\end{question}




\section{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.







\begin{thebibliography}{99}

\bibitem{bo}
Carl M.\ Bender and Steven A.\ Orszag, \textit{Advanced Mathematical
Methods for Scientists and Engineers: Asymptotic Methods and
Perturbation Theory}, Springer, 1999.

\bibitem{bcg}
Elwyn R.\ Berlekamp, John H.\ Conway, and Richard K.\ Guy, \textit{Winning Ways for Your Mathematical Plays}, Academic Press, 1982.

\bibitem{bouton}
Charles L.\ Bouton, Nim, a game with a complete mathematical theory, \textit{Ann.\ of Math.\ (2)} \textbf{3} (1901), 35--39.

\bibitem{schwenk}
Allen J.\ Schwenk, Take-away games, \textit{Fibonacci Quart.\/} \textbf{8} (1970), 225--234.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: Primary 97A20; Secondary 11Y55, 05A10.

\noindent \emph{Keywords: } take-away game, probability.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  May 11 2016;
revised versions received  May 30 2017; January 21 2018.
Published in {\it Journal of Integer Sequences}, August 22 2018.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}