4
$\begingroup$

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?

$\endgroup$
7
  • 4
    $\begingroup$ You can use Markov chains to model this problem. Take a look at: mathpages.com/home/kmath084/kmath084.htm $\endgroup$
    – Rod Carvalho
    Sep 23, 2012 at 0:29
  • $\begingroup$ The right tool is suggested here. +1, Rod. $\endgroup$
    – ncmathsadist
    Sep 23, 2012 at 0:35
  • $\begingroup$ Hmm, thanks! I've heard the term "markov chain" before. It sounds worth learning about. $\endgroup$
    – David Faux
    Sep 23, 2012 at 0:37
  • $\begingroup$ 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)? $\endgroup$
    – David Faux
    Sep 23, 2012 at 0:52
  • 2
    $\begingroup$ @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} $$ $\endgroup$
    – Sasha
    Sep 23, 2012 at 1:07

3 Answers 3

Reset to default
7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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$? $\endgroup$
    – David Faux
    Sep 23, 2012 at 2:05
  • $\begingroup$ @David: See en.wikipedia.org/wiki/…. $\endgroup$
    – joriki
    Sep 23, 2012 at 2:13
3
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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$) $\endgroup$
    – Kevin P. Costello
    Sep 23, 2012 at 1:35
  • $\begingroup$ @kevin darn, I forgot about that $\endgroup$
    – Navin
    Sep 23, 2012 at 1:38
  • $\begingroup$ Interestingly, my answer is about two times @Sasha 's answer (in the comment on the main post). Is this a coincidence? $\endgroup$
    – Navin
    Sep 23, 2012 at 1:39
  • 2
    $\begingroup$ 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. $\endgroup$
    – Kevin P. Costello
    Sep 23, 2012 at 3:15
  • $\begingroup$ @KevinCostello Nice explanation. $\endgroup$
    – Did
    Sep 23, 2012 at 11:04
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .