\documentclass[11pt]{article}
\usepackage{macros-course-lectures}

\lectureformat

\showsolutionstrue

\begin{document}

\lecture{notes15}{Random Walks}{December 10, 2001}{\stamp}


\section{Overview}

Many natural phenomena are nicely modeled by \emph{random walks} in which a
person, or particle, or process takes steps in a randomly chosen sequence
of directions.  For example in Physics, three-dimensional random walks are
used to model Brownian motion and gas diffusion.  In Computer Science, the
Google search engine uses random walks through the graph of world-wide web
links to determine the relative importance of websites.  In Finance Theory,
there is continuing debate about the degree to which one-dimensinal random
walks can explain the moment-to-moment or day-to-day fluctuations of market
prices.


In the Mathematical literature, random walks are for some reason
traditionally discussed in the context of some social vice.  A
one-dimensinal random walk is often described as the path of a drunkard
who randomly staggers left or right at each step.  In these Notes, we
examine one-dimensinal random walks using the language of gambling.  In
this case, a position during the walk is a gambler's cash-on-hand or
\emph{capital}, and steps on the walk are bets whose random outcomes
increase or decrease his capital.  We will be interested in two main
questions:
\begin{enumerate}
\item What is the probability that the gambler wins?
\item How long must the gambler expect to wait for the walk to end, and
will it always end?
\end{enumerate}


\section{Gambler's Ruin}

A gambler starts with $n$ dollars.  He makes a sequence of \$1 bets.  If
he wins, he gets his money back plus another \$1.  If he loses, he loses
the \$1.  In each bet, he wins with probability $p>0$ and loses with
probability $q \eqdef 1-p >0$.  The gambler plays until either he is
bankrupt or increases his capital to a goal amount of $T$ dollars.  If he
reaches his goal, then he is called a {\em winner}, and his \emph{profit}
will be $m \eqdef T-n$ dollars.  If his capital reaches zero dollars
before reaching his gaol, then we say that he is ``ruined'' or {\em goes
broke}.

The gambler's situation as he proceeds with his \$1 bets is illustrated in
Figure~\ref{fig:walk1}.  The random walk has boundaries at 0 and $T$.  If
the random walk ever reaches either of these boundary values, then it
terminates.  We want to determine the probability, $w$, that the walk
terminates at boundary $T$, namely, the probability that the gambler is a
winner.

\begin{figure}
  \centerline{\includegraphics[height=2.5in]{figures/walk1}}
  \caption{\em This is a graph of the gambler's capital versus time
  for one possible sequence of bet outcomes.  At each time step, the
  graph goes up with probability $p$ and down with probability $1-p$.
  The gambler continues betting until the graph reaches either 0 or $T
  = n + m$.}
  \label{fig:walk1}
\end{figure}

In a fair game, $p = q = 1/2$.  The corresponding random walk is
called {\em unbiased}.  The gambler is more likely to win if $p>1/2$ and
less likely to win if $p<1/2$; the corresponding random walks are called
{\em biased}.

\begin{example}
Suppose that the gambler is flipping a coin, winning \$1 on Heads and
losing \$1 on Tails.  Also, the gambler's starting capital is $n = 500$
dollars, and he wants to make $m = 100$ dollars.  That is, he plays until
he goes broke or reaches a goal of $T = n + m = \$600$.  What is the
probability that he is a winner?  We will show that in this case the
probability $w = 5/6$.  So his chances of winning are really very good,
namely, 5 chances out of 6.

Now suppose instead, that the gambler chooses to play roulette in an
American casino, always betting \$1 on red.  A roulette wheel has 18 black
numbers, 18 red numbers, and 2 green numbers.  In this game, the
probability of winning a single bet is $p = 18/38 \approx 0.47$.  It's the
two green numbers that slightly bias the bets and give the casino an edge.
Still, the bets are almost fair, and you might expect that the gambler has
a reasonable chance of reaching his goal---the 5/6 probability of winning
in the fair game surely gets reduced, but perhaps not too drastically.
Not so!  His odds of winning against the ``slightly'' unfair roulette
wheel are less than 1 in 37,000.  If that seems surprsing, listen to this:
\emph{no matter how much money} the gambler has to start, \eg \$5000,
\$50,000, $\$5 \cdot 10^{12}$, his odds are still less than 1 in 37,000 of
winning a mere 100 dollars!

Moral:  Don't play!
\end{example}

The theory of random walks is filled with such fascinating and
counter-intuitive conclusions.

\section{The Probability Space}

Each random-walk game corresponds to a path like the one in
Figure~\ref{fig:walk1} that starts at the point $(n,0)$.  A winning path
never touches the $x$ axis and ends when it first touches the line $y=T$.
Likewise, a losing path never touches the line $y=T$ and ends when it first
touches the $x$ axis.

\iffalse

\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}
\fi

