Random walks and the gambler's ruin
Tonight's idea
Stand on 0 on a number line. Flip a coin: heads step right, tails step left. After \(n\) flips your position is \(S_n = X_1 + \cdots + X_n\), each \(X_i\) being \(+1\) or \(-1\) with probability \(\tfrac12\). This simple random walk is the skeleton inside diffusion and stock prices.
On average? Each step has expected value 0, so \(E[S_n]\), the expected (long-run average) position, is 0. True but useless.
How far, typically? Square and take expectations. Try \(n = 2\): \((X_1 + X_2)^2 = X_1^2 + X_2^2 + 2X_1X_2\); the squares are 1 and the cross term averages 0, so \(E[S_2^2] = 2\). In general \(S_n^2 = \sum_i X_i^2 + \sum_{i \ne j} X_i X_j\). Every \(X_i^2 = 1\), so the first sum is \(n\). Each cross term \(X_i X_j\) is \(\pm 1\) with equal probability, so its expectation is 0. Therefore
\(E[S_n^2] = n\): the typical distance from the start after \(n\) steps is \(\sqrt{n}\). After 100 steps, about 10; after a million, about 1,000.
Exactly. To be at \(k\) after \(n\) steps you need \(u = (n+k)/2\) up-steps, so \(P(S_n = k) = \binom{n}{u}/2^n\), where \(\binom{n}{u}\) counts the ways to choose which \(u\) of the \(n\) steps go up. For instance \(P(S_{10} = 0) = 252/1024 \approx 0.25\).
Gambler's ruin. You have \(a\) pounds and bet 1 a round on a fair coin until you reach \(N\) or hit 0. If \(p_a\) is the chance of reaching \(N\), then \(p_a = \tfrac12 p_{a-1} + \tfrac12 p_{a+1}\): each value is the average of its neighbours, so the \(p_a\) lie on a straight line from \(p_0 = 0\) to \(p_N = 1\):
\(p_a = a/N\) in a fair game. With a win probability \(p \ne \tfrac12\) and \(q = 1 - p\), the line becomes a geometric curve: \(p_a = \dfrac{1 - (q/p)^a}{1 - (q/p)^N}\).
Watch one: roulette, one chip at a time or all at once?
You have 10 chips and want 20. Red at a double-zero table wins with \(p = 18/38\), so \(q/p = 10/9\).
Timid play, one chip a spin: \((10/9)^{10} \approx 2.868\) and \((10/9)^{20} \approx 8.225\), so \(p_{10} = \dfrac{1 - 2.868}{1 - 8.225} \approx 0.259\).
Bold play, all 10 chips on one spin: \(18/38 \approx 0.474\).
Bold play nearly doubles your chance: every spin carries the same edge against you, so give the house as few spins as possible.
Your turn
- List all 8 paths of a 3-step walk (HHH, HHT, …) and where each ends. Give the distribution of \(S_3\), then compute \(E[S_3^2]\) from it and check against the formula.
- For a 6-step walk find \(P(S_6 = 0)\), \(P(S_6 = 2)\) and \(P(|S_6| \ge 4)\). Why is \(P(S_6 = 1)\) zero?
- Fair gambler's ruin. Find the chance of reaching the target first when you (a) have 10, target 100; (b) have 10, target 20; (c) have 100 and the casino has 1,000,000, playing until one of you has everything (so the target \(N\) is your stake plus theirs, 1,000,100). What is the lesson?
- A game you win with probability \(p = 0.6\). You have 5 and want 10, betting 1 a round. Use the biased formula with \(q/p = \tfrac23\), and compare with the fair answer.
Demo: mathdetours.com/demos/dice.html, where the gap from the predicted share shrinks like \(1/\sqrt{n}\).
Stretch: how long does ruin take?
Let \(D_a\) be the expected number of rounds a fair game lasts from a stake of \(a\). One round costs 1 and leaves you at \(a \pm 1\), so \(D_a = 1 + \tfrac12 D_{a-1} + \tfrac12 D_{a+1}\), with \(D_0 = D_N = 0\). Check that \(D_a = a(N - a)\) satisfies this. How many rounds on average for a stake of 10 and a target of 100?
Answers
- HHH 3, HHT 1, HTH 1, THH 1, HTT −1, THT −1, TTH −1, TTT −3. \(P(S_3 = \pm 3) = \tfrac18\), \(P(S_3 = \pm 1) = \tfrac38\). \(E[S_3^2] = \tfrac{2 \times 9 + 6 \times 1}{8} = 3 = n\). ✓
- \(\binom63/64 = \tfrac{5}{16}\); \(\binom64/64 = \tfrac{15}{64}\); \((6 + 6 + 1 + 1)/64 = \tfrac{7}{32}\). After an even number of steps the position is even, so odd positions are impossible.
- (a) \(0.1\). (b) \(0.5\). (c) \(100/1{,}000{,}100 \approx 0.0001\). The casino does not even need an edge: in a fair game against a far richer opponent, the poorer player is almost certain to be ruined first.
- \(p_5 = \dfrac{1 - (2/3)^5}{1 - (2/3)^{10}} = \dfrac{0.8683}{0.9827} \approx 0.884\), against \(0.5\) for a fair game. A modest edge moves the answer a long way from one half.
Stretch. \((a-1)(N-a+1) + (a+1)(N-a-1) = 2a(N-a) - 2\), so \(\tfrac12\) of that plus 1 is \(a(N - a)\). ✓ And \(D_0 = D_N = 0\). Stake 10, target 100: \(10 \times 90 = 900\) rounds on average, even though you reach the target only 10% of the time. Ruin is likely but slow.