\documentstyle[12pt,twoside,amstex,eepic]{article}
\input{macros-course}

\parskip1.5ex
\parindent0pt

\begin{document}
\handout{notes26}{Notes 26}{December 12, 1995}

\section{Gambler's Ruin}
Today, we are going to talk about the Gambler's Ruin problem.
This problem is stated as follows.  A gambler starts with \$N.
He bets \$1 each time, and wins \$1 with probability $p$, and loses
\$1 with probability $1-p$.
The game ends when either the gambler is broke or has reached \$T.

We would like to find the probability of a ``win'' (i.e. reaching
\$T).  For example, betting on RED in roulette has a winning probability
of $18/38=9/19$.  Say we start with \$500, which is more likely:  quitting
after reaching \$600 or going broke (bet \$1 each time).
It turns out we will go broke about 99.997\% of the time.

We can visualize this problem as a random walk.  At each step, if we
win we go up by 1 (with probability $p$), otherwise we go down by 1
(with probability $1-p$).  If we hit either the top barrier (\$T) or
the bottom barrier (\$0), the game ends.

\setlength{\unitlength}{0.0125in}
%
\begingroup\makeatletter\ifx\SetFigFont\undefined
% extract first six characters in \fmtname
\def\x#1#2#3#4#5#6#7\relax{\def\x{#1#2#3#4#5#6}}%
\expandafter\x\fmtname xxxxxx\relax \def\y{splain}%
\ifx\x\y   % LaTeX or SliTeX?
\gdef\SetFigFont#1#2#3{%
  \ifnum #1<17\tiny\else \ifnum #1<20\small\else
  \ifnum #1<24\normalsize\else \ifnum #1<29\large\else
  \ifnum #1<34\Large\else \ifnum #1<41\LARGE\else
     \huge\fi\fi\fi\fi\fi\fi
  \csname #3\endcsname}%
\else
\gdef\SetFigFont#1#2#3{\begingroup
  \count@#1\relax \ifnum 25<\count@\count@25\fi
  \def\x{\endgroup\@setsize\SetFigFont{#2pt}}%
  \expandafter\x
    \csname \romannumeral\the\count@ pt\expandafter\endcsname
    \csname @\romannumeral\the\count@ pt\endcsname
  \csname #3\endcsname}%
\fi
\fi\endgroup
\begin{picture}(300,175)(0,-10)
\path(40,160)(40,0)
\path(20,40)(300,40)
\dottedline{5}(20,140)(300,140)
\path(40,80)(60,100)(80,80)
	(100,100)(120,120)(140,100)
	(160,120)(180,100)(200,80)
	(220,60)(240,80)(260,100)
	(280,120)(300,140)
\put(0,140){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{rm}T}}}}}
\put(0,40){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{rm}0}}}}}
\put(60,20){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{rm}1}}}}}
\put(80,20){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{rm}2}}}}}
\put(100,20){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{rm}3}}}}}
\put(0,80){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{rm}N}}}}}
\end{picture}


We are interested in the probability of winning and losing.
It's not clear whether these add up to 1.  It might be possible
that we play the game forever.  Later, we will show this happens
with probability 0.

Let $W$ be the event we win (i.e. reach \$T before \$0).
Let $D_t$ be the random variable corresponding to the number
of dollars held at step $t$ and $P_n= Pr(W|D_0=n)$.
We wish to calculate $P_n$.