Any length $k$ path can be characterized by the history of wins and losses
on individual \$1 bets, so we use a length $k$ string of $W$'s and $L$'s to
model a path, and assign probability $p^rq^{k-r}$ to a string that contains
$r$ $W$'s.  The \emph{outcomes} in our sample space will be precisely those
string corresponding to winning or losing walks.

What about the infinite walks in which the gambler plays forever, neither
reaching his goal nor going bankrupt?  We saw in a problem set that the
probability of playing forever is zero, so we don't need to include any
such outcomes in our sample space.

As a sanity check on this definition of the probability space, we should
verify that the sum of the outcome probabilities is zero, but we omit this
calculation.

\iffalse

To do this, we
let $X$ be any string of $W$'s and $L$'s, and let $[X]$ be the event
consisting of the outcomes that begin with $X$.  If $X$ itself is not an
outcome but begins with an outcome, then $[X] = \emptyset$ so $\pr{[X]} =
0$.  On the other hand, if no prefix of $X$ is an outcome, then it's easy
to verify by induction on $k$ that $\pr{[X]} = p^rq^{k-r}$.  length $k$

%%%COMPLETE

We'll leave this to the reader.
\fi

\section{The Probability of Winning}

\subsection{The fair case}

Let's begin by considering the case of a fair coin, that is, $p = 1/2$, and
determine the probability, $w$, that the gambler wins.  We can handle this
case by considering the expectation of the random variable $G$ equal to the
gambler's dollar gain.  That is, $G = T-n$ if the gambler wins, and $G= -n$
if the gambler loses, so
\begin{equation}\label{EG}
\expect{G} = w(T-n) - (1-w)n = wT - n.
\end{equation}
Notice that we're using the fact that the only outcomes are those in which
the gambler wins or loses---these are no infinite games---so the
probability of losing is $1-w$.

Now let $G_{i}$ be the amount the gambler gains on the $i$th flip:
$G_{i}=1$ if the gambler wins the flip, $G_{i}=-1$ if the gambler loses the
flip, and $G_{i}=0$ if the game has ended before the $i$th flip.  Since the
coin is fair, $\expect{G_{i}}=0$.

The random variable $G$ is the sum of all the $G_{i}$'s, so by linearity of
expectation\footnote{We've been stung by paradoxes in this kind of
situation, so we should be careful to check that the condition for infinite
linearity of expectation is satisfied.  Namely, we have to check that
$\sum_{i=1}^\infty \expect{\abs{G_i}}$ converges.  But $\abs{G_i} = 1$ iff
the walk is of length at least $i$, and $\abs{G_i} = 0$ otherwise.  So
\[
\expect{\abs{G_i}} = \pr{\text{the walk is of length } \geq i}.
\]
But we showed in a problem set that there is a constant $\epsilon >0$ such that
\[
\pr{\text{the walk is of length } \geq i} \leq (1 - \epsilon)^i.
\]
So the $\sum_{i=1}^\infty \expect{\abs{G_i}}$ is bounded term-by-term by a
convergent geometric series, and so it also converges.}
\[
wT - n= E(G) = \sum_{i=1}^{\infty}E(G_{i}) = 0,
\]
and
\[
w = \frac{n}{T}.
\]

\begin{example}
Suppose we have \$100 and we start flipping a fair coin, betting \$1 with
the aim of winning \$100.  Then the probability of reaching the \$200 goal
is $100/200=1/2$---the same as the probability of going bankrupt.  In
general, if $T=2n$, then the probability of doubling your money or losing
all your money is the same.  This is about what we would expect.
\end{example}

\begin{example}\label{win100}
Suppose we have \$500 and we start flipping a fair coin, betting \$1 with
the aim of winning \$100.  So $n=500, t=600$, and $\pr{\mbox{win}} =
500/600 = 5/6$, as we claimed at the outset.
\end{example}

\begin{example}
Suppose Albert starts with \$100, and Radhi starts with \$10.  They flip a
fair coin, and every time a Head appears, Albert wins \$1 from Radhi, and
vice versa for Tails.  They play this game until one person goes bankrupt.
What is the probability of Albert winning?

