The Gambler's Ruin

Consider a game that gives a probability q of winning 1 dollar and 
a probability (1-q) of losing 1 dollar.  If a player begins with
10 dollars, and intends to play the game repeatedly until he either 
goes broke or increases his holdings to 20 dollars, what is his 
probability of going broke?

This is commonly known as the Gambler's Ruin problem.  For any given
amount h of current holdings, the conditional probability of going 
broke before reaching 20 dollars is independent of how we acquired
the h dollars, so there is a unique probability p_h of going broke
on the condition that we currently hold h dollars.  Of course, we
can immediately set  p_0 = 1.0  and  p_20 = 0.0.  The problem is to
determine the values of p_h for h between 0 and 20.

The key point to realize is that in order to arrive at holdings equal
to h dollars after playing a round of the game, we must have held 
either h+1 or h-1 dollars just prior to that round.  When we were in
one of those states we had (by definition) a probability of p_{h+1}
or p_{h-1} respectively of going broke.  Also, the conditional
probability that we just came from the state "h-1" is q (which is
the probability that we won the round), and the probability that
we just came from state "h+1" is (1-q).  Now, the probabililiy of
going broke from the state p_h is just the linear combination of
these two

          p_h   =   q * p_{h-1}  +  (1-q) * p_{h+1}            (1)

This gives us a second-order linear recurrence relation that must 
be satisfied by the values of p_h.  If q and 1-q are distinct (meaning
that q is not equal to exactly 1/2), the general form of such a
recurrence is a linear combination of successive powers of any two 
independent particular solutions.  One particular solution is 
obviously  p_h = 1  for all h.  Also, it's not hard to verify that
p_h = [(1-q)/q]^h  is also a particular solution.  Therefore, the
general solution of the recurrence is of the form

            p_h  =  A [1]^h  +  B [(1-q)/q]^h

where A and B are constants to be determined by our two boundary
conditions, p_0 = 1.0  and  p_20 = 0.0.  Inserting these values
gives the conditions

                   1  =  A  +  B

                   0  =  A  +  B [(1-q)/q]^20

Setting r = (1-q)/q, this implies

                  r^20                   1
        A  =  - --------       B  =  ---------
                1 - r^20             1 - r^20

Therefore, if a player is currently holding h dollars, his probability 
of going broke before reaching 20 dollars is

                        r^h  -  r^20
              p_h  =  ----------------
                         1  -  r^20

This was based on the assumption that q does not exactly equal 1-q,
so that r is not equal to 1.  If, on the other hand, q=1/2, we see
that our two particular solutions 1^h and r^h are not independent.
In this case the characteristic polynomial has duplicate roots, but
another independent solution of the recurrence (1) is given by 
p_h = h.  Therefore, the general form of the solution is A + Bh,
and our boundary conditions require A = 1 and B = -1/20, so the
total solution in this special symmetrical case is

                                   h
                    p_h  =  1  -  ---
                                   20

Hence, if we begin with 10 dollars, we have a 50% chance of going
broke before reaching 20 dollars.  

Obviously we can replace 20 with any other threshold we choose.  For 
any given initial holdings, if we increase our upper target from 20 
to some larger number, we see that our probability of going broke 
before reaching that number also increases.  If we have no "quit 
while we're ahead" target, and simply intend to play the game 
indefinitely, our probability of eventually going broke approaches 
1.0 (which presumably is why this problem is called the Gambler's 
Ruin).  

In the above discussion we considered only the case when each step
changed our holdings by one unit, up or down.  We can also treat the
more general problem of allowing more than two possible outcomes of
each round, and allowing the steps to be of arbitrary sizes.  For
example, we might consider a game that has three possible outcomes,
with probabilities a, b, and c changing our holdings by the amounts 
-1, +1, and +2 respectively.  In this case the same reasoning that
led to equation (1) leads to a third-order recurrence

    p_h   =  c * p_{h-2}  +  b * p_{h-1}  +  a * p_{h+1}        (2)

If we replace 20 with some arbitrary fixed threshold T, then we have 
three boundary conditions

      p_0  =  1.0         p_T  =  0.0         p_{T+1}  =  0.0

noting that it's possible to end on either T or T+1.  In this more
general case we usually must simply solve the recurrence (2) in the
traditional way, by finding the roots of the characteristic polynomial,
and then expressing p_h as a linear combination of the hth powers of
those roots, subject to the boundary conditions.

This problem is essentially an example of a one-dimensional random 
walk.  Of course, we can also represent this by a Markov model,
and recursively generate the probabilities of having each particular
value of holdings after the nth round of play, beginning from some
specified initial holdings.  This is an example of a diffusion
process, with absorbing states at 0 and T, where all the probability
eventually accumulates.