Random walks and gambler’s ruin

A surprising number of interview problems are a walk between two absorbing barriers wearing a disguise: two ants on a shape, a gambler with a stack, a trader with a stop-loss. Once you see the states, the method is always the same — write one equation per state and solve.

Definition 4.1

The object

Simple random walk, $S_n = \sum_{i=1}^{n} X_i, \quad X_i = \pm 1$ — A position that moves up one with probability $p$ and down one with probability $q = 1-p$ at each step. Absorbing barriers are values at which the walk stops.

Proposition 4.2

The method, every time

Let $P_k$ be the probability of the outcome you want, starting from state $k$ . Write the boundary conditions, then one equation per interior state by conditioning on the next step. Solve the system. This works whether the states are money, positions on a graph, or anything else finite.

Holds when

The states must be a complete description — if the answer depends on history, you have not found the right state variable.
Boundaries are where the process stops: $P_0$ and $P_N$ are known, not unknown.

Derivation 4.3

The fair game

With $p = 1/2$ , the recursion says each state is the average of its neighbours — which forces the solution to be a straight line.

$P_k = \tfrac{1}{2}P_{k-1} + \tfrac{1}{2}P_{k+1}, \qquad P_0 = 0,\ P_N = 1$
$P_{k+1} - P_k = P_k - P_{k-1}$
Equal increments, so the solution is linear in $k$ .

P_k = \frac{k}{N}

Why the fair answer is your share of the stack. The walk is a martingale, so your expected final wealth equals your starting wealth. You end at either $0$ or $N$ , so $k = 0\cdot(1-P) + N\cdot P$ , giving $P = k/N$ immediately. That is the optional stopping theorem doing in one line what the recursion does in three.

Equation 4.4

The biased game

The probability of reaching $N$ before $0$ , starting from $k$ , when each step is up with probability $p$ .

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

$r = q/p$: The odds against you per step. $r = 1$ recovers the fair case $k/N$ .
$N$: The combined stack — your money plus the opponent’s.

Example 4.5

The SIG version

Your opponent has $\$2$ and you have $\$1$ . Each round you both stake a dollar; you win each round with probability $2/3$ . You play until someone is broke. What is the probability you win?

Show the worked solutionHide the worked solution

Worked solution

Formula $P_k = \frac{1 - r^{k}}{1 - r^{N}}, \qquad r = \frac{q}{p}$
Substitute $r = \frac{1/3}{2/3} = \tfrac{1}{2}, \quad k = 1, \quad N = 3$
Solve $P_1 = \frac{1 - \tfrac{1}{2}}{1 - \tfrac{1}{8}}$
$= \frac{1/2}{7/8}$
Answer $P_1 = \tfrac{4}{7}$

Sanity check. Above $1/3$ , which is what a fair game would give from a one-in-three share of the stack, but well below $2/3$ — being the better player does not compensate for being short of capital.

Reaches $\$100$ — 10 of 100
Goes broke first — 90 of 100

Figure 4.6 · Your share of the money on the table. A hundred gamblers, each starting on

\$10

against an opponent holding

\$90

, each playing a fair game. Ten get there. The fraction is your starting stack over the total on the table, and no betting pattern changes it while the game stays fair.