This problem is identical to the Gambler's Ruin problem with $n=100$ and
$T=100+10=110$.  The probability of Albert winning is $100/110 = 10/11$,
namely, the ratio of his wealth to the combined wealth.  Radhi's chances of
winnning are $1/11$.

Note that although Albert will win most of the time, the game is still
fair.  When Albert wins, he only wins \$10; when he loses, he loses
big---\$100.  Albert's---and Radhi's---expected win is zero dollars.
\end{example}

Another intuitive idea is confirmed by this analysis: the larger the
gambler's initial stake, the larger the probability that he will win a
fixed amount.

\begin{example}
If the gambler started with one million dollars instead of 500, but aimed
to win the same 100 dollars as in the Example~\ref{win100}, the
probability of winning would increase to $1M/(1M + 100) > .9999$.
\end{example}

\subsection{A Recurrence for the Probability of Winning}

To handle the case of a biased game we need a more general approach.  We
consider the probability of the gambler winning as a function of his
initial capital.  That is, let $p$ and $T$ be fixed, and let $w_n$ be the
gambler's probabiliity of winning when his initial capital is $n$ dollars.
For example, $w_0$ is the probability that the gambler will win given that
he starts off broke; clearly, $w_0 = 0$.  Likewise, $w_T =1$.

Otherwise, the gambler starts with $n$ dollars, where $0 < n < T$.
Consider the outcome of his first bet.  The gambler wins the first bet with
probability $p$.  In this case, he is left with $n+1$ dollars and becomes a
winner with probability $w_{n+1}$.  On the other hand, he loses the first
bet with probability $1-p$.  Now he is left with $n-1$ dollars and becomes
a winner with probability $w_{n-1}$.  Overall, he is a winner with
probability $w_n = p w_{n+1} + q w_{n-1}$.  Solving for $w_{n+1}$ we
have
\begin{equation}\label{rec1}
w_{n+1} = \frac{w_n}{p} - w_{n-1}\frac{q}{p}.
\end{equation}

This kind of inductive definition of a quantity $w_{n+1}$ in terms of a
linear combination of values $w_k$ for $k < n+1$ is called a
\emph{homogeneous linear recurrence}.  There is a simple general method for
solving such recurrences which we now illustrate.  The method is based on a
guess that the form of the solution is $w_n = c^n$ for some $c>0$.  It's
not obvious why this is a good guess, but we now show how to find the
constant $c$ and verify the guess.

Namely, from~(\ref{rec1}) we have
\begin{equation}\label{rec2}
w_{n+1} - \frac{w_n}{p} + w_{n-1}\frac{q}{p} = 0.
\end{equation}
If our guess is right, then this is equivalent to
\begin{equation}\label{rec3}
c^{n+1} - \frac{c^n}{p} + c^{n-1}\frac{q}{p} = 0,
\end{equation}
and factoring $c^{n-1}$ from the lefthand side of~(\ref{rec3}) gives
\begin{equation}\label{rec4}
c^2 - \frac{c}{p} + \frac{q}{p} = 0.
\end{equation}
Solving this quadratic equation~(\ref{rec4}) in $c$ yields
\begin{eqnarray*}
c       & = &   \frac{1/p \pm \sqrt{(1/p)^2 - 4(q/p)}}{2} \\
        & = &   \frac{1 \pm \sqrt{1 - 4p(1-p)}}{2p} \\
        & = &   \frac{1 \pm \sqrt{1 - 4p - 4 p^2}}{2p} \\
        & = &   \frac{1 \pm \sqrt{(1 - 2p)^2}}{2p} \\
        & = &   \frac{1 - p}{p} \text{ or } 1.
\end{eqnarray*}
So if we define $w_n \eqdef ((1-p)/p)^n =
(q/p)^n$, then~(\ref{rec2}), and hence~(\ref{rec1}) is satisifed.  We can
also define $w_n \eqdef 1$ and satisfy ~(\ref{rec2}).  Since the lefthand
side of~(\ref{rec2}) is zero using either definition, it follows that any
definition of the form
\begin{equation}
w_n \eqdef A\left(\frac{q}{p}\right)^n + B\cdot 1^n = A\left(\frac{q}{p}\right)^n + B
\end{equation}
will also satisfy~(\ref{rec2}).  Now our boundary conditions, namely the
values of $w_0$ and $w_T$, let us solve for $A$ and $B$:
\[\begin{array}{rccclr}
0 & = & w_0 & = & A + B,\\
1 & = & w_T & = &  A\left(\dfrac{q}{p}\right)^T + B, & \text{ so}\\
A & = &  \dfrac{1}{(q/p)^T -1}, &&& \text{ and}\\
w_n & = & \dfrac{(q/p)^n}{A} - \dfrac{1}{A} & = & \dfrac{(q/p)^n-1}{A}\\
    & = & \dfrac{(q/p)^n-1}{(q/p)^T -1}.
\end{array}\]

