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?

  • 0
    @Sasha: Nice big fraction! Are you using arbitrary-precision rational numbers to compute $p$? Did you compute the Jordan canonical form of matrix $P$?2012-09-23

3 Answers 3

7

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.

  • 0
    @David: See http://en.wikipedia.org/wiki/Linear_recurrence#Linear_homogeneous_recurrence_relations_with_constant_coefficients.2012-09-23
3

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

  • 0
    @Navin: You can get the exact value for an infinite bankroll using the formula (25/(k+25))*C(2k+24,k)*.25^(25+k)*.75^k, summing from k = 0 to infinity, to get an ans of 1.1802e-122012-09-24
1

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.