Gambler’s ruin
Section of Random walks and first passage, part of Stochastic processes
Gambler’s ruin
| Type | Section |
| Taught in | Random walks and first passage |
| Part | Stochastic processes |
Take steps of size 1: \mathbb{P}(Y_i=+1)=p and \mathbb{P}(Y_i=-1)=q=1-p. Fix barriers at 0 and d, and a starting state x\in\{0,1,\ldots,d\}. Let
\tau=\inf\{n\ge 0: S_n\in\{0,d\}\}
be the first time the walk is absorbed, and write h_x=\mathbb{P}_x(S_\tau=d) for the probability of hitting d before 0 from x. The subscript records the starting state. Conditioning on the first step gives the boundary-value recurrence
h_x=p\,h_{x+1}+q\,h_{x-1}, \qquad 1\le x\le d-1,
with h_0=0 and h_d=1. From an interior point the walk moves to x+1 or x-1, and then the conditional probability of eventual success is the value of h at the new point.
If p=q=1/2, the equation says h_{x+1}-h_x=h_x-h_{x-1}. The first differences are constant, so h_x is linear. The boundary values force
h_x=\frac{x}{d}.
If p\neq q, substitute h_x=r^x. The characteristic equation is p r^2-r+q=0, with roots r=1 and r=q/p. The general solution is A+B(q/p)^x, and the boundary values give
h_x=\frac{1-(q/p)^x}{1-(q/p)^d}.
As p\to q this expression tends to x/d, which is the fair-walk formula. A biased walk with p>q satisfies h_x>x/d: the upward drift makes the upper barrier more likely than the fair proportion of the distance. If p<q, then h_x<x/d.
Used in
See also
Random walk with drift · Drift and scale of a random walk · Four-state random walk · First-passage time · Expected duration of a random walk · Solving the recurrences from scratch · Why the boundary problem is well posed