The Gambler's Ruin Problem
Problem
The gambler’s ruin problem is a type of random walk where two players bet a finite amount of money and the game is repeated until one of them goes bankrupt.
If you are one of the players, then according to the diagram above, the probability of you winning is $p$ and the probability of losing is $(1-p)$. State $0$ is when you go bankrupt, and state $N$ is when you win all the money from your opponent, meaning the game does not continue. This is represented by the probability of moving to oneself in $0$ and $N$ being $1$. $i$ can be seen as your initial money when starting the game.
Basically, if $\displaystyle p \ne {{1} \over {2}}$ or $\displaystyle i \ne {{N} \over {2}}$, the game is not fair. The game doesn’t end until one person goes bankrupt. A question of mathematical interest might be “what are the chances of you bankrupting your opponent and winning when you start with $i$ amount of money?”. However, one might first ask “why play such an unfair and extreme game?”.
But this is only a question one might pose when viewing the gambler’s ruin problem strictly as a game, whereas in reality, fair fights are even harder to come by. This could be seen as the struggle between large corporations with significant capital and protected small businesses, or as total warfare between nations that produce similar resources. There are times when one must engage in an unfavorable fight, and naturally, one would be curious about their chances of winning.
Returning to mathematics, our interest lies in calculating the probability ‘of bankrupting the opponent and taking all the money when the initial capital is $i$ and the winning probability is $p$ ‘, which is $P_{i}$. For convenience, let’s call the situation ‘of bankrupting the opponent and taking all the money’ a ‘win’.
Solution
Based on the definition of $P_{i}$, we have $P_{0} = 0$ and $P_{N} = 1$.
Part 1.
$P_{ i }$ can be seen as the probability of winning the first game with the probability of $p$ and then starting anew from $( i+1 )$ to win, plus the probability of losing the first game with the probability of $(1-p)$ and then starting anew from $( i-1 )$ to win. Mathematically, this is represented as $P_{ i } = p P_{ i + 1 } + (1 - p ) P_{ i - 1 }$. If we split the left-hand side into $p$ and $(1-p)$, then $$P_{ i } = (p + 1 - p ) P_{i} = p P_{i} + (1 - p) P_{i}$$ thus, $$ \begin{align*} & P_{ i } =& p P_{ i + 1 } + (1 - p ) P_{ i - 1 } \\ \implies& p P_{i} + (1 - p) P_{i} &= p P_{ i + 1 } + (1 - p ) P_{ i - 1 } \\ \implies& p \left( P_{i+1} - P_{i} \right) =& (1 - p) \left( P_{i} - P_{i-1} \right) \\ \implies& \left( P_{i+1} - P_{i} \right) =& {{1-p} \over {p}} \left( P_{i} - P_{i-1} \right) \end{align*} $$
Recursive solving leads to $\displaystyle P_{i} - P_{i-1} = \left( {{1-p} \over {p}} \right)^{i-1} \left( P_{1} - P_{0} \right)$, but since $P_{0} = 0$, $$\displaystyle P_{i} - P_{i-1} = \left( {{1-p} \over {p}} \right)^{i-1} P_{1}$$
Part 2.
$$P_{1} - P_{0} = \left( {{1-p} \over {p}} \right)^{0} P_{1} \\ P_{2} - P_{1} = \left( {{1-p} \over {p}} \right)^{1} P_{1} \\ P_{3} - P_{2} = \left( {{1-p} \over {p}} \right)^{2} P_{1} \\ P_{i} - P_{i-1} = \left( {{1-p} \over {p}} \right)^{i-1} P_{1} $$
Adding the equations side by side, the left-hand side becomes $$( P_{1} - P_{0} ) + ( P_{2} - P_{1} ) + \cdots + ( P_{i} - P_{i-1} ) = P_{i} - P_{0} = P_{i}$$ and the right-hand side becomes $$\displaystyle \sum_{k=1}^{i} \left( {{1-p} \over {p}} \right)^{k-1} P_{1} = {{ 1 - \left( {{1-p} \over {p}} \right)^{i} } \over {1 - \left( {{1-p} \over {p}} \right) }} P_{1}$$ Simplifying, $$\displaystyle P_{i} = {{ 1 - \left( {{1-p} \over {p}} \right)^{i} } \over {1 - \left( {{1-p} \over {p}} \right) }} P_{1}$$
Part 3.
Since $P_{N} = 1$, $$ 1 = P_{N} = {{ 1 - \left( {{1-p} \over {p}} \right)^{N} } \over {1 - \left( {{1-p} \over {p}} \right) }} P_{1} $$ Therefore, $$ P_{1} = {{1 - \left( {{1-p} \over {p}} \right) } \over { 1 - \left( {{1-p} \over {p}} \right)^{N} }} $$ By substituting $P_{1}$ into the equation obtained in Part 2., $$ P_{i} = {{ 1 - \left( {{1-p} \over {p}} \right)^{i} } \over {1 - \left( {{1-p} \over {p}} \right) }} \cdot {{1 - \left( {{1-p} \over {p}} \right) } \over { 1 - \left( {{1-p} \over {p}} \right)^{N} }} = {{ 1 - \left( {{1-p} \over {p}} \right)^{i} } \over {1 - \left( {{1-p} \over {p}} \right)^{N} }} $$ is obtained.
■