Random walks and diffusion

What you will be able to do

After this lesson you can

• simulate a random walk with np.cumsum,
• simulate thousands of walkers at once with a two-dimensional array, and
• show that the typical distance grows as the square root of the number of steps.

A drunk on a line

A walker stands on a line. At every step, the walker goes one place to the left or one place to the right, with the same chance. After many steps, where is the walker? This is a random walk. It is a model for many things: a molecule of perfume moving through the air, a particle jostled by the molecules of water (Brownian motion), the price of a share, and the path of a photon in the Sun.

Predict first. After 20 steps, will the walker be near 0 or far from 0?

Many walkers at once

Predict first. On average, will the walkers drift to the right, or stay near 0? How far from 0 will a typical walker be after 100 steps: about 100, about 10, or about 1?

The output says:

• The mean final position is $-0.06$, about 0. There is no push to either side, so on average the walkers have not gone anywhere.
• The mean of the squared distance is 101.3. It is about 100, the number of steps.
• The typical distance is 10.07, which is the square root of 100.

So after 100 steps, the walker is typically 10 places from the start, not 100. The walker takes 100 steps, but most of them cancel: half to the left and half to the right.

The law of the mean squared distance

For steps of length $\ell$ and a number of steps $n = t / \tau$ in time $t$, this becomes $\langle x^2 \rangle = \ell^2 t / \tau$: the mean squared distance grows in proportion to the time. This is the law of diffusion, found by Einstein in 1905. Perfume spreads in a room, and ink spreads in water, in just this way. It is also why diffusion is very effective over a short distance and very slow over a long one: to go 10 times farther, a particle needs 100 times as much time.

The mean position stays near 0, because left and right steps cancel. The squares do not cancel, which is why the spread grows.

The bell curve

This is a case of a deep fact, the central limit theorem: when many small random pieces are added, the sum has a bell-shaped distribution, whatever the shape of the pieces. Here each piece is a step of $\pm 1$. This is why the bell curve is everywhere in nature: the height of people, the errors of measurements, and the final positions of walkers.

A walk in a plane

Common mistakes

• Thinking that the walker drifts away at one step for each unit of time. The typical distance is $\sqrt{n}$.
• Taking the mean of the position and concluding that nothing moved. Use the mean of the squared position.
• Using cumsum along the wrong axis. For one running total for each walker, use axis=1.
• Looking at one path only. The law is for the average.
• Mixing up size=(walkers, steps) and size=(steps, walkers).

Practice

Start with two quick questions. Each New numbers gives you a fresh one, so you can practise as long as you like.

Then the labs and the problems:

1. Warm-up. Open the lab Random walk. You write a walk, and the mean squared distance of many walkers.
2. Build. Open the problem Drunk walker and the problem Diffusion coefficient.

Remember these

• A random walk is the running total (np.cumsum) of random steps.
• For many walkers, make a two-dimensional array with a row for each walker, and cumsum(axis=1).
• The mean position is 0. The mean squared distance after $n$ steps is $n$. The typical distance is $\sqrt{n}$.
• The final positions form a bell curve: this is diffusion.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

1. What is the typical distance of a walker after 400 steps of length 1?

2. How many times more steps are needed to go 3 times as far?

3. What is np.cumsum([1, -1, 1, 1])?

4. Why is the mean position zero, but the mean squared distance is not?