Gambler's Ruin

Medium3–4 hrsRandom WalkBoundary ConditionsRuin ProbabilityRecurrence

Overview

Gambler's ruin is the archetypal first-passage problem. It arises in quant interviews any time someone asks about 'probability of reaching target X before going broke' or 'which player is favored in a repeated-bet scenario.' The key insight is that pₖ satisfies a linear recurrence that's easy to solve. The fair-game case (p=½) gives the beautiful result that probability of winning equals starting fraction of the total pot. The biased case shows exponential decay in your favor — even a tiny house edge makes ruin almost certain over the long run.

How to Recognize

→'Player has $k, plays until bankrupt or reaches $N'
→'What is the probability of reaching level a before level b?'
→'Two players bet repeatedly — who wins?'
→Any absorbing-barrier random walk problem

Step-by-Step Approach

1.Define pₖ = P(reaching N | current wealth = k)
2.Write recurrence: pₖ = p·pₖ₊₁ + (1-p)·pₖ₋₁ with p₀=0, p_N=1
3.For fair game (p=½): solution is linear pₖ = k/N
4.For biased game (p≠½): solution is pₖ = (1 - (q/p)^k) / (1 - (q/p)^N) where q=1-p
5.Expected duration: for fair game E[T | start at k] = k(N-k)

Key Formulas

p_k = k/N \quad

(fair game:

p=\tfrac{1}{2}

)

p_k = \frac{1-(q/p)^k}{1-(q/p)^N} \quad

(biased:

p \ne \tfrac{1}{2}

q=1-p

)

E[\text{duration} \mid X_0=k] = k(N-k) \quad

(fair game)

P(\text{ruin before doubling} \mid \text{start at } k, \text{target } 2k) = (q/p)^k \cdot \frac{1-(q/p)^k}{1-(q/p)^{2k}}

Worked Examples

0Quick Example

Casino: p=18/38 (roulette, bet on red). Start with

10, target

20. P(success) = (1-(20/18)^{10})/(1-(20/18)^{20}) ≈ 1/1022 + ... ≈ 10.6%. You'll almost certainly go bust.

Problem

Alice has $3, Bob has$ 7. They bet $1 each round on a fair coin flip. What is P(Alice wins all$ 10)?

Solution

Total pot N=10, Alice starts at k=3.

Fair game (p=½), so pₖ = k/N.

P(Alice wins) = 3/10 = 30%.

Sanity check: P(Bob wins) = 7/10 = 70% (proportional to starting wealth). Makes sense!

Answer

$P(\text{Alice wins}) = 3/10 = 30\%$ . In a fair game, your probability of winning equals your share of the total pot.

Common Mistakes

!
Confusing q/p > 1 (house edge, bad for you) vs q/p < 1 (your edge). When p > ½, q/p < 1 and the formula gives you high probability of winning.
!
Applying the fair-game formula to biased games. pₖ = k/N ONLY when p=½.
!
Forgetting boundary conditions: p₀ = 0 (ruined) and p_N = 1 (won).

Practice Problems

Click "Show Answer" to reveal

In a game, you win $1 with probability 2/3 and lose$ 1 with probability 1/3. Starting with $2, what is P(reaching$ 5 before going broke)?

Hint: q/p = (1/3)/(2/3) = 1/2. Use the biased gambler's ruin formula with k=2, N=5.

You play a fair game (p=½). You start with $k and want to reach$ N. What is the expected number of bets until the game ends?

Hint: Set up Tₖ = expected duration from state k. Tₖ = 1 + ½Tₖ₋₁ + ½Tₖ₊₁, with T₀ = T_N = 0.

Back to Study Plan

First-Step Analysis Recursive Game Values