QUANT INTERVIEW PROBLEM·markov-chains·difficulty 3

Gambler's Ruin

Q: Why is the answer k/N so clean for the fair coin?

Because the gambler's wealth is a martingale. The optional stopping theorem then gives $\mathbb{E}[\text{final wealth}] = k$, and the final wealth is either 0 or N, which uniquely determines the probability of each.

Q: Does this apply to actual gambling?

Yes — with one crucial caveat: real casinos have p < 1/2, so the (q/p)^k formula applies. For roulette (p ≈ 18/38), the probability of doubling a £1000 bankroll to £2000 is about $(20/18)^{1000}$ tiny. Conversely, the probability of going broke while trying to double up is nearly 1.

Q: How does this generalise?

To multi-dimensional walks (Pólya's theorem says 1D and 2D fair walks are recurrent, 3D+ are transient), to continuous-time analogues (Brownian motion with absorbing barriers), and to option pricing (American options are gambler's ruin problems with known payoff functions).

Q: What's the expected duration?

For fair coin: $\mathbb{E}[T] = k(N-k)$ steps. Notice this peaks at k = N/2 — games starting at the midpoint take longest. This is a useful sanity check for any Markov-chain-style interview problem.

Starting with £k, what's your chance of reaching £N before going broke? The canonical absorbing-chain problem.

also known as: biased random walk problem · absorbing random walk

PROBLEM

A gambler starts with £k. On each round he bets £1 on a fair coin: heads wins £1, tails loses £1. He plays until he reaches £0 (ruin) or £N (goal). What is the probability of reaching £N before ruin?

ANSWER

k / N for a fair coin. For biased coin (p = P(heads) ≠ 1/2): P(reach N) = (1 - (q/p)^k) / (1 - (q/p)^N), where q = 1 - p.

CANONICAL SOLUTION

Let f(k) = P(reach N | starting at k). By first-step analysis:

$f(k) = p \cdot f(k+1) + q \cdot f(k-1), \quad f(0) = 0, \; f(N) = 1$

For p = q = 1/2 (fair coin), the recurrence becomes $f(k) = \tfrac{1}{2}(f(k+1) + f(k-1))$ , i.e., f is harmonic. The only linear solution satisfying the boundary conditions is $f(k) = k/N$ .

For p ≠ 1/2, try $f(k) = A + B \cdot (q/p)^k$ . Plugging in the boundary conditions:

$f(k) = \frac{1 - (q/p)^k}{1 - (q/p)^N}$

AI ALTERNATIVE FRAMING

For the fair coin, there's a beautiful conservation argument: the gambler's wealth is a martingale (fair game), so $\mathbb{E}[\text{final wealth}] = \mathbb{E}[\text{starting wealth}] = k$ . The final wealth is either 0 or N; so if p = P(reach N), then $0 \cdot (1-p) + N \cdot p = k$ , giving $p = k/N$ immediately. This martingale argument generalises to biased walks by using a log-transform that makes the biased walk a martingale in a new variable.

On QuantPrep, every practice problem gets an AI-generated alternative explanation like this — tailored to the canonical solution, streaming live.

COMMON VARIATIONS

Expected time to absorption

Starting at k, what's the expected number of rounds until the game ends (at 0 or N)?

For fair coin: $\mathbb{E}[T] = k(N - k)$. Peak at k = N/2, i.e. games starting from the middle take longest.

Infinite goal

What if N = ∞ (no goal, just avoiding ruin)? What's the probability of ever going broke starting from k?

For fair coin: 1 (you always eventually go broke). For p > 1/2: $(q/p)^k$ (nontrivial chance of never going broke). For p < 1/2: 1. Reflects recurrence of 1D walks.

With a minimum bet size

The gambler can bet any amount up to his current wealth on each round (bold play).

For fair coin, all strategies give the same ruin probability. For unfair (p < 1/2), bold play — bet min(k, N-k) every round — maximises the probability of reaching N.

FIRMS THAT ASK THIS

SIG Jane Street Citadel Optiver

TECHNIQUE

Markov Chains

If the problem has states and transitions, it's a Markov chain — and quant interviewers love them.

FREE QUANT BRAINTEASERS WEEKLY

Not ready to sign up? Get 5 hand-picked quant interview problems every week. No spam, unsubscribe any time.

TRY A PROBLEM NOW · NO SIGNUP

#042 · optimal_stoppingdifficulty 4

In the classical secretary problem, as n → ∞, what fraction should you reject outright before accepting the next best-so-far candidate?

FAQ

Why is the answer k/N so clean for the fair coin?

Because the gambler's wealth is a martingale. The optional stopping theorem then gives $\mathbb{E}[\text{final wealth}] = k$ , and the final wealth is either 0 or N, which uniquely determines the probability of each.

Does this apply to actual gambling?

Yes — with one crucial caveat: real casinos have p < 1/2, so the (q/p)^k formula applies. For roulette (p ≈ 18/38), the probability of doubling a £1000 bankroll to £2000 is about $(20/18)^{1000}$ tiny. Conversely, the probability of going broke while trying to double up is nearly 1.

How does this generalise?

To multi-dimensional walks (Pólya's theorem says 1D and 2D fair walks are recurrent, 3D+ are transient), to continuous-time analogues (Brownian motion with absorbing barriers), and to option pricing (American options are gambler's ruin problems with known payoff functions).

What's the expected duration?

For fair coin: $\mathbb{E}[T] = k(N-k)$ steps. Notice this peaks at k = N/2 — games starting at the midpoint take longest. This is a useful sanity check for any Markov-chain-style interview problem.

Practice variants of this problem

400+ problems on QuantPrep, including variants of gambler's ruin and every technique it draws on.

Start practicing free