Now we can verify our guess work and prove that
\begin{equation}\label{wnsol}
w_n  =  \frac{(q/p)^n-1}{(q/p)^T -1},
\end{equation}
by induction on $n$.  We require that $p \neq q$ so the denominator
in~(\ref{wnsol}) is not zero, so this solution only applies to biased
walks.  That's ok, since we already worked out that $w_n=n/T$ in the
unbiased case, \ie when $p=q$.

\subsection{A Simplified Bound}

The expression on the righthand side of equation~(\ref{wnsol}) for $w_n$ is
a little hard to interpret.  There is a simpler upper bound which is nearly
tight when the gambler's starting capital is large.

Suppose that $p < 1/2$; that is, the game is biased {\em against}
the gambler.  Then both the numerator and denominator in the quotient in
equation~(\ref{wnsol}) are positive, and the quotient is less
than one.  Under these conditions, adding 1 to both the numerator and
denominator increases the quotient:
\begin{lemma*}
If $0 < a < b$, then
\[
\frac{a}{b} < \frac{a+1}{b+1}.
\]
\end{lemma*}
\begin{proof}
\[
\frac{a}{b} = \frac{a(1+1/b)}{b(1+1/b)} = \frac{a+a/b}{b+1} < \frac{a+1}{b+1}.
\]
\end{proof}

It follows that
\[
w_n  < \frac{(q/p)^n}{(q/p)^T}
         =  \left( \frac{p}{q} \right)^{T-n}
         =  \left( \frac{p}{q} \right)^m.
\]
So the gambler goes up $m$ dollars before going broke with probability at
most $(p/q)^m$.

\begin{example}
Suppose that the gambler starts with \$500 and bets on red in
roulette until he is up \$100 or goes broke.  The probability
that he is a winner is at most
\[
w_{500}  <      \left( \frac{18/38}{20/38} \right)^{100}
         =      \left( \frac{9}{10} \right)^{100}
         <      \frac{1}{37,648}.
\]

The amazing thing is that the upper bound on $w_n$ does not depend on $n$,
the gambler's starting capital, but only on $m$, the amount he aims to
profit.  So if the gambler starts with a trillion dollars, his chance of
going up a mere \$100 is still less than 1 in 37,648.  He will almost
surely lose the whole trillion!  The contrast with the fair case, where we
have seen he will almost surely win the \$100, is truly dramatic.

Furthermore, the bound is exponential in $m$.  Regardless of his
starting capital, the probability that the gambler is ever up $m =
1000$ dollars before he goes broke is at most $(9/10)^{1000} < 10^{-45}$.
\end{example}

\begin{example}
The odds of winning a little money are not so bad.  Applying the exact
formula for $w_n$, we can find the probability of winning \$10 before
losing \$10.
\[
w_{10} = \frac{\left( \frac{20/38}{18/38} \right)^{10} - 1}
              {\left( \frac{20/38}{18/38} \right)^{20} - 1}
        = 0.2585\dots
\]
This is somewhat worse than the 1 in 2 chance in the fair game, but not
dramatically so.
\end{example}

Thus, in the fair case, it helps a lot to have a large bankroll,
whereas in the unfair case, it doesn't help much.


\subsection{Intuition}

Why is the gambler so unlikely to make money when the game is slightly
biased against him?  Intuitively, there are two forces at work.
First, the gambler's capital has random upward and downward {\em
swings} due to runs of good and bad luck.  Second, the gambler's
capital will have a steady, downward {\em drift}, because he has a
small, negative expected return on every bet.  The situation is shown
in Figure~\ref{fig:walk2}.

For example, in roulette the gambler wins a dollar with probability $9/19$
and loses a dollar with probability $10/19$.  Therefore, his expected
return on each bet is $9/10 - 10/19 = - 1/19 \approx -0.053$ dollars.  That
is, on each bet his capital is expect to drift downward by a little over 5
cents.

