# What's the probability that I will earn \$25? I go to a casino with \$100. At the casino, I play a game in which I get \$1 if I win, and lose \$1 if I lose. The probability of me winning is $\frac{1}{4}$, and I must either win or lose every time I play this game. I will keep playing this game until I either earn \$25 or lose all my money. What's the probability that I will earn \$25?

I originally thought that the answer was $\frac{1}{4^{25}}$ because I must win a net 25 times. However, I realized that the problem was far more complicated because I could win and lose many times. Furthermore, if I go broke, I must stop playing. What tools in probability can I latch off of to solve this problem?

• You can use Markov chains to model this problem. Take a look at: mathpages.com/home/kmath084/kmath084.htm Sep 23, 2012 at 0:29
• The right tool is suggested here. +1, Rod. Sep 23, 2012 at 0:35
• Hmm, thanks! I've heard the term "markov chain" before. It sounds worth learning about. Sep 23, 2012 at 0:37
• I was reading about Markov chains on Wikipedia, and they look really cool. All these states and weighted arrows going around... must I use Markov chains or could I use say some variation of the counting principle (like a decreasing geometric series)? Sep 23, 2012 at 0:52
• @RodCarvalho Actually one can compute $\lim_{n \to \infty} P_n$ exactly. The exact probability is $$p = \frac{608266787714075607107376692496241000}{51537752073261959782417520537272864939460 3763001} \approx 1.18 \cdot 10^{-12}$$ Sep 23, 2012 at 1:07

Let $p_n$ be the probability that starting out with $n$ dollars you will reach $\$125$before you reach$\$0$. Then we have the recurrence

$$p_n=\frac14p_{n+1}+\frac34p_{n-1}$$

for $0\lt n\lt125$ and the boundary conditions $p_0=0$ and $p_{125}=1$. The characteristic equation of the recurrence is

$$\frac14\lambda^2-\lambda+\frac34=0$$

with solutions $\lambda=1$ and $\lambda=3$. Thus the general solution is

$$p_n=c_1+c_23^n\;,$$

and the boundary conditions yield $c_1+c_2=0$ and $c_1+c_23^{125}=1$, with solution $c_2=-c_1=1/(3^{125}-1)$, so

$$p_n=\frac{3^n-1}{3^{125}-1}$$

and

$$p_{100}=\frac{3^{100}-1}{3^{125}-1}\approx3^{-25}\approx1.18\cdot10^{-12}\;,$$

as given by Sasha in a comment.

• I think I can get $p_n=\frac14p_{n+1}+\frac34p_{n-1}$ by summing conditional probabilities. How do you get $\frac14\lambda^2-\lambda+\frac34=0$ from that? Furthermore, how do you get $p_n=c_1+c_23^n$? Sep 23, 2012 at 2:05
• @David: See en.wikipedia.org/wiki/…. Sep 23, 2012 at 2:13

I can play 25 games (win all) or play 27 games (win 26, lose 1) or play 29 (win 27, lose 2), ...

The probability of winning n games of k games played is $\binom{k}{n}(1/4)^n(3/4)^{k-n}$ so the total probability should be \begin{align} \sum_{x=0}^{\infty}\binom{25+2x}{x}(1/4)^{25+x}(3/4)^{x} \end{align} However this does not account for the fact that you can lose all your money for larger numbers of games played or you can overshoot \$25 so it is an upper bound:$2.3604707743147794*10^{-12}$• This also overcounts somewhat in situations where you reach$25$before you play the last game of the sequence (e.g. If you win the first$25$games, lose one, then win one, you're counting it both as winning$25$and as winning$26$of the first$27$) Sep 23, 2012 at 1:35 • @kevin darn, I forgot about that Sep 23, 2012 at 1:38 • Interestingly, my answer is about two times @Sasha 's answer (in the comment on the main post). Is this a coincidence? Sep 23, 2012 at 1:39 • What your answer computes is the expected number of times you are exactly 25 dollars ahead, ignoring the bankroll issues. Now suppose that at some point you reach +25. If you work through a similar argument to Joriki's recurrence relation, you'll see you have a$1/2$chance of hitting +25 again given that you start from there. So the expected number of times you hit 25, given you hit it at least once, is$1+1/2+1/4+\dots=2$. This means your answer is exactly twice the correct answer to the infinite bankroll version. And the infinite and 100 dollar versions have almost the same answer. Sep 23, 2012 at 3:15 • @KevinCostello Nice explanation. – Did Sep 23, 2012 at 11:04 You have a$1$-dimensional random walk where you jump forward with probability$1/4$and backward with probability$3/4$. Let$X_k$be a random variable that denotes the amount of money you have after$k \geq 0$games. You start with 100 dollars, so$X_0 = 100$with probability equal to$1$, i.e., there is no uncertainty about the initial state so$\mathbb{P} (X_0 = 100) = 1$. Since you lose 1 dollar with probability$3/4$and win a dollar with probability$1/4$, we have that$\mathbb{P} (X_1 = 99) = 3/4$and$\mathbb{P} (X_1 = 101) = 1/4$. To obtain the probability mass function for$k \geq 2$, use the matrix formulation of Markov chains $$\pi_{k+1}^T = \pi_k^T P$$ where$\pi_0$is the probability vector whose$100$-th component is one and the rest are zero. Matrix$P$is tridiagonal. You want to compute$\pi_{\infty}^T = \pi_0^T P^{\infty}$. Make the end states absorbing or sinks, which is to say that the diagonal of$P$will be$(1,0,\dots,0,1)\$. For more information, take a look at this book.