Random Walks

2014-04-11

{
  // const height = 50;
  const svg = d3.select(DOM.svg(width, height));
  
  let pos = 0.5;
  const step = 0.05;
  
  var walker = svg.append("circle");
      walker
          .attr("cx", x(pos))
          .attr("cy", y(0.5))
          .attr("r", 10)
          .classed("fill-coral", true);
  
  while (true) {
    yield svg.node();
    await Promises.delay(1000);
    if (Math.random() < 0.5) {
      pos += step;
    }
    else 
    {
      pos -= step;
    }
    walker.transition().duration(100).attr("cx", x(pos)).end();
  }
}

width = 720;
height = 50
lims = ({xMin: 0, xMax: 1, yMin:0, yMax:1})
margin = ({top: 40, right: 40, bottom: 40, left: 40})

y = d3.scaleLinear()
  .domain([lims.yMin, lims.yMax])
  .range([height - margin.bottom, margin.top]);

x = d3.scaleLinear()
    .domain([lims.xMin, lims.xMax])
    .range([margin.left, width - margin.right]);

// Includes
d3 = require("d3@7")

Imagine you stand on the pavement on your street, flip a coin and take a step left for heads or a step right for tails. Then repeat. Your movement might look something like the circle above, which is moving according to electronic coin flips made by your computer.¹

We call this kind of path a random walk in mathematics, and though it might not seem like much, random walks prove to be of great use in modelling complex systems in diverse fields, from financial markets to animal behaviour. It is also used everywhere in computational physics from the cosmological to the quantal, but perhaps the most familiar random walk in physics came in the form of a classical problem so we’ll start there.

Brownian Motion

In 1827, the Scottish botanist Robert Brown looked through his microscope at pollen grains suspended in water and noted that they jittered around in a way he couldn’t explain.

It took until 1905 until a satisfactory answer was provided by Albert Einstein² who brought some statistical methods to the problem, predicting that the random motion of the pollen grains was due to water being made up of molecules, which were continually bumping into the pollen grains. First he derived a diffusion equation for the grains, then he showed how to link this to physically measurable quantities starting with the mean squared dispacement (MSD), which we’ll come back to.

The reality of atoms and molecules was not fully accepted at that time, and Einstein viewed this model of Brownian motion as a way to give evidence for, or to falsify, the atomic theory. He wrote in the paper:

If the movement discussed here can actually be observed (together with the laws relating to it that one would expect to find), then classical thermodynamics can no longer be looked upon as applicable with precision to bodies even of dimensions distinguishable in a microscope: an exact determination of actual atomic dimensions is even possible. On the other hand, had the prediction of this movement proved to be incorrect, a weighty argument would be provided against the molecular-kinetic conception of heat.

Experimental verification of the theory was made a few years later by Jean Perrin — atoms and molecules were here to stay.

Walking on a Lattice

To introduce modelling with random walks, we’ll go back to the coin toss example we started with. This is an example of a lattice walk, in this case a 1D lattice.

We define the walk as a sequence of n independent integers a_n, each with equal probability of being either -1 or 1. Then we define the series \{ S_n \}, where

S_n = \sum_{i=0}^{n}{a_n},

as the random walk. In the simulation below, 100 walks are made with n = 20 steps. The final positions of the walkers are recorded in the histogram, which gives us a starting point for investigating the statistical properties of the lattice walk.

Click to start. The walkers move along the horizontal axis, with their paths being tracked in time on the vertical axis and their final positions recorded in the histogram.

Note that no walkers land on odd numbers. Why is that?

[FIGURE UNDER REPAIR]

A number of runs should show that despite each walker taking its own route, the result of many walkers tends toward the same result: a normal distribution. I won’t derive that distribution here, but fundamentally its normality is due to the central limit theorem.

All good, but for any physical system we’re trying to model (e.g. Brown’s jittery pollen grains) we need to find something to relate the individual walkers to something we can physically observe. The obvious place to start is the question: how far do the walkers get after a certain time, or n steps?

The mean value \langle a_n \rangle of any single step is zero, and by addition we find the the mean, or expectation, value of the walk,

\langle S_n \rangle = \sum_{i=0}^{n}{\langle a_i \rangle} = 0.

This we might expect, as with each step having equal probability of going either way the most probable distance travelled after a number of steps will be zero — back where the walker started. So in this case the mean displacement is not useful to us.

Next we might look at the squared distance travelled. This proves more useful as (-1)^2 = 1^2 = 1, so \langle a_n^2 \rangle = 1. Then

\langle S_n^2 \rangle = \sum_{i=0}^{n}{\langle a_i^2 \rangle} + \sum_{i=0}^{n} \sum_{j \ne i} 2 \langle a_i a_j \rangle = n + 0 = n.

So this non-zero mean squared displacement gives us a more useful statistical quantity to work with.

Measurable Quantities

In his paper Einstein derived, from basic principles of kinetic theory, a mean squared displacement that might be expected for a particle subject to Brownian motion. Describing the motion in terms of a diffusion equation, he showed that the mean squared displacement \langle S(t)^2 \rangle of a particle at a time t is related linearly to the diffusion coefficient D by

\langle S(t)^2 \rangle = 2 d D t

where d is the number of dimensions in the problem. The diffusion of particles is something we can observe and measure, so now we have a way to check the random walks of a model with reality.

In the next simulation, we’ll move up to a 2D lattice, where each walker can move on a plane: up, down, left or right with equal probability. We’ll set off 50 walkers, and keep track of the MSD as we go in a graph.

The equation for the diffusion coefficient above tells us we should expect the MSD graph to tend to a straight line as we increase the number of walkers. Then, once the last walker has walked we’ll take a line of best fit through the function from which (by the relation for the diffusion equation above, with d = 2) the slope of the line gives us the diffusion coefficient.

Click to start. The walkers move around the plane randomly.

The graph below shows the mean squared distance the walkers have travelled, against the number of steps taken.

Does the MSD function tend toward a straight line? When the walkers are finished and the trendline is drawn, does it fit the data well?

What does the diffusion coefficient tell us about particle motion?

[FIGURE UNDER REPAIR]

Conclusions

I hope I’ve given an inkling of how detailed physical models can be based on something as simple as taking random steps. By making a good choice of random walks, we can sample huge domains in a systematic way that gives us useful results, without having to check every possible outcome (for example, every way a particle might go). We can then link the theory of microscopic behaviour to macroscopic observables — things we can measure in the lab.

One example, Einstein’s model of Brownian motion and Perrin’s measurement, provided crucial evidence for the existence of atoms at the beginning of the last century, something we take for granted now. But as I mentioned, random walks are everywhere in physics, playing an important role in what are known as Monte Carlo simulations.

References & Further Reading

• Werner Krauth. Statistical Mechanics: Algorithms and Computations, Oxford University Press, November 2006.

• Jos Thijssen. Computational Physics. Cambridge University Press, second edition, March 2007.

• When writing this note, I found this blogpost by Jan Wrobel, who has done something similar to the first simulation. I used his code to improve my walk loops.

Footnotes

1. Your computer is actually generating pseudorandom numbers. A good introduction to random and pesudorandom numbers can be found in this epsisode of In Our Time.

2. Einstein had a spectacular 1905, coming up with an explanation for the photoelectric effect (starting the quantum revolution), special relativity and the mass-energy equivalence as well as giving this explanation of Brownian motion. Each of these four would be deserving of a Nobel prize. It is known as the annus mirabilis. No physicist has felt truly productive ever since.