Lessons · Probability
Random walks and gambler's ruin
"You start with $a and bet $1 at a time until you hit $N or go broke." Questions like this look like they need long calculations. One idea, the fair game, solves most of them in a line.
Fair games don't change your expected wealth
In a fair bet, your expected wealth after the bet equals your wealth before it. A process with this property is called a martingale. The key fact, called optional stopping, is that (under mild conditions that hold for these bounded problems) stopping at a sensible time doesn't change the expectation either.
Worked example: reaching a target
You have $3, bet $1 on fair coin flips, and stop at $10 or $0. Let p be the chance of reaching $10. At the end you have $10 with probability p and $0 otherwise, so your expected final wealth is 10p. A fair game keeps it at $3:
10p = 3 ⟹ p = 3/10
In general, starting at a with targets 0 and N: p = a/N.
The same idea for a symmetric walk
A walk starts at 0 and moves ±1 with equal chances. What's the chance it reaches +b before −a? Its position is a martingale, so p · b − (1 − p) · a = 0, giving p = a/(a + b). Reaching +2 before −1 has probability 1/3.
How long does it take?
For a ±1 walk, (position)² − (number of steps) is also a martingale. At the stopping time this gives E[steps] = E[final position²]. With barriers at −a and +b:
E[steps] = b² · a/(a+b) + a² · b/(a+b) = a · b
Hitting ±3 from 0 takes 9 steps on average.
When the game isn't fair
If each bet wins with probability p ≠ ½, let r = q/p where q = 1 − p. Then r^(wealth) is the martingale, and the chance of reaching N from a is
P = (rᵃ − 1) / (rᴺ − 1)
A small edge compounds dramatically over many bets, which is the mathematical reason casinos win.
Common traps
- Infinite games. Optional stopping needs the game to end in a sensible way. "Double your bet after every loss" seems to guarantee profit, but it needs unlimited money and time.
- Using a/N for unfair games. That formula only holds when every bet is fair.