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 α and 1–α 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 α. For any given values of N and α 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 α = 1/2 the formula is

so the denominators of p_n,h are 2ⁿ 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 β = 1 – α 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ⁿ 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 p_n,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 λ₁λ₂ = β/α, so this equation can be written as

Since we’re free to choose x between 0 and 1, we have |λ₁| > |λ₂|, and so in the limit as N increases, the right hand factor in this expression approaches λ₁^N–h/λ₁^N = 1/λ₁^h. Therefore, remembering that λ₁λ₂ = β/α, we have

To illustrate, consider the case with α = β = 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₃(x) as follows:

As can be confirmed from the previous table, the coefficient if xⁿ 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 α = 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 non-zero 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₀(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₀(x) = 1 instead of 1/(1–x). 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/(1-x) 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.

Return to MathPages Main Menu