Discrete Stochastic Processes

Lesson 1 of 10

Random Walks

A drunk on a 100 m bridge: why spread grows like √n, and why twice as far takes four times as long.

The idea

Take ±1\pm1 steps with equal probability. After nn steps the position SnS_n has mean 00 but variance nn, so its typical distance from the start is n\sqrt n, not nn. A thousand walkers fan out, and the fan's edge grows like n\sqrt n.

Turn that around: to get a distance dd away you need about d2d^2 steps. That answers "how long until the drunk falls off?"