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 1-a 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 ph denote the probability of ruin given current holdings of h dollars. We immediately have the relation which we can solve explicitly for ph, 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 pn,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 p0,0 = 1 and p0,h = 0 for all h > 0. We also know pn,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 pn,h are 2n 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 p6,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 pn,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 xn 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 p0,h = 0 for all h >0. Now, if we define a generating function Ph(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 Ph(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 PN(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 l1l2 = b/a, so this equation can be written as Since we’re free to choose x between 0 and 1, we have |l1| > |l2|, and so in the limit as N increases, the right hand factor in this expression approaches l1N-h/l1N = 1/l1h. Therefore, remembering that l1l2 = 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 P3(x) as follows: As can be confirmed from the previous table, the coefficient if xn in this expression equals pn,3, so this is indeed the generating function for those probabilities.  With this we can extrapolate the values of pn,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 non-zero values are 2, with the exception of the value p0,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 P0(x), because in this case we still have p0,0 = 1 but now we have pn,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 P0(x) = 1 instead of 1/(1-x). The upper boundary condition, though, is still PN(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