Our intuition is that if the gambler starts with a trillion dollars, then
he will play for a very long time, so at some point there should be a
lucky, upward swing that puts him \$100 ahead.  The problem is that his
capital is steadily drifting downward.  If the gambler does not have a
lucky, upward swing early on, then he is doomed.  After his capital drifts
downward a few hundred dollars, he needs a huge upward swing to save
himself.  And such a huge swing is extremely improbable.  As a rule of
thumb, \emph{drift dominates swings} in the long term.

%\begin{nooutline}
\begin{figure}
\centerline{\includegraphics[height=2.5in]{figures/walk2}}
\caption{\em In an unfair game, the gambler's capital swings randomly up
and down, but steadily drifts downward.  If the gambler does not have
a winning swing early on, then his capital drifts downward, and later
upward swings are insufficient to make him a winner.}
\label{fig:walk2}
\end{figure}
%\end{nooutline}

We can quantify these drifts and swings.  After $k$ rounds, the number of
wins by our player has a binomial distribution with parameters $p < 1/2$
and $k$.  His expected win on any single bet is $p-q = 2p-1$ dollars, so
his expected capital is $n-k(1-2p)$.  Now to be a winner, his actual number
of wins must exceed the expected number by $m+k(1-2p)$.  But we saw before
that the binomial distribution has a standard deviation of only
$\sqrt{kp(1-p)}$.  So for the gambler to win, he needs his number of wins
to deviate by
\[
\frac{m+k(1-2p)}{\sqrt{kp(1-2p)}}=\Theta(\sqrt{k})
\]
times its standard deviation.  In our study of tail bounds we saw that
this was extremely unlikely.

In a fair game, there is no drift; swings are the only effect.  In the
absence of downward drift, our earlier intuition is correct.  If the
gambler starts with a trillion dollars then almost certainly there
will eventually be a lucky swing that puts him \$100 ahead.

If we start with \$10 and play to win only \$10 more, then the difference
between the fair and unfair games is relatively small. We saw that the
probability of winning is $1/2$ versus about $1/4$.  Since swings of \$10
are relatively common, the game usually ends before the gambler's capital
can drift very far.  That is, the game does not last long enough for drift
to dominate the swings.

\section{How Long a Walk?}

Now that we know the probability, $w_n$, that the gambler is a winner in
both fair and unfair games, we consider how many bets he needs on average
to either win or go broke.

\subsection{Duration of an Biased Walk}

Let $Q$ be the number of bets the gambler makes until the game ends.  Since
the gambler's expected win on any bet is $2p-1$, Wald's Theorem should tell
us that his game winnings, $G$, will have expectation $\expect{Q}(2p-1)$.
That is,
\begin{equation}\label{gw}
\expect{G} = (2p-1)\expect{Q},
\end{equation}

In an unbiased game~(\ref{gw}) is trivially true because both $2p-1$ and
the expected overall winnings, $\expect{G}$, are zero.  On the other hand,
in the unfair case, $2p-1 \neq 0$.  Also, we know that
\[
\expect{G} = w_n(T-n) - (1-w_n)n = w_nT-n.
\]
So assuming~(\ref{gw}), we conclude
\begin{equation}\label{ExQ}
\expect{Q} = \frac{w_nT-n}{2p-1}.
\end{equation}

The only problem is that~(\ref{gw}) is not a special case of Wald's
Theorem because $G = \sum_{i=1}^Q G_i$ is not a sum of \emph{nonnegative}
variables: when the gambler loses the $i$th bet, the random variable $G_i$
equals $-1$.  However, this is easily dealt with.  The random variable
$G_i+1$ is nonnegative, and $\expectcond{G_i+1}{Q \geq i} =
\expectcond{G_i}{Q\geq i}+1 = 2p$, so by Wald's Theorem
\begin{equation}\label{G1}
\expect{\sum_{i=1}^Q (G_i+1)}  = 2p\expect{Q}.
\end{equation}
But
\begin{eqnarray}
\expect{\sum_{i=1}^Q (G_i+1)} & = & \expect{\sum_{i=1}^Q G_i + \sum_{i=1}^Q 1}\notag\\
   & = & \expect{(\sum_{i=1}^Q G_i) + Q}\notag\\
   & = & \expect{\sum_{i=1}^Q G_i} + \expect{Q}\notag\\
   & = & \expect{G} + \expect{Q}\label{GQ}.
