Gambler's Ruin on a Fair Coin
A gambler starts with $\$k$ and repeatedly bets $\$1$ on a fair coin flip -- heads they win $\$1$, tails they lose $\$1$. The game ends when their bankroll hits $\$n$ (they win) or $\$0$ (they're ruined).
What is the probability the gambler reaches $\$n$ before going broke?
Hints
- Think about what symmetry of a fair coin tells you. If the walk has no drift, the win probability should depend only on where you start relative to the two barriers.
- Define $p_i$ as the probability of reaching $n$ from state $i$ and write a recurrence using first-step analysis: $p_i = \frac{1}{2}p_{i-1} + \frac{1}{2}p_{i+1}$.
- The recurrence implies constant differences $p_{i+1} - p_i = p_i - p_{i-1}$. With $p_0 = 0$ and $p_n = 1$, this pins down the unique linear solution.
Worked Solution
How to Think About It: This is the classic gambler's ruin -- a symmetric random walk with two absorbing barriers. Before doing any math, think about it this way: the coin is fair, so there's no drift. The gambler's only "edge" is how close they start to the target relative to the total distance. If you start at $k = 1$ with $n = 100$, you're almost certainly going broke. If you start at $k = 99$, you're almost certainly winning. The answer should be linear in $k$ -- and it is.
Quick Estimate: Suppose $k = 25$ and $n = 100$. By symmetry of a fair random walk, the gambler's chance of reaching $n$ versus $0$ should be proportional to how far they are from each barrier. Distance to $0$ is 25, distance to $n$ is 75. So the probability of winning should be roughly $25/100 = 0.25$. That turns out to be exact.
Approach: Set up a recurrence relation using first-step analysis, then solve the resulting linear system.
Formal Solution:
Let $p_i$ be the probability of reaching $\$n$ starting from state $\$i$.
Boundary conditions:
$$p_0 = 0, \quad p_n = 1$$
By first-step analysis, for $0 < i < n$:
$$p_i = \frac{1}{2}\,p_{i-1} + \frac{1}{2}\,p_{i+1}$$
Rearranging: $p_{i+1} - p_i = p_i - p_{i-1}$. This says the differences $d_i = p_i - p_{i-1}$ are all equal. Call this common difference $d$.
Then $p_i = p_0 + i \cdot d = i \cdot d$. Applying $p_n = 1$ gives $d = 1/n$, so:
$$p_i = \frac{i}{n}$$
Note: this is the unique solution to the harmonic equation $p_i = \frac{1}{2}(p_{i-1} + p_{i+1})$ on $\{0, 1, \ldots, n\}$ with the given boundary conditions. Harmonic functions on a line segment are linear -- this is a discrete version of the Laplace equation.
Answer: The probability of reaching $\$n$ starting from $\$k$ is:
$$P(\text{win}) = \frac{k}{n}$$
Intuition
The gambler's ruin is the simplest non-trivial Markov chain absorption problem, and its punchline is surprisingly clean: on a fair game, your win probability is just the fraction of the total bankroll you start with. This is because a fair random walk is a martingale -- your expected wealth never changes, so your probability of hitting the upper barrier must equal $k/n$ to keep the expected value consistent. If it were anything else, the martingale property would be violated.
This result shows up constantly in quant work. Any time you model something as a symmetric random walk between two boundaries -- a trader's P&L hitting a stop-loss or profit target, a particle diffusing between walls, an inventory level triggering a rebalance -- the exit probabilities are linear in the starting position. The biased coin version ($p \neq 1/2$) is equally important and the answer becomes exponential rather than linear, which is why even a tiny edge compounds dramatically over many bets. The key interview trap: candidates often try to compute the probability by summing over paths, which is hopeless. The recurrence/martingale approach is the only clean way.