\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\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}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\underline{#1}}}
\def\modd#1 #2{#1\ \mbox{\rm (mod}\ #2\mbox{\rm )}}
\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}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf
A Probabilistic Two-Pile Game}
\vskip 1cm
\large
Ho-Hon Leung\\
Department of Mathematical Sciences \\
United Arab Emirates University \\
Al Ain, 15551\\
United Arab Emirates\\
\href{mailto:hohon.leung@uaeu.ac.ae}{\tt hohon.leung@uaeu.ac.ae}\\
\ \\
Thotsaporn ``Aek'' Thanatipanonda\\
Science Division\\
Mahidol University International College\\
Nakornpathom\\
Thailand \\
\href{mailto:thotsaporn@gmail.com}{\tt thotsaporn@gmail.com}\\
\end{center}
\vskip .2 in
\begin{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.
\end{abstract}
\section{Introduction} \label{section1}
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{\'e}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'', {\it Winning Ways for
Your Mathematical Plays}, written
by Berlekamp, Conway, and Guy \cite{WW}
is a good reference for a mathematical introduction to these games.
Recently, Wong and Xu \cite{WX} 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 {\it 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^{\text{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
\begin{align} p_n = \sum_{k=1}^{\infty} \label{equation0}
P( \mbox{A does not win on his } k^{\text{th}} \mbox{ move}) \cdot
P( \mbox{B wins on his } k^{\text{th}} \mbox{ move}). \end{align}
\subsection{Important notation}
\begin{itemize}
\item $p_n$ = the probability of the second player winning the game by collecting $n$ chips first.
\item $q(n,k)$ = the probability that a player does not win the game on his $k^{\text{th}}$ move, i.e., he never collects $n$ chips on or before his $k^{\text{th}}$ move.
\item $r(n,k)$ = the probability that a player collects $n$ chips for the first time on his $k^{\text{th}}$ move.
\end{itemize}
The equation (\ref{equation0}) can be written as follows:
\begin{align} \label{M1}
p_n = \sum_{k=1}^{\infty} q(n,k) \cdot r(n,k)
\end{align}
where $q(n,k) = P(S_j < n\mbox{ for all }j=0,1,\dots,k)$
and $r(n,k) = P(S_k \geq n \mbox{ and } S_{j} < n \mbox{ for all }j=0,1,\dots, k-1) $.
A nice connection between the probabilities
$q(n,k)$ and $r(n,k)$ is as follows:
\begin{lemma} \label{claim1}
For any positive integer $n$,
\[ r(n,k) = q(n,k-1)-q(n,k), \;\ \;\ k\geq 1. \]
\end{lemma}
\begin{proof}
We prove the lemma by the following computation:
\begin{align*}
r(n,k) &= P(S_k \geq n \mbox{ and } S_{j} < n,\mbox{ for all }j=0,1,\dots,k-1) \\
&= P(S_k \geq n) - P(S_{k-1} \geq n) \\
&= (1-q(n,k))-(1-q(n,k-1)) \\
&= q(n,k-1)-q(n,k).
\end{align*}
\end{proof}
\begin{remark}\label{remark1} By Lemma \ref{claim1} and the fact that
$q(n,0)=1$ for all $n \geq 1$,
we write $q(n,k)$ where $ k \geq 1$, by
\begin{equation} \label{M2}
q(n,k) = 1- \sum_{j=1}^k r(n,j).
\end{equation}
\end{remark}
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).
\begin{lemma} \label{claim2}
Let $n$ be a fixed positive integer.
If $\displaystyle \lim_{k \to \infty}q(n,k) =0$
(i.e., $a+b \geq 0$; otherwise there is a positive
chance that the game will not end), then
\[\displaystyle \sum_{k=1}^{\infty} \big(q(n,k-1)+q(n,k)\big) \cdot r(n,k) = 1.\]
\end{lemma}
\begin{proof}
We prove the lemma by the following computation:
\begin{align*}
& \sum_{k=1}^{\infty} \big(q(n,k-1)+q(n,k)\big) \cdot r(n,k) \\
&= \sum_{k=1}^{\infty} \big(q(n,k-1)+q(n,k)\big) \cdot \big(q(n,k-1)-q(n,k)\big)
\;\ \;\ \mbox{ from Lemma \ref{claim1}} \\
&= \sum_{k=1}^{\infty} \big(q(n,k-1)^2-q(n,k)^2\big) \\
&= q(n,0)^2- \lim_{k \to \infty}q(n,k)^2 =1.
\end{align*}
\end{proof}
\begin{remark}Alternatively, Lemma \ref{claim2} can also be proven combinatorially as follows:
\begin{align*}
1 &= \mbox{$P$( first player wins) + $P$( second player wins) + $P$( nobody wins) }\\
&= \sum_{k=1}^{\infty} r(n,k)q(n,k-1) + \sum_{k=1}^{\infty} q(n,k)r(n,k)
+ \lim_{k \to \infty}q(n,k)^2.
\end{align*}
\end{remark}
In Theorem \ref{theorem1} below, we write the probability $p_n$ in terms of the probabilities $r(n,k)$ only.
\begin{theorem}\label{theorem1}
If $\displaystyle \lim_{k \to \infty}q(n,k)=0$, then
$\displaystyle p_n = \dfrac{1}{2}-\dfrac{1}{2}\sum_{k=1}^{\infty} r(n,k)^2$.
\end{theorem}
\begin{proof}
By definition, \[\displaystyle p_n = \sum_{k=1}^{\infty} q(n,k) \cdot r(n,k). \]
On the other hand, based on Lemma \ref{claim2}, we have \[\displaystyle
p_n = 1-\sum_{k=1}^{\infty} q(n,k-1) \cdot r(n,k). \]
By combining the two equations above, we obtain
\[ p_n = \dfrac{1}{2}-\dfrac{1}{2}\sum_{k=1}^{\infty} \big(q(n,k-1)-q(n,k)\big) \cdot r(n,k). \]
Then the result follows by applying Lemma \ref{claim1}.
\end{proof}
In order to find $p_n$, by Theorem \ref{theorem1}, 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 \cite[Theorem 3]{WX} obtained the following expression for the probability $r(n,k)$:
\[ r(n,k) = \dfrac{1}{2^k}\Bigg(\binom{k}{n-k}+\binom{k-1}{n-k} \Bigg).\]
Although it can be shown that the expression $\displaystyle \sum_{k=1}^{\infty} 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 \cite{AB}),
nevertheless, an approximation for it was computed
by Wong and Xu \cite[p.~12]{WX}. In particular, they showed that
\[ \displaystyle \sum_{k=1}^{\infty} r(n,k)^2 \sim\sqrt{\dfrac{27}{8\pi 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 \texttt{Piles}
which can be found on the second author's website: \href{http://www.thotsaporn.com}{www.thotsaporn.com}.
\section{The case $\{a,b\}=\{-1,1\}$} \label{section2}
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$.
\subsection{The winning probability for the first non-trivial case: $n=1$} \label{section2.1}
In this subsection, we simplify our notation slightly. The probabilities $q(1,k)$ and $r(1,k)$ defined in Section \ref{section1} 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^{\text{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\geq 1$, we have
\[C(2m-1) = 0\]and
\[C(2m)= \dfrac{\binom{2m}{m}}{m+1}.\]
The probability that the second player collects one chip for the first time on his $k^{\text{th}}$ move is
\[r(k) = \dfrac{C(k-1)}{2^k}\]because the player has
no chip on his $(k-1)^{\text{th}}$ move; and on his next move he is required to collect one chip to win the game.
Hence, for $m\geq 1$, we have
\[r(2m)=0\]and
\[r(2m-1) = \dfrac{(2m-2)!}{m!(m-1)!}\cdot \dfrac{2}{4^m}.\]
We therefore applied Theorem \ref{theorem1} 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
$\displaystyle \lim_{k \to \infty}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 \eqref{M2}, we needed to show that
\begin{align} \label{equation100} \sum_{k=1}^{\infty} r(k) &= 1. \end{align}
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 \cite{AB}.
This algorithm has been implemented
in all major symbolic computation programs
such as Maple and Mathematica. For example, when one types in
\[\texttt{ sum( (2*m-2)!/m!/(m-1)!*2/4\string^m, m=1..M);}\]in Maple, it will then return the expression $1-\dfrac{(2M)!}{M!M!4^M}$. By an application of the Stirling
formula: $n! \approx \sqrt{2\pi n} \left(\dfrac{n}{e}\right)^n$, we note that \[1-\dfrac{(2M)!}{M!M!4^M} \rightarrow 1 \mbox{ as }M\rightarrow \infty. \]Hence, the equation (\ref{equation100}) is true.
We are ready to find $p_1$ by Theorem \ref{theorem1}. To evaluate
\[ \sum_{k=1}^{\infty} r(k)^2, \]
in Maple, we type
\[\texttt{ sum( ( (2*m-2)!/m!/(m-1)!*2/4\string^m )\string^2, m=1..infinity);}\]in Maple, it will then return $\dfrac{4}{\pi}-1$. By Theorem \ref{theorem1},
\[ p_1 = \dfrac{1}{2}-\dfrac{1}{2}\left(\dfrac{4}{\pi}-1\right)
\approx 0.3633802277. \]
Hence, we easily obtained the value of $p_1$ by applying Theorem \ref{theorem1} and the summation tools in Maple.
\subsection{ The winning probabilities for the cases $n\geq 2$} \label{section2.2}
Analogously, let $C(n,k)$ be the number of ways for a player to
have $n-1$ chips on his $k^{\text{th}}$ move without ever collecting $n$ chips.
\begin{lemma} \label{lemma2}
For $n \geq 0, \;\ k \geq 1$ such that $n-k \equiv \modd{0} {2}$, we have\[C(n,k) = 0.\]
Otherwise, for $s \geq 0$, we have
\begin{align*}
C(2s+1,2m) &= \dfrac{2s+1}{m+s+1}\binom{2m}{m-s}
, \;\ \;\ \mbox{for } m\geq 0, \\
C(2s,2m-1) &= \dfrac{s}{m}\binom{2m}{m-s}
, \;\ \;\ \mbox{for } m\geq 1.
\end{align*}
\end{lemma}
\begin{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 \geq 1, \;\ k \geq 1. \]
If the first move is 1, then the number of ways for a player to have $n-1$ chips on his $k^{\text{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
\begin{equation} \label{M3}
C(n,k) = C(n-1,k+1) - C(n-2,k), \;\ n \geq 2, \;\ k \geq 0.
\end{equation}
Then, the results follow by induction on $n$
where base cases are given by \[C(0,k) =0, \quad C(1,2m-1)=0 \mbox{ and }
C(1,2m)= \dfrac{\binom{2m}{m}}{m+1}.\]
It is also important to note that $C(n,0)=0$ for all $n \geq 0$ except $C(1,0) =1$.
\end{proof}
We proceed in the same manner as in Section \ref{section2.1}. The following relation between the numbers $r(n,k)$ and $C(n,k-1)$ is true for $n\geq 0$: \begin{align} \label{equation101} r(n,k)&= \dfrac{C(n,k-1)}{2^k}.\end{align}By Lemma \ref{lemma2}, for $n \geq 0, \;\ k \geq 1$ and $n-k \equiv \modd{1} {2}$, we have
\begin{equation} \label{zero}
r(n,k) = 0.
\end{equation}
Otherwise, for $s \geq 0$, we have
\begin{align*}
r(2s+1,2m+1) = \dfrac{C(2s+1,2m)}{2^{2m+1}}
&= \dfrac{2s+1}{(m+s+1)\cdot 2\cdot 4^m}\binom{2m}{m-s},
\;\ \;\ \mbox{for } m\geq 0, \\
r(2s,2m) = \dfrac{C(2s,2m-1)}{2^{2m}} &= \dfrac{s}{m\cdot 4^m}\binom{2m}{m-s}
, \;\ \;\ \mbox{for } m\geq 1.
\end{align*}
To apply Theorem \ref{theorem1}, it is necessary to prove the following lemma.
\begin{lemma} \label{lemma3}
For each $n \geq 1$, the probability that one of the players wins the game (by collecting $n$ chips first)
is 1, i.e.,
\[ \sum_{k=1}^{\infty}r(n,k) = 1. \]
\end{lemma}
\begin{proof}
This can be done by induction on $n$. By (\ref{M3}) and (\ref{equation101}), we have the following recurrence relation for the numbers $r(n,k)$:
\begin{align} \nonumber r(n,k) &= \dfrac{C(n,k-1)}{2^k} = \dfrac{C(n-1,k)}{2^k}-\dfrac{C(n-2,k-1)}{2^k} \\
&= 2r(n-1,k+1) - r(n-2,k). \label{equation102} \end{align}
By (\ref{equation100}), we note that \begin{align} \label{equation103} \displaystyle \sum_{k=1}^{\infty}r(1,k) &= 1.\end{align}
For $n=2$, by (\ref{equation102}) and (\ref{equation103}), we get
\begin{align*} \sum_{k=1}^{\infty}r(2,k) &= \sum_{k=1}^{\infty} \big(2r(1,k+1)-r(0,k)\big)
= 2\sum_{k=1}^{\infty} r(1,k+1) +2r(1,1) -2r(1,1) \\
&= 2\sum_{k=1}^{\infty} r(1,k) -2r(1,1) = 2-1 =1
\end{align*}
since $r(0,k) =0$ for all $k \geq 1$.
For the cases $n \geq 3$, by (\ref{equation102}) and the inductive hypothesis, we have
\begin{align*} \sum_{k=1}^{\infty}r(n,k) &= \sum_{k=1}^{\infty} \big(2r(n-1,k+1)-r(n-2,k)\big)\\
&= 2\sum_{k=1}^{\infty} r(n-1,k) -\sum_{k=1}^{\infty}r(n-2,k) = 2-1 =1
\end{align*}
since $r(n-1,1) =0$ for all $n \geq 3$.
\end{proof}
Finally, we are in the position to apply Theorem \ref{theorem1} for each value of $n$.
For example, to evaluate
$\displaystyle \sum_{k=1}^{\infty} r(2,k)^2$, we type
\[\texttt{ sum( (binomial(2*m,m-1)/m/4\string^m)\string^2 ,m=1..infinity);} \]
and then Maple will return $\dfrac{16}{\pi}-5$. By Theorem \ref{theorem1},
\[ p_2 = \dfrac{1}{2}-\dfrac{1}{2}\bigg(\dfrac{16}{\pi}-5\bigg) \approx 0.4535209109. \]
For $n\geq 3$, we list some values of $\displaystyle \sum_{k=1}^{\infty} r(n,k)^2$ as follows:
\begin{align*}
\sum_{k=1}^{\infty} r(3,k)^2 &= \dfrac{236}{3\pi}-25, \\
\sum_{k=1}^{\infty} r(4,k)^2 &= \dfrac{1216}{3\pi}-129, \\
\sum_{k=1}^{\infty} r(5,k)^2 &= \dfrac{32092}{15\pi}-681,\\
\sum_{k=1}^{\infty} r(6,k)^2 &= \dfrac{172144}{15\pi}-3653.
\end{align*}The corresponding values of $p_n$ are
\begin{align*}
p_3 \approx 0.4798111434 , \\
p_4 \approx 0.4891964033 , \\
p_5 \approx 0.4933044576 , \\
p_6 \approx 0.4954322531. \end{align*}
There is an interesting pattern for the values of $\displaystyle \sum_{k=1}^{\infty} r(n,k)^2$ for $n\geq 1$.
In fact, let $T_n$ be $\displaystyle \sum_{k=1}^{\infty} r(n,k)^2$. The terms
$T_n$ appear to satisfy a recurrence relation with polynomial coefficients:
\begin{align} (n+3)T_{n+3}-(7n+16)T_{n+2}+(7n+5)T_{n+1}-n T_n&=0. \label{special} \end{align}
(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_0n+b_0)T_{n}+(a_1n+b_1)T_{n+1}+\dots+(a_Nn+b_N)T_{n+N}=0\]
for some specific $N$. Then, by plugging in values of $n, T_n, T_{n+1}, \dots, T_{n+N}$,
say, for $n=1,2,\dots,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 \cite[Chapter 6]{AB} and Zeilberger's Maple package \texttt{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 \eqref{special}, we obtain the asymptotic approximation of $T_n$ (see Wimp and Zeilberger \cite{JZ}) as follows:
\[ T_n = \dfrac{1}{\pi n^2}\left( 1+\dfrac{1}{n^2} + \dfrac{19}{4n^4}
+\dfrac{107}{2n^6} +\dots \right) + O(\alpha^n)\]
for some $\alpha$ such that $|\alpha| < 1.$
\subsection{The winning probability within $k$ moves} \label{section2.3}
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 \ref{section2.1} that
\[r(2m) =0 \]
and
\[ r(2m-1) = \dfrac{(2m-2)!}{m!(m-1)!}\cdot \dfrac{2}{4^m} . \]
By Remark \ref{remark1}, we have
\[ q(2m)=q(2m-1) = 1-\sum_{j=1}^m r(2j-1)
= 1-\sum_{j=1}^m \dfrac{(2j-2)!}{j!(j-1)!}\cdot \dfrac{2}{4^j}.\]
This finite sum is Gosper-summable. In Maple, we type
\[ \texttt{ simplify( 1-sum( (2*j-2)!*2/j!/(j-1)!/4\string^j ,j=1..m));} \]
and the output is $\dfrac{\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 \eqref{M1}) is
\begin{align*}
\sum_{i=1}^k q(i)r(i) &= \sum_{j=1}^{\left\lfloor\frac{k+1}{2}\right\rfloor} q(2j-1)r(2j-1)\\
&= \sum_{j=1}^{\left\lfloor\frac{k+1}{2}\right\rfloor} \dfrac{\binom{2j}{j}}{4^j}\dfrac{(2j-2)!}{j!(j-1)!}\cdot \dfrac{2}{4^j}\\
&= \sum_{j=1}^{\left\lfloor\frac{k+1}{2}\right\rfloor} \binom{2j}{j}^2 \cdot \dfrac{1}{16^j}\cdot \dfrac{1}{2j-1}.
\end{align*}
In Maple, we type
\[ \texttt{ sum(binomial(2*j,j)\string^2/16\string^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-\dfrac{2L+1}{16^L}\binom{2L}{L}^2,
\;\ \;\ \mbox{where } L = \left\lfloor\frac{k+1}{2}\right\rfloor. \]
\subsection{Average duration of a game} \label{section2.4}
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 \cite{RS} on the duration
of the game \textit{Dreidel}.
Let the random variable $X$ be the number of moves required to end the game.
\begin{theorem}
For any take-away move $\{a,b\}$ where $a$ and $b$ are not necessarily positive,
the average duration of the game is
$\displaystyle \sum_{k=0}^{\infty} q(n,k)^2$.
\end{theorem}
\begin{proof}We compute $E[X]$ as follows:
\begin{align*}
E[X] &= \sum_{k=1}^{\infty} k \cdot P(\mbox{ the game ends at the } k^{\text{th}} \mbox{ turn}) \\
&= \sum_{k=1}^{\infty} k \cdot \big(q(n,k-1)r(n,k)+q(n,k)r(n,k)\big) \\
&= \sum_{k=1}^{\infty} k \cdot \Big(q(n,k-1)^2-q(n,k)^2\Big) \\
&= \sum_{k=1}^{\infty} q(n,k-1)^2.
\end{align*}
The result follows by shifting the index $k$ by 1.
\end{proof}
\begin{corollary}
For the case $\{a,b\}=\{-1,1\}$, $E[X]= \infty$ for any $n \geq 1$.
\end{corollary}
\begin{proof}
For $n =1$, by our computation of the probability $q(k)$ in Section \ref{section2.3}, we have \[ E[X] = \sum_{k=0}^{\infty} q(k)^2= 1+2 \cdot \sum_{m=1}^\infty
\Bigg(\dfrac{\binom{2m}{m}}{4^m} \Bigg)^2 = \infty. \]
The last equality was found by Maple. But we can also show that it is true by the following approximation: \[\Bigg(\dfrac{\binom{2m}{m}}{4^m} \Bigg)^2
\approx \dfrac{1}{\pi m} \mbox{ as } m \to \infty.\]
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]= \infty$ holds true for $n>1$.
\end{proof}
\section{The case $\{a,b\}=\{-1,2\}$} \label{section3}
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^{\text{th}}$ move without ever collecting $n$ chips (thus allowing the game to continue).
\begin{lemma}
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)=\dfrac{\binom{3m}{m}}{2m+1}, \quad
D(1,3m+1)=\dfrac{\binom{3m+1}{m+1}}{2m+1}
, \quad D(1,3m+2)=0.\]
\end{lemma}
\begin{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 \seqnum{A001764} in OEIS and was named {\it $3$-Raney sequences} \cite[Section 7.5]{GKP}.
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 \seqnum{A006013} in OEIS.
\end{proof}
We have the following relation \[r(n,k)= \dfrac{D(n,k-1)}{2^k}\]because the player has $n-1$ or $n-2$ chips on his $(k-1)^{\text{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, $\displaystyle \lim_{k \to \infty}q(n,k) =0$ for each $n \geq 0$.
For each $n\geq 1$, we evaluate
$\displaystyle \sum_{k=1}^\infty r(n,k)^2$
and apply Theorem \ref{theorem1} 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 \ref{tab1} below.
\begin{table}[ht]
\begin{center}
\begin{tabular}{c|c|c}
$n$ & $\displaystyle \sum_{k=1}^\infty r(n,k)^2$ & $ p_n$ \\
\hline
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{tabular}\caption{The values of $\displaystyle \sum_{k=1}^\infty r(n,k)^2$ and $p_n$ for some $n$} \label{tab1}
\end{center}
\end{table}
\section{A remark on Theorem \ref{theorem1}} \label{section4}
We would like to find an analog of Theorem \ref{theorem1} 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
\begin{equation} \label{new}
p_{n_1,n_2} = \sum_{k=1}^{\infty} q(n_1,k)\cdot r(n_2,k).
\end{equation}
Similarly, the probability that the first player collects
$n_1$ chips before the second player collects $n_2$ chips is
\[ \sum_{k=1}^{\infty} q(n_2,k-1)\cdot 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 \geq 0$, we have
\[ \sum_{k=1}^{\infty} q(n_2,k-1)\cdot r(n_1,k)
+ \sum_{k=1}^{\infty} q(n_1,k)\cdot r(n_2,k) = 1.\]
By Lemma \ref{claim1}, we have a generalization of Theorem \ref{theorem1} as follows:
\begin{proposition} \label{proposition7}
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} + \sum_{k=1}^{\infty} r(n_1,k)\cdot r(n_2,k) = 1. \]
\end{proposition}
\subsection{The probability $p_{n_1,n_2}$ for the case $ \{a,b\} = \{-1, 1\}$} \label{section4.1}
We list some values of $p_{n_1,n_2}$ obtained by the equation \eqref{new} in Table \ref{table:nonlin} 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 \ref{section2.3}, we obtained
\[ q(1,2m)=q(1,2m-1)= \dfrac{\binom{2m}{m}}{4^m}. \]Based on the closed-form expression of $q(n,k)$ and Lemma \ref{claim1}, we can simplify the infinite sums in the equation (\ref{new}) nicely for different values of $n_1$ and $n_2$. For more values of $p_{n_1, n_2}$, one can use the function \texttt{Win2($n_1$, $n_2$)} in the
accompanied Maple program.
\begin{table}[ht]
\begin{center}
\begin{tabular}{c | c c c c c}
\hline
$n_1$ $\backslash$ $n_2$ & 1 & 2 & 3 & 4 & 5\\ [0.5ex] \hline \\
1 & $\dfrac{\pi-2}{\pi}$ & $\dfrac{4-\pi}{\pi}$ & $\dfrac{10-3\pi}{\pi}$ &
$\dfrac{3\pi-8}{3\pi}$ & $\dfrac{15\pi-46}{3\pi}$ \\ [3ex]
2 & $\dfrac{2(\pi-2)}{\pi}$ & $\dfrac{3\pi-8}{\pi}$ & $\dfrac{2(10-3\pi)}{\pi}$ &
$\dfrac{3(16-5\pi)}{\pi}$ & $\dfrac{2(15\pi-46)}{3\pi}$ \\ [3ex]
3 & $\dfrac{3\pi-2}{3\pi}$ & $\dfrac{7\pi-20}{\pi}$ & $\dfrac{39\pi-118}{3\pi}$ &
$\dfrac{296-93\pi}{3\pi}$ & $\dfrac{5(142-45\pi)}{3\pi}$ \\ [3ex]
4 & $\dfrac{8}{3\pi}$ & $\dfrac{16-3\pi}{3\pi}$ & $\dfrac{8(12\pi-37)}{3\pi}$ &
$\dfrac{195\pi-608}{3\pi}$ & $\dfrac{8(63-20\pi)}{\pi}$ \\ [3ex]
5 & $\dfrac{5\pi-2}{5\pi}$ & $\dfrac{92-27\pi}{3\pi}$ & $\dfrac{926-285\pi}{15\pi}$ &
$\dfrac{7(23\pi-72)}{\pi}$ & $\dfrac{5115\pi-16046}{15\pi}$ \\ [1ex]
\end{tabular}
\caption{The winning probability of the
second player, $p_{n_1,n_2}$}
\label{table:nonlin}
\end{center}
\end{table}
\section{Future Work} \label{section5}
Based on our work above, we suggest the following open problems:
\begin{enumerate}
\item Formally prove that the guessed
recurrence relation (\ref{special}) for the terms $\displaystyle\sum_{k=1}^\infty r(n,k)^2$ (where $n\geq 0$) for the case $\{a,b\}=\{-1,1\}$ is correct.
\item Find a recurrence relation for the terms $\displaystyle \sum_{k=1}^\infty r(n,k)^2$ (where $n\geq 0$) for the case $\{a,b\}=\{-1,2\}$,
and then find an asymptotic approximation for it.
\item 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.
\end{enumerate}
\section{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.
\begin{thebibliography}{9}
\bibitem{WW} E.~Berlekamp, J.~Conway, and R.~Guy, \emph{Winning Ways for Your Mathematical Plays. Vol.~2},
2nd edition, A. K. Peters, 2001.
\bibitem{GKP} R.~L.~Graham, D.~E.~Knuth, and O.~Patashnik, \emph{Concrete Mathematics}, 2nd edition, Addison-Wesley, 1994.
\bibitem{AB} M.~Petkovsek, H.~Wilf, and D.~Zeilberger, \emph{A = B}, 1st edition, A. K. Peters, 1996.
\bibitem{RS} T.~Robinson and S.~Vijay, Dreidel lasts $O(N^2)$ spins, \emph{Adv. in Appl. Math.} {\bf 36} (2006), 85--94.
\bibitem{JZ} J.~Wimp and D.~Zeilberger, Resurrecting the asymptotics of linear recurrences, \emph{J. Math.
Anal. Appl.} {\bf 111} (1985), 162--177 .
\bibitem{WX} T.~W.~H. Wong and J.~Xu, A probabilistic
take-away game, \emph{J. Integer Sequences} {\bf 21} (2018),
\href{https://cs.uwaterloo.ca/journals/JIS/VOL21/Wong2/wong8.pdf}{Article
18.6.3}.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 91A60; Secondary 05A10, 11Y55, 60C05.
\noindent \emph{Keywords: }
take-away game, probability, Gosper's algorithm.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A000108},
\seqnum{A001764},
and \seqnum{A006013}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received March 22 2019;
revised versions received May 19 2019; June 29 2019.
Published in {\it Journal of Integer Sequences}, August 19 2019.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}