Random walks
Start at 0. At every step move one unit up or down, each with probability 1/2. The same rule produces wildly different lives — and yet the typical distance from the start after n steps is always about √n.
From the slides: Why should anyone care about chance?.
Some walks
How far after n steps?
Run thousands of walks and measure, at every step, the root-mean-square distance from the start: the square root of the average of (position)2. Then look at where the walks finish.
Walks run
0
Root-mean-square distance at the end
—
Walks that finished exactly at 0
—
What to notice
- Individual walks wander far outside ±√n now and then, and spend long stretches on one side of zero. Long leads are normal in a fair game.
- The root-mean-square distance tracks √n exactly. The proof needs nothing but variance: each step adds variance 1, so after n steps the variance is n.
- The finishing positions form the same bell as the Galton board. It is the same experiment, sideways.