Gambler’s ruin, for quant interviews

Set the walk up before you solve it

Strip away the story — chips, a random-walking stock, a token bouncing between barriers — and every gambler’s-ruin question is the same object: an integer state $i$ doing a random walk between two absorbing walls at $0$ and $N$. Each step is $+1$ with probability $p$ and $-1$ with probability $q = 1 - p$. The single number that runs the whole problem is the ratio $r = q/p$.

Before writing anything, say out loud what you are solving for: the hitting probability (which wall do you reach first?) or the expected duration (how many steps until you hit one?). Both come from the same recurrence, and mixing them up is the fastest way to lose the room.

The fair walk is a straight line

Let $P_i$ be the probability of ruin — hitting $0$ before $N$ — starting from $i$. Conditioning on the first step gives the recurrence $P_i = p\,P_{i+1} + q\,P_{i-1}$ with boundaries $P_0 = 1$ and $P_N = 0$. When $p = q = \tfrac12$ this says $P_i$ is the average of its neighbours, i.e. the sequence is linear:

Starting from $3$ with a target of $10$: ruin $= 7/10 = 70\%$, reach $= 3/10 = 30\%$. No exponentials, no fuss — and a clean sanity check that the boundaries give $1$ and $0$.

The biased walk: solve the recurrence

For $p \neq q$ the linear shortcut is wrong, and reaching for it is the classic trap. Treat $P_i = p\,P_{i+1} + q\,P_{i-1}$ as a linear recurrence and try $P_i = x^i$. That gives the characteristic equation

since the discriminant is $1 - 4pq = (q-p)^2$, a perfect square. The general solution is $P_i = A + B\,r^i$ with $r = q/p$; the boundaries $P_0 = 1$, $P_N = 0$ pin down $A$ and $B$:

As $p \to \tfrac12$ you have $r \to 1$, the two roots collide, and L’Hôpital collapses this straight back to $1 - i/N$. That limit is the check that proves you derived the right thing rather than pattern-matched a formula.

How fast a small edge becomes fatal

Ruin depends on $r^i$ against $r^N$, so a bias does not nudge the answer — it compounds geometrically with distance. Take $p = 0.4$, so $r = q/p = 1.5$, from the same start of $3$ out of $10$:

so ruin is about 95.8%, up from $70\%$ in the fair game. A ten-point shift in the per-step odds nearly doubled your chance of losing everything.

This is the intuition an interviewer wants you to carry out of the room: against the house, the barrier you want is exponentially far away and the barrier you fear sits right behind you. Distance from ruin buys you almost nothing once the walk is biased.

Expected duration is a second recurrence

“How long does the game last?” uses the same first-step conditioning, but with a $+1$ for the step you just took: $D_i = 1 + p\,D_{i+1} + q\,D_{i-1}$, $D_0 = D_N = 0$. In the fair case this telescopes to a clean product,

which peaks dead center: from $i = 3$, $N = 10$ you expect $3 \cdot 7 = 21$ steps, and the mid-point $i = 5$ tops out at $25$. The biased duration carries the $r$ terms and is shorter and skewed — the drift keeps flushing you toward ruin instead of letting the walk meander.

Watch the sign: with $q - p > 0$ the formula $D_i = \tfrac{i}{q-p} - \tfrac{N}{q-p}\cdot\tfrac{1-r^i}{1-r^N}$ stays positive. A negative or zero expected time off the boundary means your recurrence is broken.

The infinite-horizon limit

A favorite follow-up: drop the upper wall ($N \to \infty$) and ask whether you are ruined for sure. Send $N \to \infty$ in the ruin formula. If $p < \tfrac12$ then $r > 1$, $r^N \to \infty$, and $P_i \to 1$ — certain ruin, no matter how rich you start. If $p > \tfrac12$ then $r < 1$ and you survive forever with probability

American roulette makes it concrete: an even-money bet wins with $p = 18/38$, a $5.26\%$ edge, so $r = 10/9$. Trying to double from $100$ to $200$ units succeeds only about $0.9^{100} \approx$ 1 in 37,000 of the time. The edge is small; the wall is not.

Variants that change the answer

The result is a fact about how the walk moves, so listen for a tweak that changes the mechanics:

• Ties / lazy walk. Add a “stay put” probability $s$. It divides both $p$ and $q$ by $1-s$, leaving the ratio $q/p$ — and therefore every ruin probability — unchanged. Only the expected duration stretches, by roughly $1/(1-s)$.
• Bold play. With the odds against you, small even bets guarantee slow ruin; betting boldly toward the target minimizes the number of unfavorable bets and maximizes your reach probability. Timid play is the trap.
• Reflecting barrier. If $0$ bounces you back instead of absorbing, it is no longer a ruin problem at all — the boundary condition changes and so does the whole answer. Always confirm each wall is absorbing before you reuse the formula.

Common mistakes

• Using $1 - i/N$ on a biased walk. The linear answer is a $p = q$ special case. If the prompt gives any edge, you owe the $r^i$ formula.
• Dropping the $+1$ in duration. Expected time counts the step you just took; forget it and you get zero everywhere. Boundary $D = 0$ is what makes the recurrence solvable.
• Assuming a tiny edge barely matters. Because ruin scales with $r^i$, a couple of percent per step becomes near-certain ruin over any real distance. Say so — it is the finance-relevant punchline.
• Confusing ruin with reach. They sum to $1$, but interviewers ask for a specific one. State which wall your $P_i$ is measuring and check both boundaries.