8. Gambler’s Ruin

Suppose we play a game where we start with £1. Each turn we flip a coin. If we get a heads, we gain £1 and if we get a tails, we lose £1. The goal of the game is to make £10. What is the probability we win (get a total of £10) versus going broke (end with £0).

To make the problem more general, suppose the probability of getting a heads is \(p\) and the probability of getting a tails is \(1 - p = q\). Suppose also we start the game with \(i\) pounds and the aim is to win \(N\) pounds.

So, the aim is to predict the probability of going bust or making \(N\) pounds given we start the game with \(i\) pounds. Let \(P_i\) be the probability of winning having started with \(i\) pounds. The outcome of the \(n\)-th coin flip is not dependent on the \(n-1\)-th coin flip. Therefore, we can say,

\[\begin{equation} P_i = p P_{i + 1} + q P{i - 1}. \end{equation}\]

Now, we can recursively calculated \(P_i\). Since \(p + q = 1\), we can rewrite this as,

\[\begin{equation} p P_i + q P_i = p P_{i + 1} + q P_{i - 1}. \end{equation}\]

Rearranging this becomes,

\[\begin{split}\begin{align} p P_{i + 1} - p P_i & = q P_i - q P_{i - 1} \\ P_{i + 1} - P_i & = \frac{q}{p} (P_i - P_{i - 1}) \\ \end{align}\end{split}\]

Using \(i = 1\), we have \(P_0 = 0\) since it is impossible to win the game if we are already broke. Therefore, we get,

\[\begin{split}\begin{equation} P_2 - P_1 = \frac{q}{p} \left(P_1 - P_0 \right) = \frac{q}{p} P_1. \\ \end{equation}\end{split}\]

Using this fact, for \(i = 2\) we get,

\[\begin{split}\begin{align} P_3 - P_2 & = \frac{p}{q} \left(P_1 - P_0 \right) \\ & = \frac{p^2}{q^2} P_1. \end{align}\end{split}\]

For \(i = 3\), we have,

\[\begin{split}\begin{align} P_4 - P_3 & = \frac{p}{q} \left(P_2 - P_3 \right) \\ & = \frac{p^3}{q^3} P_1. \end{align}\end{split}\]

Following this pattern for \(i = n\), we get,

\[\begin{split}\begin{align} P_{n + 1} - P_n = \frac{p^n}{q^n} P_1. \\ P_{n + 1} = \frac{p^n}{q^n} P_1 + P_n. \\ \end{align}\end{split}\]

Again by recursion.

\[\begin{split}\begin{align} P_{n + 1} & = \frac{p^n}{q^n} P_1 + \frac{p^{n - 1}}{q^{n - 1}} P_1 + P_{n - 1} \\ P_{n + 1} & = \frac{p^n}{q^n} P_1 + \frac{p^{n - 1}}{q^{n - 1}} P_1 + \frac{p^{n - 2}}{q^{n - 2}} P_1 + P_{n - 2} \\ \vdots & \\ P_{n + 1} - P_1 & = \sum_{k = 1}^n \frac{p^k}{q^k} P_1 \end{align}\end{split}\]

Using the fact that \(P_N = 1\), we have,

\[\begin{split}\begin{align} P_N - P_1 & = \sum_{k = 1}^{N - 1} \frac{p^k}{q^k} P_1 \\ 1 & = \sum_{k = 0}^{N - 1} \frac{p^k}{q^k} P_1 \\ \left(\sum_{k = 0}^{N - 1} \frac{p^k}{q^k}\right)^{-1} & = P_1 \\ \end{align}\end{split}\]