How far does a random walker get?
Tonight's idea
Stand on a row of paving stones. Flip a fair coin. Heads, step one stone right. Tails, step one stone left. Keep going. This is a random walk. Nobody can say where one walk will end, but math(s) can say how far walkers get on average.
Your distance is how many stones you are from the start, on either side. Your squared distance is the distance times itself.
Take every possible walk of \(N\) steps. The average of their squared distances is exactly \(N\). The typical distance is the number whose square is \(N\), written \(\sqrt{N}\).
After 100 steps the typical distance is 10, because \(10 \times 10 = 100\). It is not a promise: many walks end nearer and some end farther.
Scientists use this as a model. A tiny speck in still water is knocked about by water molecules (Brownian motion). A long, floppy chain molecule turns at random from one link to the next. Both are messier than coin flips, so the walk is only a model. It predicts averages and spreads, never one exact path.
Watch one: every walk of 4 steps
Four flips can come out in \(2 \times 2 \times 2 \times 2 = 16\) ways, all equally likely. Where you end depends only on how many were heads. Three heads and one tail, for example, leaves you at \(3 - 1 = 2\) stones right, and there are 4 ways to do it: the tail can be the first, second, third or fourth flip.
| Heads | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| End | 4 left | 2 left | start | 2 right | 4 right |
| Ways | 1 | 4 | 6 | 4 | 1 |
| Distance | 4 | 2 | 0 | 2 | 4 |
| Squared distance | 16 | 4 | 0 | 4 | 16 |
Check: \(1 + 4 + 6 + 4 + 1 = 16\) ways. So 2 walks have squared distance 16, 8 walks have 4 and 6 walks have 0. Average squared distance: \((2 \times 16 + 8 \times 4 + 6 \times 0) \div 16 = 64 \div 16 = 4\). That is the number of steps, as the callout says. The typical distance is 2, because \(2 \times 2 = 4\).
The average of the plain distances is smaller: \((2 \times 4 + 8 \times 2 + 6 \times 0) \div 16 = 24 \div 16 = 1.5\). Squaring makes the far walks count for more.
Your turn
- List the 4 equally likely walks of 2 steps (use L and R). Write each distance and squared distance. Find the average squared distance. Does it match the callout?
- Do the same for the 8 walks of 3 steps. Can a walk of 3 steps end back at the start? The typical distance is \(\sqrt{3}\): which two whole numbers is it between?
- Find the typical distance after 100 steps, after 400 steps and after 10,000 steps. How many times as many steps does it take to double the typical distance?
- A model chain molecule has 16 links, each 1 unit long. Each link points left or right at random, like a coin-flip step. How long is the chain pulled out straight? What is the typical distance between its two ends? Answer both again for 10,000 links.
- You are 3 stones from the start. One more step puts you at distance 2 or 4, with equal chances. Average the two squared distances and compare with \(3 \times 3\). Try it again from distance 5, and from distance 0. What does one step always do to the average squared distance?
Stretch: most likely to be at the start, and yet far from it
After 4 steps, which single stone is the most likely place to end? How many of the 16 walks end somewhere else? Which distance is the most likely? After 100 steps the most likely stone is still the start, but exact counting shows only about 8 walks in 100 end there. Explain how the start can be the most likely stone while the typical distance is 10.
Answers
- LL ends 2 left, LR and RL end at the start, RR ends 2 right. The distances are 2, 0, 0, 2 and the squared distances are 4, 0, 0, 4. The average is \(8 \div 4 =\) 2, the number of steps, so it matches. The typical distance is \(\sqrt{2}\), about 1.4, since \(1.4 \times 1.4 = 1.96\).
- LLL and RRR end 3 away. The other six (LLR, LRL, RLL, RRL, RLR, LRR) end 1 away. The squared distances are 9 twice and 1 six times, so the average is \((2 \times 9 + 6 \times 1) \div 8 = 24 \div 8 =\) 3. No walk of 3 steps ends at the start: to get back you need as many lefts as rights, and 3 is odd. \(\sqrt{3}\) is between 1 and 2, because \(1 \times 1 = 1\) and \(2 \times 2 = 4\). It is about 1.7, since \(1.7 \times 1.7 = 2.89\).
- 10, 20 and 100, because \(10 \times 10 = 100\), \(20 \times 20 = 400\) and \(100 \times 100 = 10{,}000\). Going from 10 to 20 took 4 times as many steps. That is true from any starting number: doubling a distance multiplies its square by \(2 \times 2 = 4\). A random walker spreads out slowly. From 100 steps to 10,000 is 100 times the steps for only 10 times the typical distance.
- Pulled straight, the 16-link chain is 16 units long. Its typical end-to-end distance is 4 units, a quarter of that. With 10,000 links it is 10,000 units straight and typically 100 units end to end, only a hundredth. In this model, the longer the chain, the more crumpled it is compared with its full length. A real chain can turn in any direction and cannot pass through itself, so this is only a model.
- From 3: the squared distances are \(2 \times 2 = 4\) and \(4 \times 4 = 16\), with average \(20 \div 2 = 10\). That is \(9 + 1\). From 5: 16 and 36, average \(26 = 25 + 1\). From 0: both steps take you to distance 1, so the average is \(1 = 0 + 1\). One step always raises the average squared distance by exactly 1, wherever you are. It starts at 0, so after \(N\) steps it is \(N\). That is why the callout is true.
Stretch. After 4 steps the most likely stone is the start, with 6 walks. No other stone has more than 4. But \(16 - 6 =\) 10 walks end somewhere else. The most likely distance is 2, with 8 walks, because distance 2 collects two stones, 2 left and 2 right. So "most likely stone" and "how far" are different questions. After 100 steps there are 101 stones you could end on. The start is the most likely one, yet about 92 walks in 100 miss it. They are spread over many stones on both sides, and every one of them adds something to the average squared distance. The far ones add a lot: ending 20 away adds 400. So the typical distance, 10, is well away from 0. It also sits above the middle of the pack: exact counting shows about 73 walks in 100 end 10 stones away or nearer, and the average plain distance is about 8.