# Gambler´s ruin problem

A gambler starts with an initial fortune of 9. He wins 1 with p=1/3 and losses 1 with q=2/3. The game ends when the gambler looses all of his money or when we reaches 15. What is the probability that the gambler will win the game, but that he also reached 3 in certain point of time?

• Gambler starts with some fortune $k$
• and the game ends if he loses all the money or if he wins $15. Let$p_k$be the probability that starting with fortune$k$, the gambler will win. (Here$0 \leq k \leq 15$) When he has fortune$k$, there are two possibilities: • With probability 1/3, he wins and has fortune$k+1$, or • with probability 2/3, he loses and has fortune$k-1$. This lets us set up the recurrence $$p_k = \frac{1}{3} p_{k+1} + \frac{2}{3} p_{k-1}.$$ Moreover, •$p_{15} = 1$(since we win at that point), and •$p_0 = 0$(since we lost all the money). Usual methods to solve recurrence allows one to find$p_k = \frac{2^k - 1}{2^{15}-1}$for$0 \leq k \leq 15$. For the given problem, we can formulate a similar set up as above: • Gambler starts with some fortune$k$• He wins 1 with probability 1/3 and loses 1 with probability 2/3 • and the game ends if he loses all the money or if he reaches 15. Let$q_k$be the probability that starting with fortune$k$, the gambler will win and reach 3 at some point of time. We can again try to formulate a recurrence relation. For$3 \leq k \leq 15$, with gambler starting with fortune$k$, • With probability 1/3, he wins and has fortune$k+1$, or • with probability 2/3, he loses and has fortune$k-1$. Thus we have the same recurrence $$q_{k} = \frac{1}{3}q_{k+1} + \frac{2}{3} q_{k-1}.$$ However, the boundary conditions changed: •$q_3 = p_3 = \frac{2^3-1}{2^{15}-1}$, since once we hit 3, we only need to make sure the gambler will eventually win. •$q_{15} = 0$, since we already finished the game (by reaching 15), but never got to 3. Solving the recurrence, we have $$q_k = \frac{(2^3-1)(2^{15} - 2^k)}{(2^{15}-1)(2^{15}-2^3)}$$ Substituting$k = 9$gives$q_9 = 64/304265\$.