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?
 A: 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.
A: 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}$
A: 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.
