Random Walk
A path built by adding up independent random steps; its typical distance from the start grows like the square root of the number of steps.
Contents
Random Walk
A random walk is the simplest random process there is: start at a point, take a step in a random direction, then another, then another. Each step forgets the past — it does not matter how you got here, only that you take one more independent jump. The classic picture is the drunkard's walk: a stumbling figure who flips a coin at every lamppost to decide left or right. Where do they end up?
The surprising answer is that the walk has a precise statistical shape even though every single step is unpredictable. On average the drunkard goes nowhere — left and right cancel. But their typical distance from the start grows steadily, and at a very specific rate.
Spread grows like the square root
After n steps of size 1, the position X_n = s_1 + s_2 + \cdots + s_n is a sum of independent \pm 1 steps. Its mean is zero, but its variance adds up: each step contributes 1, so \operatorname{Var}(X_n) = n. The typical distance is the standard deviation:
This \sqrt{n} law is the signature of diffusion. To get twice as far from home you need four times as many steps. It is why ink spreads slowly through still water, why a smell takes minutes to cross a room, and why a stock price wanders the way it does. The walk explores, but it explores reluctantly.
A crowd of walkers spreading out
Below, hundreds of walkers all start at the center line and step left or right at random each frame. Two things happen at once. The cloud spreads — its edges creep outward like \sqrt{n}, slowing as it widens. And the histogram at the bottom fills in: it counts how many walkers sit at each horizontal position, and it grows into a smooth bell curve, sharp in the middle, thin at the tails.
Walks in more dimensions
Nothing forces the walk to a line. A walker on a plane or in space follows the same \sqrt{n} spreading, and in the continuous limit — infinitely many infinitely small steps — the path becomes Brownian Motion, the mathematically exact model of a diffusing particle. A random walk is also the simplest interesting Markov Chain: the next position depends only on the current one, never on the route taken to reach it.