\end{eqnarray}
Now combining~(\ref{G1}) and~(\ref{GQ}) confirms the truth of our
assumption~(\ref{gw}),

\subsection{Duration of an Unbiased Walk}

This time, we need the more general approach of recurrences to handle the
unbiased case.  We consider the expected number of bets as a
function of the gambler's initial capital.  That is, for fixed $p$ and $T$,
let $e_n$ be the expected number of bets until the game ends when the
gambler's initial capital is $n$ dollars.  Since the game is over in no
steps if $n=0$ or $T$, the boundary conditions this time are $e_0=e_T=0$.

Otherwise, the gambler starts with $n$ dollars, where $0 < n < T$.
Now by the conditional expectation rule, the expected number of steps can
be broken down into the expected number of steps given the outcome of the
first bet weighted by the probability of that outcome.  That is,
\[
e_n = p\expectcond{Q}{\text{gambler wins first bet}} +
q\expectcond{Q}{\text{gambler loses first bet}}.
\]
But after the gambler wins the first bet, his capital is $n+1$, so
he can expect to make another $e_{n+1}$ bets.  That is,
\[
\expectcond{Q}{\text{gambler wins first bet}} = 1 + e_{n+1},
\]
and similarly, 
\[
\expectcond{Q}{\text{gambler loses first bet}} = 1 + e_{n-1}.
\]
So we have
\[
e_n =  p(1 + e_{n+1}) +  q(1 + e_{n-1}) =  pe_{n+1} + qe_{n-1} + 1, 
\]
which yields the linear recurrence
\begin{equation}\label{en1}
e_{n+1} = \frac{e_n}{p} - \frac{q}{p} e_{n-1} - \frac{1}{p}.
\end{equation}
For $p = q = 1/2$, equation~(\ref{en1}) simplifies to
\begin{equation}\label{en2}
e_{n+1} = 2e_n - e_{n-1} - 2.
\end{equation}
There is a general theory for solving linear recurrences like~(\ref{en2})
in which the value at $n+1$ is a linear combination of values at some
arguments $k<n+1$ plus another simple term---in this case plus the constant
$-2$.  This theory implies that
\begin{equation}\label{Tn}
e_n  = (T - n)n.
\end{equation}
Fortunately, we don't need the general theory to \emph{verify} this
solution.  Equation~(\ref{Tn}) can be verified routinely from the boundary
conditions and~(\ref{en2}) using strong induction on $n$.

Note that using the definition $T = n + m$, we can also say
\begin{equation}\label{mn}
e_n   = ((n + m) - n)n = mn.
\end{equation}

Now for example, we can conclude that if the gambler starts with \$10
dollars and plays until he is broke or ahead \$10, then $10 \cdot 10 = 100$
bets are required on average.  If he starts with \$500 and plays until he
is broke or ahead \$100, then the expected number of bets until the game is
over is $500 \times 100 = 50,000$.

Notice that~(\ref{mn}) is a very simple answer that cries out for an
intuitive proof, but we have not found a way to confirm it other than by
induction.

