Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 47 ยท Monte Carlo Methods

Random Walks and Diffusion

Simulate random walks in one and two dimensions, show that the mean squared distance grows linearly with time, and extract the diffusion coefficient from the simulation.

A grain of pollen in water jitters unpredictably. A drop of ink spreads, a smell crosses a room, heat creeps through a metal rod. Behind all of these is one simple mathematical object: the random walk. Each step is random and independent, yet the collective behavior of many walkers is perfectly regular. This is how Monte Carlo connects microscopic randomness to macroscopic laws.

Left: four 2D random walks from a common origin. Right: mean squared distance averaged over 300 walkers growing linearly with steps
Individual paths wander, but the average of r squared over many walkers follows the straight line r squared = N.

What you will learn

  • How to simulate random walks in 1D and 2D with vectorized NumPy.
  • The central results โŸจxโŸฉ = 0 and โŸจxยฒโŸฉ = N aยฒ.
  • How the walk relates to the diffusion equation and the diffusion coefficient D.
  • How to measure D from a simulation.

Key terms

Random walk: a path made of independent random steps.

Mean squared displacement (MSD): โŸจrยฒโŸฉ, the average over walkers of the squared distance from the start.

Diffusion coefficient D: a constant (units mยฒ/s) defined by โŸจrยฒโŸฉ = 2 d D t in d dimensions.

Brownian motion: the random motion of a small particle in a fluid, driven by molecular collisions.

The one-dimensional walk

A walker starts at x = 0. At each time step it moves +a or โˆ’a with equal probability. After N steps its position is a sum x = a (sโ‚ + sโ‚‚ + โ€ฆ + s_N) where each sแตข = ยฑ1. Because the steps are independent with mean 0 and variance 1:

  • โŸจxโŸฉ = 0: no drift.
  • โŸจxยฒโŸฉ = N aยฒ: the variance adds up, so the typical distance grows like โˆšN, not N.

By the central limit theorem, for large N the position is approximately Gaussian with variance N aยฒ. The typical spread is aโˆšN. Doubling the typical distance takes four times as many steps.

Python Many 1D walkers at once

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two dimensions and the MSD

In 2D, let each step have unit length and a uniformly random direction: ฮ”r = (cos ฯ†, sin ฯ†) with ฯ† uniform in [0, 2ฯ€). Then โŸจฮ”xยฒโŸฉ + โŸจฮ”yยฒโŸฉ = 1 per step and the squared distance after N steps averages to โŸจrยฒโŸฉ = N. Averaging over many walkers gives a clean straight line against N, as the figure shows. The single paths are jagged, but the ensemble average is smooth.

Connecting to diffusion

If each step has length a and takes time ฯ„, then t = N ฯ„ and the mean squared displacement is โŸจrยฒโŸฉ = N aยฒ = (aยฒ/ฯ„) t. The macroscopic definition of the diffusion coefficient in d dimensions is

โŸจrยฒโŸฉ = 2 d D t

so for the random walk D = aยฒ / (2 d ฯ„). In d = 2 with a = 1, ฯ„ = 1 you expect D = 1/4. The same D appears in the diffusion equation โˆ‚c/โˆ‚t = D โˆ‡ยฒ c for the concentration c(r, t) of many walkers: you will solve it on a grid in chapter 5. Einstein's 1905 analysis of Brownian motion used exactly this link, and Jean Perrin's measurements of the pollen-like particles' MSD helped establish that atoms are real.

Python Measuring D from a 2D walk

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The statistical error is itself a Monte Carlo error that shrinks like 1/โˆš(walkers), so averaging more walkers gives a smoother MSD.

Watch diffusion happen

The interactive demo below releases 400 walkers from the origin. The pink dashed circle has radius โˆšt, the theoretical root-mean-square distance. Notice how the cloud fills the circle and how slowly the radius grows.

A cloud of random walkers

Extensions you will meet later

  • Biased walks have a drift: a step to the right with probability p โ‰  1/2 gives โŸจxโŸฉ = N a (2p โˆ’ 1), which models a particle in an electric field.
  • Absorbing and reflecting boundaries give first-passage times and escape probabilities.
  • Recurrence: a simple random walk on a line or a plane returns to the start with probability 1, while in three dimensions it may escape forever (Pรณlya's theorem).
  • Self-avoiding walks model polymer chains: the walk may not revisit a site, and the size grows faster than โˆšN.

Common misconceptions

"A random walker drifts away linearly with time." The typical distance grows only as โˆšt; the MSD, not the distance, is linear.

"One long walk is as good as many short ones." The MSD is an average over the ensemble, and a single walk has large fluctuations. Average over walkers (or over time windows) before fitting D.

"Diffusion pushes particles." There is no force: the spreading is the statistics of random steps. Concentration gradients appear to drive a flow because more walkers step from the crowded side than from the empty side.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. After N unit steps of an unbiased 1D random walk, the mean squared displacement is

    Variances of independent steps add: each contributes 1, so <x^2> = N.
  2. 2. The typical distance of a random walker from the start grows like

    The rms distance is the square root of the MSD, sqrt(N).
  3. 3. In d dimensions the MSD satisfies <r^2> = 2 d D t. For d = 3 and MSD = 6 D t what does the factor 6 represent?

    2d = 6 for d = 3.
  4. 4. For a 2D walk with steps of length 1 every time unit, D equals

    D = a^2 / (2 d tau) = 1 / (2 * 2) = 1/4.
  5. 5. Why average over many walkers?

    The smooth linear law emerges only in the average.

Summary

  • An unbiased random walk has โŸจxโŸฉ = 0 and โŸจxยฒโŸฉ = N aยฒ; the spread grows like โˆšN.
  • The MSD of an ensemble grows linearly in time: โŸจrยฒโŸฉ = 2 d D t.
  • Measure D by fitting the MSD of many walkers; the error shrinks like 1/โˆš(walkers).
  • Random walks are the microscopic picture behind the diffusion equation.

Next: The Ising Model and the Metropolis Algorithm