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 – Rod Carvalho Sep 23 '12 at 0:29
The right tool is suggested here. +1, Rod. – ncmathsadist Sep 23 '12 at 0:35
Hmm, thanks! I've heard the term "markov chain" before. It sounds worth learning about. – David Faux Sep 23 '12 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)? – David Faux Sep 23 '12 at 0:52
@RodCarvalho Actually one can compute $\lim_{n \to \infty} P_n$ exactly. The exact probability is $$p = \frac{608266787714075607107376692496241000}{515377520732619597824175205372728649‌​39460 3763001} \approx 1.18 \cdot 10^{-12}$$ – Sasha Sep 23 '12 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$? – David Faux Sep 23 '12 at 2:05
@David: See en.wikipedia.org/wiki/…. – joriki Sep 23 '12 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$) – Kevin Costello Sep 23 '12 at 1:35 @kevin darn, I forgot about that – Navin Sep 23 '12 at 1:38 Interestingly, my answer is about two times @Sasha 's answer (in the comment on the main post). Is this a coincidence? – Navin Sep 23 '12 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. – Kevin Costello Sep 23 '12 at 3:15 @KevinCostello Nice explanation. – Did Sep 23 '12 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.

-