Gambler's Ruin

A bettor between two absorbing barriers: the fair game wins with probability k/N.

The idea

The gambler's ruin problem asks for the probability that a gambler reaches a target fortune before going broke.

Theorem (Gambler's ruin).

A gambler starts with $\$k$ and bets $\$1$ at a time on a fair coin, stopping the moment the fortune reaches either $\$0$ or a target $\$N$, where $0 \le k \le N$. The probability of reaching $\$N$ before $\$0$ is $p_{k} = \frac{k}{N},$ and the expected number of bets before the game stops is $k\,(N - k)$.

The setting is more general than gambling: a walk between two absorbing barriers, started in between, also describes a queue that either empties or fills, and a population that either dies out or reaches its ceiling. The method matters as much as the answer, because it applies to any process that has no memory: after any bet, the game ahead is a fresh gambler's ruin started at the new stake, because the coin retains no memory of how the fortune got there.

Ways to work on it

• Walkthrough. Boundary values, the first-bet recurrence, and the fair game's linear solution.
• Proof. Derive the fair game's win probability by conditioning and telescoping, then its expected duration.
• Practice. Win, ruin, and expected-duration computations for the fair game.
• Hardest. Compute win probabilities when the game is biased.

Not sure where to start? Take the ten-question placement test.