Reaching Ruin In Limited Turns 

That time of year thou mayst in me behold 
When yellow leaves, or none, or few, do hang 
Upon those boughs which shake against the cold, 
Bare ruin'd choirs, where late the sweet birds sang. 

In another note we discussed the classic “gambler’s ruin” problem, which consists of a gambler who has current holding of h dollars, and either wins or loses 1 dollar on each turn, with probabilities a and 1a respectively. In the usual form of this problem, the gambler intends to continue playing until he either reaches a fixed goal or N dollars or he is “ruined” (i.e, he goes broke by reaching zero dollars). We are asked to determine the probability of ruin for any given values of h, N, and a. For any given values of N and a let p_{h} denote the probability of ruin given current holdings of h dollars. We immediately have the relation 

_{} 

which we can solve explicitly for p_{h}, as described in the previous note. 

A variation on this problem is to consider the case where the gambler with holdings h is only going to play for n more turns or until he goes broke or reaches N, whichever comes first. For this problem we let p_{n,h} denote the probability of ruin (before reaching N) given current holdings of h dollars and given that the gambler has n turns remaining. (Note that he may not use all of these turns if he reaches 0 or N before using all his turns.) By the same reasoning as before, but taking into account the fact that n is decrement by 1 on each turn, we have the relation 

_{} 

We know that p_{0,0} = 1 and p_{0,h} = 0 for all h > 0. We also know p_{n,0} = 1 for all n > 0. From these boundary conditions we can calculate all other probabilities using the above formula. For the simple case a = 1/2 the formula is 

_{} 

so the denominators of p_{n,h} are 2^{n} and the numerators form an array where each element is the sum of the two elements in the neighboring columns of the previous row. A portion of this infinite array is shown below. 

_{} 

So, for example, the probability of ruin for a gambler with h = 2 dollars who has (up to) n = 6 turns remaining is p_{6,2} = 29/64. Note that this table is for N > 8. The Nth column will be populated with zeros, since when h = N the gambler has achieved the target and his probability of ruin before reaching the target is therefore 0. 

We would like to find a more explicit expression for p_{n,h}. One approach would be to seek a generating function for the hth column of probabilities. Putting b = 1  a for convenience, let us write equation (1) explicitly for n = 1, 2, 3, … as 

_{} 

If we multiply both sides of the nth equation in this sequence by x^{n} where x is some arbitrary parameter, then these equations become 

_{} 

If we sum up all these equations together, we get 

_{} 

Notice that we written the summation on the left side beginning at j = 0, even though the left side terms in the sequence actually start at j = 1. This is permissible, because the equations apply only for h > 0 (noting that one of the terms on the right side involves h – 1), and we’ve already seen that p_{0,h} = 0 for all h >0. Now, if we define a generating function P_{h}(x) by the infinite series 

_{} 

then the summation equation can be written as 

_{} 

Thus for any choice of the parameter x we have the recurrence relation 

_{} 

which has the characteristic equation 

_{} 

with the roots 

_{} 

If these two roots are distinct, then we know P_{h}(x) is of the form 

_{} 

where A(x) and B(x) are arbitrary functions of x, to be determined by the boundary conditions. Recalling that pn,0 = 1 for all n (as seen from the zeroth column of the table above), we have as one boundary condition 

_{} 

For the second boundary condition, we stipulate that the probability of ruin is zero if our current holdings h equal the target N, so we have P_{N}(x) = 0. These conditions imply 

_{} 

from which we get 

_{} 

To evaluate this in the limit as N goes to infinity, it’s useful to notice that l_{1}l_{2} = b/a, so this equation can be written as 

_{} 

Since we’re free to choose x between 0 and 1, we have l_{1} > l_{2}, and so in the limit as N increases, the right hand factor in this expression approaches l_{1}^{N}^{h}/l_{1}^{N} = 1/l_{1}^{h}. Therefore, remembering that l_{1}l_{2} = b/a, we have 

_{} 

To illustrate, consider the case with a = b = 1/2, and suppose the gambler’s current holdings are 6 dollars. What is the probability of ruin for various values of n? To determine this, we develop the series of the generating function P_{3}(x) as follows: 

_{} 

As can be confirmed from the previous table, the coefficient if x^{n} in this expression equals p_{n,3}, so this is indeed the generating function for those probabilities. With this we can extrapolate the values of p_{n,h} for negative values of h, giving the results shown below for the case a = 1/2. 

_{} 

To give a more explicit expression for the probabilities, notice that each value can be expressed as a sum of alternating values on a previous row with binomial coefficients, as is clear from the basic recurrence relation. It is simplest to trace the values back to the row n = 0, where all the nonzero values are 2, with the exception of the value p_{0,0} = 1. From this it is easy to infer the result 

_{} 

For example, we have 

_{} 

It’s worth noting that our calculations above were for the probability of ruin within n turns, not necessarily in exactly n turns. If we change the problem, to ask for the probability of ruin in exactly n turns, given current holdings h, then the recurrence relation described above still applies. The only difference is in the boundary condition for P_{0}(x), because in this case we still have p_{0,0} = 1 but now we have p_{n,0} = 0 for all n > 0. This is because if our holdings are already zero while the number n of remaining turns is greater than zero, we obviously didn’t reach ruin in exactly n turns. Thus the first boundary condition for this modified problem is P_{0}(x) = 1 instead of 1/(1x). The upper boundary condition, though, is still P_{N}(x) = 0. The effect of changing the first boundary condition is simply to remove the leading factor 1/(1x) from the results, so we have 

_{} 

and 
_{} 

The result for h = 3 is 

_{} 

The coefficients of the even powers of x are all zero, which stands to reason, because if the current holdings are odd (h = 3 in this case), there is zero probability of reaching ruin in exactly an even number of turns. 