We can use a recursive approach.  We claim 
\[
P_n = \left\{ \begin{array}{ll}
                0 & \mbox{if $n=0$} \\
                1 & \mbox{if $n=T$} \\
		pP_{n+1}+(1-p)P_{n-1} & \mbox{if $0<n<T$}
              \end{array}
        \right.
\]

The first two conditions follow by the definition of a win or lose.
The last condition is derived as follows.  Let $E$ be the event of
a win on the first bet.  Then, 

\begin{eqnarray*}
P_n &=&  Pr(W|D_0=n) \\
&=&  Pr(W\wedge E|D_0=n) + Pr(W\wedge \bar{E}|D_0=n) \mbox{ Law of Total Probability} \\
&=&  Pr(E|D_0=n) Pr(W|E\wedge D_0=n) +  Pr(\bar{E}|D_0=n) Pr(W|\bar{E}\wedge D_0=n) \mbox{ Cond. Prob.}\\
&=&  pPr(W|D_1=n+1)+(1-p)Pr(W|D_1=n-1) \\
&=&  pPr(W|D_0=n+1)+(1-p)Pr(W|D_0=n-1) \\
&=&  pP_{n+1}+(1-p)P_{n-1} \\
\end{eqnarray*}

Note that $Pr(W|D_1=n+1)=Pr(W|D_0=n+1)$, since we play till one of the
termination conditions.  Thus, we can view the game as resetting at
each step.  Rewriting, we have $pP_{n+1}-P_n +(1-p)P_{n-1}=0$, which
is a linear homogeneous equation with two boundary conditions.

The characteristic equation is $p\alpha^2 - \alpha +(1-p)=0$.

The roots are:  $\frac{1-p}{p}$, 1.   These roots are distinct if $p\neq 1/2$.

Let's assume $p\neq 1/2$.  We will consider the other case later.

Then, 
\[
P_n = A \left(\frac{1-p}{p}\right)^n + B 1^n.
\]

Using the boundary conditions, $P_0=0$ and $P_T=1$, we obtain
\[
A=\frac{1}{\left(\frac{1-p}{p}\right)^T -1}, B= -A.
\]

Thus, 
\begin{eqnarray*}
P_n& =& 
\frac{\left(\frac{1-p}{p}\right)^n}{\left(\frac{1-p}{p}\right)^T -1}
- \frac{1}{\left(\frac{1-p}{p}\right)^T -1}\\
&=& \left(\frac{p}{1-p}\right)^{T-n} 
\frac{1- \left(\frac{p}{1-p}\right)^n}{1- \left(\frac{p}{1-p}\right)^T} \\
&\leq& \left(\frac{p}{1-p}\right)^{T-n}
\end{eqnarray*}

Example:  Let $p=9/19$, $T=600$, $n=500$, then $Pr(win) \leq (.9)^{100} \leq
0.003\%$.

Even if we let $n=\$1,000,000,000$ and $T=n+100$, then the $Pr(win)\leq
0.003\%$.  In other words, we expect to lose \$1 trillion before
winning \$100.  The last inequality does not depend on where you start.
It's a good approximation if both $T$ and $n$ are large.
For small values, we can use the exact formula.

Example: $n=10$, $T=20$.
$Pr(win) = (.9)^{10} \left(\frac{1-.9^{10}}{1-.9^{20}}\right) = 9\%$.
Bad odds, but not astronomically small.

Remember, we assumed that $p\neq 1/2$.  Let's consider the case
$p=1/2$.  Now, we have a double root of 1.  Thus, 
\[
P_n=An+B,
\]

Using the conditions, $P_0 = 0$ and $P_T=1$, we derive the solution as
\[
P_n = \frac{n}{T}.
\]

Example:  $n=500$, $T=600$.  $Pr(win) = 500/600 = 5/6$.
This is about what we would expect.  For example, if $T=2n$, then
the probability of doubling your money or losing all your money is the
same -- 1/2.

This problem can also be stated in the following manner.
Suppose Andrew starts with \$100, and Ravi starts with \$10.
They flip a fair coin, and every time a head appears, Andrew wins \$1 
from Ravi, and vice versa for tails.  They play this game until
one person goes bankrupt.  What is the probability of Andrew winning?

This problem is identical to the previous problem with $n=100$ and
$T=100+10=110$.  The probability of Andrew winning is $100/110 =
10/11$.  In other words, the ratio of his wealth to the combined
wealth.  Ravi's chances of winnning are $1/11$.  Although Andrew will
win most of the time, the game still have ZERO expected value for him.
When Andrew wins, he wins \$10.  When he loses, he loses big -- \$100.
Thus, the expectation is
\[
10(10/11) - 100(1/11) = 0.
\]

Observe that the expectation had to be zero.  Each individual coin
flip has zero expectation.  Thus, by linearity of expectation, any
set of coins flips must still have zero expectation.

One issue we'd like to resolve is the apparent difference between the
games with a biased and unbiased coin.  If $p$ is very close to 1/2,
we would expect the probabilities of winning to be similar.  However,
the probability of winning (with a biased coin) is much worse than an
unbiased coin.  Intuitively, this seems very strange.  The correct
intuition is as follows.  If the boundaries are far from the starting
point (i.e. $T$ and $0$ are not to close to $n$), the amount of time
for the random walk to reach the boundary is pretty long.  With a fair
coin, the random walk will have an equal chance of swinging widely up
or down.  However, with a biased coin, the walk has a downward drift
in it.  As time progress, the upward swing needed to reach the upward
barrier becomes larger, and the downward swing to hit the lower
barrier gets smaller.  Thus, if it takes a long time to see a large
swing, the downward drift will be the dominant factor.

\setlength{\unitlength}{0.0125in}
%
\begingroup\makeatletter\ifx\SetFigFont\undefined
% extract first six characters in \fmtname
\def\x#1#2#3#4#5#6#7\relax{\def\x{#1#2#3#4#5#6}}%
\expandafter\x\fmtname xxxxxx\relax \def\y{splain}%
\ifx\x\y   % LaTeX or SliTeX?
\gdef\SetFigFont#1#2#3{%
  \ifnum #1<17\tiny\else \ifnum #1<20\small\else
  \ifnum #1<24\normalsize\else \ifnum #1<29\large\else
  \ifnum #1<34\Large\else \ifnum #1<41\LARGE\else
     \huge\fi\fi\fi\fi\fi\fi
  \csname #3\endcsname}%
\else
\gdef\SetFigFont#1#2#3{\begingroup
  \count@#1\relax \ifnum 25<\count@\count@25\fi
  \def\x{\endgroup\@setsize\SetFigFont{#2pt}}%
  \expandafter\x
    \csname \romannumeral\the\count@ pt\expandafter\endcsname
    \csname @\romannumeral\the\count@ pt\endcsname
  \csname #3\endcsname}%
\fi
\fi\endgroup
\begin{picture}(397,121)(0,-10)
\path(244,106)(244,12)
\dottedline{5}(232,94)(397,94)
\path(232,23)(397,23)
\path(244,59)(256,71)(267,59)
	(279,47)(291,35)(302,47)
	(314,35)(326,47)(337,59)
	(349,47)(362,35)(373,47)
	(385,35)(397,23)
\dottedline{5}(244,59)(397,23)
\put(221,94){\makebox(0,0)[lb]{\smash{{{\SetFigFont{7}{8.4}{rm}T}}}}}
\put(221,35){\makebox(0,0)[lb]{\smash{{{\SetFigFont{7}{8.4}{rm}0}}}}}
\put(221,59){\makebox(0,0)[lb]{\smash{{{\SetFigFont{7}{8.4}{rm}N}}}}}
\put(267,12){\makebox(0,0)[lb]{\smash{{{\SetFigFont{7}{8.4}{rm}Time}}}}}
\put(397,23){\makebox(0,0)[lb]{\smash{{{\SetFigFont{7}{8.4}{rm}Drift}}}}}
\put(279,0){\makebox(0,0)[lb]{\smash{{{\SetFigFont{7}{8.4}{rm}Biased Game}}}}}
\path(23,106)(23,12)
\dottedline{5}(12,94)(176,94)
\path(23,59)(35,71)(47,59)
	(58,71)(71,83)(83,71)
	(94,83)(106,71)(118,59)
	(129,47)(141,59)(153,71)
	(164,83)(176,94)
\path(12,23)(176,23)
\dottedline{5}(23,59)(176,59)
\put(58,0){\makebox(0,0)[lb]{\smash{{{\SetFigFont{7}{8.4}{rm}Fair game}}}}}
\put(0,94){\makebox(0,0)[lb]{\smash{{{\SetFigFont{7}{8.4}{rm}T}}}}}
\put(0,35){\makebox(0,0)[lb]{\smash{{{\SetFigFont{7}{8.4}{rm}0}}}}}
\put(0,59){\makebox(0,0)[lb]{\smash{{{\SetFigFont{7}{8.4}{rm}N}}}}}
\put(47,12){\makebox(0,0)[lb]{\smash{{{\SetFigFont{7}{8.4}{rm}Time}}}}}
\put(176,59){\makebox(0,0)[lb]{\smash{{{\SetFigFont{7}{8.4}{rm}Drift}}}}}
\end{picture}


Earlier, we claimed the probability of playing forever is 0.
For example, the sequence $WLWLWLWL ...$ would allow
the player to play forever.  In fact, there are infinite number of sequences
that allow the player to play forever.  Nevertheless, the probability
of all these sequences is 0.  What we really mean is they form a set
of measure 0.  It is possible that one could play forever, but the
likelihood of that is arbitrary close to 0.


\begin{theorem}
For $0<p<1$, the probability that the game never ends is 0.
\end{theorem}

\begin{proof}
Break the time line into intervals of size $T$.
The probability you go broke in the $ith$ interval is at least
$(1-p)^T$ (i.e. if you lose $T$ times in row, you will definitely lose).
The probability that you continue to play is at most $1-(1-p)^T$.
After $k$ such intervals, the probability you continue to play is at most
$(1-(1-p)^T)^k$.  As $k$ gets large, this probability goes to 0.
\end{proof}

In fact, if $p<1/2$, then you will be broke in $\Theta(n)$ time with
probability close to 1.  The payoff distribution follows a binomial.
As you recall, the tails of a binomial shrink expontentially fast.

Let's return to the fair game with an unbiased coin.
We'll change the game a bit, so you either play forever or go broke.
What is the probability that you go broke?  It turns out to be 1.

\begin{theorem}
For any initial wealth, $n$, the probability of going broke
is 1.
\end{theorem}

\begin{proof}
For any $T>n$, we have shown that the probability of reaching $T$ 
before going broke is $\frac{n}{T}$, and the probability of neither
reaching $T$ or 0 is 0.  Therefore, the probability of going broke
before reaching $T$ is
$1-\frac{n}{T}$.

We now proceed by contradiction.  Assume the probability of
going broke, $P$ is less than 1.  (i.e. $P<1$).

Choose $T> \frac{n}{1-P}$.  Therefore, 
\begin{eqnarray*}
P & \geq & Pr(\mbox{going broke before reaching $T$})\\
&=& 1-\frac{n}{T}\\
&>&1-\frac{n}{\frac{n}{1-P}}\\
&=&1-(1-P)\\
&=&P
\end{eqnarray*}

This implies $P>P$ -- a contradiction.
Therefore, $P=1$.
\end{proof}

So far, we've been pessimistic.  Our final result will be positive.
In the fair game, even though you will go broke with probability 1, 
your expected playing time is infinite.  Even if you start with \$1.

\begin{theorem}
If $n=1$ and $p=1/2$, expected time to go broke is infinite.
\end{theorem}

\begin{proof}
Let $S$ be the number of step to go broke.
Note that $S$ must be odd.  After an even number of steps,
the final wealth must be 1+(even).  So, $S$ is odd.

Claim:  For $t$ odd, $Pr(S=t) = \frac{2}{t+1} {t \choose {\frac{t-1}{2}}}
2^{-t}$.

For $S=t$, the random walk must start at (0,1) and end at
(t,0) without previously touching  the $0$-axis.
This is equivalent to the number of paths from (0,1) to (t-1,1), which
do not touch the $0$-axis.  This is identical to the
Catlaan number for $t-1$.
Each path has probability $2^{-t}$, which completes the claim.

Asymptotically, $Pr(S=t)=\Theta(t^{-3/2})$ from Stirling
approximation.
Therefore, 
\[
Pr(S>m) = 
\sum_{t\mbox{ odd,}t=m+1}^\infty \Theta(t^{-3/2}) = \Theta(1/\sqrt{m}).
\]

Finally,
\[
Ex(S) = \sum_{m=0}^\infty Pr(S>m) = \sum_{m=0}^\infty \Theta(1/\sqrt{m}).
\]

This above sum is unbounded and approaches infinity.  Thus, the
expected length of the game is infinite.
\end{proof}

\end{document}

