Gambler's ruin. A gambler makes a sequence of independent

QUESTION:

Gambler's ruin. A gambler makes a sequence of independent bets. In each bet, he wins $1 with probability p, and loses $1 with probability 1 - p. Initially, the gambler has $k, and plays until he either accumulates $n or has no money left. What is the probability that the gambler will end up with $n? Solution. Let us denote by A the event that he ends up with $n, and by F the event that he wins the first bet. Denote also by Wk the probability of event A, if he starts with $k. We apply the total probability theorem to obtain Wk = P(A I F)P(F) + P(A I FC)P(FC) = pP(A I F) + qP(A I FC). 0< k < n, where q = 1 - p. By the independence of past and future bets, having won the first bet is the same as if he were just starting now but with $(k+l), so that P(A I F) = Wk+l and similarly P(A I FC) = Wk- l . Thus, we have Wk = PWk+l + qwk- l, which can be written as 0< k < n, where r = q/p. We will solve for Wk in terms of p and q using iteration, and the boundary values Wo = 0 and Wn = 1. We have Wk+ l - Wk = r k (wl - wo), and since Wo = 0, k k-l k k Wk+l = Wk + r WI = Wk -l + r WI + r WI = WI + rWI + . .. + r WI . The sum in the right-hand side can be calculated separately for the two cases where r = 1 (or p = q) and r =J. 1 (or p =J. q). We have if p =J. q. if p = q. Since Wn = 1, we can solve for WI and therefore for Wk: r -r if p =J. q, 1 - r n ' WI = 1 -. if p = q, n so that c-rk if p =J. q, 1 - rn Wk = k - , if p = q.