Setting up the gambler's problem
The previous guide handed you the simple random walk: start at some integer, and at each step move +1 with probability p and -1 with probability q = 1 - p, independently each time. Now we put walls on it. Imagine a gambler who starts with i dollars, bets one dollar per round, and quits the moment they either go broke (reach 0) or reach a target of N dollars. The walk is exactly the gambler's wealth; the two walls at 0 and N are absorbing — once the walk touches either, it stops forever. This is the gambler's ruin problem, and the headline question is simple to state: starting from i, what is the probability of hitting 0 (going broke) before reaching N?
Before any algebra, sharpen your intuition. The gambler is not fighting a single coin toss; they're fighting a whole sequence of them, and the question is which wall the wandering wealth meets first. Two forces are in tension: the random jitter that could carry you either way, and the drift — if p is not exactly 1/2, the walk has a built-in lean. A drift toward N helps you reach the target; a drift toward 0 (which is what every real casino game gives you, since p < 1/2 for the player) pushes you toward ruin. The beauty of gambler's ruin is that we can compute the exact ruin probability for any starting wealth i, any target N, and any p — and the answer is clean.
Solving it by conditioning on the first step
Let h(i) be the probability of eventual ruin (hitting 0 before N) when you start at wealth i. The trick is to condition on the very first bet, using the law of total probability. After one round you are either at i+1 (probability p) or at i-1 (probability q), and from there the future is a fresh gambler's ruin problem starting from the new wealth — because the steps are independent and identically distributed, the walk has no memory of how it got to its current spot. So h(i) = p · h(i+1) + q · h(i-1), with the boundary conditions h(0) = 1 (already broke) and h(N) = 0 (already won). This is a tidy recurrence relation, and it pins down h on every interior point.
Solving the recurrence gives two cases. When the game is fair (p = q = 1/2), the answer is breathtakingly simple: h(i) = 1 - i/N, so the probability of ruin is just the fraction of the way you'd still have to climb to reach N. Start halfway (i = N/2) and you're ruined exactly half the time. When the game is biased, write r = q/p for the ratio of losing to winning odds; then h(i) = (r^N - r^i) / (r^N - 1). Don't memorize the formula — feel it. If r > 1 (the player is disadvantaged, p < 1/2), the powers of r blow up and ruin becomes nearly certain unless you start very close to N.
Recurrence: h(i) = p*h(i+1) + q*h(i-1), h(0)=1, h(N)=0 Fair (p = 1/2): h(i) = 1 - i/N Biased (r = q/p): h(i) = (r^N - r^i) / (r^N - 1) Example, fair, i=50, N=100: ruin prob = 1 - 50/100 = 0.5 Example, p=18/38 roulette-red, i=100, N=200, r=20/18: ruin ~ 0.99996
How long does the game last?
Knowing whether you'll be ruined is only half the story; you also want to know how many bets the game runs before it stops at one wall or the other. Let d(i) be the expected number of steps starting from i until absorption. The same conditioning trick applies, but now each step costs one unit of time, so d(i) = 1 + p · d(i+1) + q · d(i-1), with d(0) = d(N) = 0. In the fair case this solves to the strikingly clean d(i) = i · (N - i). This is the expected duration — a mean hitting time for the pair of walls — and it is maximized right in the middle, where you are farthest from both exits.
Put numbers on it and the result is surprising. A fair game starting at i = 50 with target N = 100 has expected duration 50 · 50 = 2500 bets. That's a long evening for a game that, in the end, you only win half the time. The lesson sits uneasily next to the gambler's fallacy: the walk genuinely has no memory, so a long losing streak does not make the next bet safer — and yet the *aggregate* journey is governed by these exact, knowable laws. Randomness with no memory at the step level still produces rigid, predictable structure at the level of the whole game.
Recurrence: what if there's no wall?
Now remove the target wall entirely and let the walk run on all the integers forever. The natural question becomes: starting at 0, will the walk ever return to 0? A state is called recurrent if return is certain (probability 1), and transient if there's a positive chance the walk wanders off and never comes back. This is the heart of recurrence versus transience, and it is where gambler's ruin pays off, because we can read the answer off the ruin formula by pushing one wall to infinity.
Take the fair walk and let N go to infinity. The ruin probability h(i) = 1 - i/N tends to 1 for every fixed starting point i. In words: with no upper wall, a fair walk is certain to eventually hit 0 — and by the same argument, certain to eventually hit any level. So the symmetric simple random walk on the integers is recurrent: it returns to its start with probability 1, and in fact visits every integer infinitely often. But here is the honest catch that trips people up: although return is certain, the *expected time* to return is infinite. Recurrence guarantees you come home; it makes no promise about waiting a reasonable while. This is called null recurrence, and the d(i) = i·(N-i) duration blowing up as N grows is exactly its fingerprint.
Bias changes everything. If p is not 1/2, the walk has a steady drift, and the strong law of large numbers says the position after n steps behaves like n·(p - q), marching off toward plus or minus infinity. A drifting walk is transient: it may revisit its start a few times early on, but with probability 1 it eventually leaves for good and never returns. You can see this in the ruin formula too — for the biased walk the limit of the return probability as N grows stays strictly below 1. So the knife-edge p = 1/2 is special: exactly at fairness the walk is recurrent, and any drift at all, however slight, tips it into transience.
Why dimension matters: a famous twist
There's a celebrated extension worth knowing, because it shows recurrence is delicate. Run a symmetric simple random walk not on a line but on a grid, stepping to a random neighbor each time. On the one-dimensional line and on the two-dimensional grid the walk is still recurrent — return to the start is certain. But in three dimensions it becomes transient: a drunkard wandering on an infinite city grid always finds their way home, but a bird flying in three-dimensional space, taking random unit steps, returns with probability only about 0.34 — roughly one chance in three. Pólya summed it up: 'A drunk man will find his way home, but a drunk bird may get lost forever.'