The Gambler's Ruin

Here’s an interesting probability question that I’ve found in Adrian Torchiana’s Probability Math Puzzles app (highly recommended!) back in high school.

You find $2 in your pocket and decide to go gambling. Fortunately, the game you’re playing has very favorable odds: each time you play, you gain $1 with probability 3/4 and lose $1 with probability 1/4.

Suppose you continue playing so long as you have money in your pocket. If you lose your first two bets, you go broke and go home after only two rounds; but if you win forever, you’ll play forever.

What’s the probability you’ll eventually go broke?

At first glance, it seems like everyone will eventually go broke given that people have to play the game forever.

Surprisingly, this is not the case!

This is a very tricky problem! I wasn’t able to solve the problem at the time without this hint given in the app.

Reveal the Hint

Starting at any positive initial wealth \( x \), think about the probability of ever reaching state \( \left( x - 1 \right) \). The answer you're looking for is just the square of the probability: to go broke you have to at some point reach a wealth of \( $1 \), and then, having gotten there, at some point reach a wealth of \( $0 \).

Let’s look at two ways in which we can solve the problem. Starting with the “dumb” method of simulating the gambler’s outcomes through code.

“Solve” using Simulations

We can attempt to simulate plays similar to the graph above. Given the max number of plays and the number of samples, we can estimate the probability to a degree of accuracy.

To increase the accuracy of our estimate we have to increase the max number of plays and the number of samples, however, we must restart the simulation when we change our parameters. Fortunately, we have a better approach that automagically increases the accuracy by increasing the max number of plays and the number of samples the longer the script runs.

Running an arbitrarily large number of samples, all potentially running infinitely long, can cause issues. A technique we can use is called “dovetailing” which involves running the first step of the first sample, and then running the second step of the first sample and the first step of the second sample, and then running the third step of the first sample, the second step of the second sample and the first step of the third sample. This pattern continues indefinitely.

Solve using Algebra

Let \( p \left( n \right) \) be the probability of going broke starting with \( n \) dollars.

We have the following equation,

\[ p \left( n \right) = p \left( 1 \right) ^ n \]

This may seem unintuitive, but by understanding \( p \left( n \right) \) as doing \( p \left( 1 \right) \) \( n \) times might make a bit more sense.

Additionally, we need to come up with a recurrence relation.

We have the following base case,

\[ p \left( 0 \right) = 1 \]

And our recursive step is,

\[ p \left( n \right) = \frac{3}{4} p \left( n+1 \right) + \frac{1}{4} p \left( n-1 \right) \]

The \( \frac{3}{4} p \left( n+1 \right) \) part represents the probability of going broke after winning a dollar and the \( \frac{1}{4} p \left( n-1 \right) \) part represents the probability of going broke after losing a dollar.

Since finding \( p \left( 1 \right) \) will allow us to find \( p \left( n \right) \) and by extension \( p \left( 2 \right) \), we have the following equation that we need to solve,

\[ p \left( 1 \right) = \frac{3}{4} p \left( 2 \right) + \frac{1}{4} p \left( 0 \right) \]

Substituting \( p \left( 2 \right) \) with \( p \left( 1 \right) ^ 2 \) and \( p \left( 0 \right) \) with \( 1 \),

\[ p \left( 1 \right) = \frac{3}{4} p \left( 1 \right) ^ 2 + \frac{1}{4} \] \[ 3 p \left( 1 \right) ^ 2 - 4 p \left( 1 \right) + 1 = 0 \] \[ \left( 3 p \left( 1 \right) - 1 \right) \left( p \left( 1 \right) - 1 \right) = 0 \]

Ignoring the \( p \left( 1 \right) - 1 = 0 \) case,

\[ 3 p \left( 1 \right) - 1 = 0 \] \[ p \left( 1 \right) = \frac{1}{3} \]

Using \( p \left( n \right) = p \left( 1 \right) ^ n \), we can find \( p \left( 2 \right) \),

\[ p \left( 2 \right) = p \left( 1 \right)^2 = \left( \frac{1}{3} \right) ^ 2 = \frac{1}{9} \]

We can conclude that the exact odds of going broke is \( \frac{1}{9} \). Looks like the casino will quickly run out of business.