\section{Unbounded ``Fair'' Gambler's Ruin}

\subsection{Quit While You Are Ahead}

Suppose that the gambler never quits while he is ahead.  That is, he
starts with $n>0$ dollars, ignores any goal $T$, but plays until he is
flat broke.  Then it turns out that if the game is not favorable, \ie $p
\leq 1/2$, the gambler is sure to go broke.  In particular, he is even
sure to go broke in a ``fair'' game with $p = 1/2$.
\footnote{If the game is favorable to the gambler, \ie $p>1/2$, then using
methods similar to the ones here, we could show that there is a positive
probability that the gambler will play forever, but we won't examine this
case.}
\begin{lemma}\label{go broke}
If the gambler starts with one or more dollars and plays a fair game until
he is broke, then he will go broke with probability 1.
\end{lemma}

\begin{proof}
If the gambler has initial capital $n$ and goes broke in a game without
reaching a goal $T$, then he would also go broke if he were playing and
ignored the goal.  So the probability that he will lose if he keeps playing
without stopping at any goal $T$ must be at least as large the probability
he loses when he has a goal $T>n$.

But we know that in a fair game, the probability that he loses is $1 -
n/T$.  This number can be made arbitrarily close to 1 by choosing a
sufficiently large value of $T$.  Hence, the probability of his losing
while playing without any goal has a lower bound arbitrarily close to 1,
which means it must in fact be 1.
\end{proof}

So even if the gambler starts with a million dollars and plays a perfectly
fair game, he will eventually lose it all with probability 1.  In fact, if
the game is unfavorable, then~(\ref{wnsol}) and~(\ref{ExQ}) imply that for
any fixed $p<1/2$, his expected time to go broke is essentially
proportional to his initial capital, \ie $\Theta(n)$.

But there is good news: if the game is fair, he can expect to play for a
very long time before going broke; in fact, he can expect to play forever!

\begin{lemma}\label{play forever}
If the gambler starts with one or more dollars and plays a fair game until
he goes broke, then he can expect to play forever.
\end{lemma}

\begin{proof}
Consider the gambler's ruin game where the gambler starts with initial
capital $n$, and let $u_n$ be the expected number of bets for
the \emph{unbounded} game to end.  Also, choose any $T \geq n$, and as
above, let $e_n$ be the expected number of bets for the game to end when
the gambler's goal is $T$.

The unbounded game will have a larger expected number of bets compared to
the bounded game because, in addition to the possibility that the gambler
goes broke, in the bounded game there is also the possibility that the
game will end when the gambler reaches his goal, $T$.  That is,
\[
u_n \geq e_n.
\]
So by~(\ref{Tn}), 
\[
u_n \geq n(T-n).
\]
But $n \geq 1$, and $T$ can be any number greater than or equal to $n$, so
this lower bound on $u_n$ can be arbitrarily large.  This implies that
$u_n$ must be infinite.

Now by Lemma~\ref{go broke}, with probability one the unbounded game ends
when the gambler goes broke.  So the expected time for the unbounded game
to \emph{end} is the \emph{same} as the expected time for the gambler to
\emph{go broke}.  Therefore, the expected time to go broke is infinite.
\end{proof}

In particular, even if the gambler starts with just one dollar, he can
expect to play forever!  Of course, this does not mean that it is likely
he will play for long.  For example, there is a 50\% chance he will lose
the very first bet and go broke right away.

Lemma~\ref{play forever} says that the gambler can expect to play forever,
while Lemma~\ref{go broke} says that with probability 1 he will go broke.
These Lemmas sound contradictory, but our analysis showed that they are
not.

\subsection{Infinite Expectation}

So what are we to make of such a random variable with infinite
expectation?  For example, suppose we repeated the experiment of having
the gambler make fair bets with initial stake one dollar until he went
broke, and we kept a record of the average number of bets per experiment.
Our theorems about deviation from the mean only apply to random variables
with finite expectation, so they don't seem relevant to this situation.
But in fact they are.

For example, let $Q$ be the number of bets required for the gambler to go
broke in a fair game starting with one dollar.  We could use some of our
combinatorial techniques to show that
\begin{equation}\label{Qm}
\pr{Q=m} = \Theta(m^{-3/2}).
\end{equation}
This implies that
\[
\expect{Q} = \Theta(\sum_{m=1}^\infty m\cdot m^{-3/2}) = 
\Theta(\sum_{m=1}^\infty m^{-1/2}).
\]
We know this last series is divergent, so we have another proof that $Q$
has infinite expectation.

But suppose we let $R \eqdef Q^{1/5}$.  Then the estimate~(\ref{Qm}) also
lets us conclude that
\[
\expect{R}  =  \Theta(\sum_{m=1}^\infty m^{-13/10})
\]
and
\[
\expect{R^2}  = \Theta(\sum_{m=1}^\infty m^{-11/10}).
\]
Since both these series are convergent, we can conclude that
$\variance{R}$ is finite.  Now our theorems about deviation can be applied
to tell us that the average \emph{fifth root} of the number of bets to go
broke is very likely to converge to a finite expected value.

We could also use our techniques to estimate $\pr{Q_k = m}$, where $Q_k$
is the sum of $k$ independent gambler's ruin games starting with one
dollar.  So $\expect{Q_k/k} = \expect{Q}$ remains infinite, but
using~(\ref{Qm}), we could also show that $\expect{Q_k/k^2}$ is finite.
Our bounds on deviation from a finite mean now tell us that when the
gambler plays $k$ games, his average time to go broke will very likely
grow proportionally to $k$.

We won't go further into the details, but the moral of this discussion is
that our results about deviation from a finite mean can still be applied
to natural models like random walks where variables with infinite
expectation may play an important role.

\end{document}
