Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
4  
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
2  
@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
show 2 more comments

3 Answers

up vote 7 down vote accepted

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.

share|improve this answer
    
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
add comment

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}$

share|improve this answer
    
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
2  
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
show 1 more comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.