Skip to main content

The Random Walk

Module 3: Modelling with Randomness

NoteReading
  • Compulsory: Berg (1993), Chapters 1 and 2.
  • Recommended: Britton (2003), Chapter 5 (Biological Motion).

A random walk is a sequence of positions in which each step is random and independent of the previous ones. Karl Pearson named the problem in a letter to Nature (Pearson 1905). In the same year Einstein’s theory of Brownian motion described a suspended particle through many independent displacements (Einstein 1905). In this module you use random walks to model diffusing molecules, heavy-tailed fluctuations and prices.

The one-dimensional lattice walk

Follow Berg (1993, chap. 1). A particle starts at \(x = 0\) at time \(t = 0\) and obeys three rules:

  • Every \(\tau\) seconds it steps a distance \(\delta\) to the right or to the left.
  • It steps right with probability \(p\) and left with probability \(q = 1 - p\), independently of earlier steps.
  • Different particles move independently of each other.

After \(n\) steps the position is a sum of independent steps \(\xi_i \in \{+\delta, -\delta\}\):

\[ x(n) = \sum_{i=1}^{n} \xi_i . \tag{1}\]

Mean and variance

Each step has mean \((p - q)\delta\) and variance \(4pq\,\delta^2\). Means and variances of independent variables add, so

\[ \langle x(n) \rangle = n (p - q)\,\delta, \qquad \operatorname{Var}[x(n)] = 4 n p q\, \delta^2 . \tag{2}\]

This agrees with the binomial derivation in Berg (1993, Eqs. 1.15 to 1.20). For the unbiased walk, \(p = q = 1/2\), the mean stays at zero and \(\langle x^2(n) \rangle = n\delta^2\). The typical distance from the origin grows as \(\sqrt{n}\), not as \(n\).

Figure 1: Twenty unbiased lattice walks with \(\delta = 1\). The dashed curves are \(\pm\sqrt{n}\), one standard deviation of \(x(n)\).
NoteExercise

Simulate 5000 walkers for 400 steps with \(p = 0.6\) and \(\delta = 1\) using simulate_lattice_walk. Compare the sample mean and variance of \(x(400)\) with Equation 2.

The theory gives \(\langle x \rangle = 400 \cdot 0.2 = 80\) and \(\operatorname{Var} = 4 \cdot 400 \cdot 0.6 \cdot 0.4 = 384\).

from amlab.random_walks import simulate_lattice_walk

rng = np.random.default_rng(0)
x = simulate_lattice_walk(5000, 400, p=0.6, rng=rng)
print(f"mean     {x[:, -1].mean():7.2f}  (theory 80)")
print(f"variance {x[:, -1].var():7.2f}  (theory 384)")
mean       79.92  (theory 80)
variance  394.05  (theory 384)

What the model leaves out

The lattice walk ignores inertia: successive steps are uncorrelated. Berg (1993, chap. 1) estimates that a protein such as lysozyme in water takes about \(10^{12}\) such steps per second, so the memory of each step is lost almost at once. Walks with memory or with long jumps behave differently; you meet one kind in Lévy flights.

References

Berg, Howard C. 1993. Random Walks in Biology. New and expanded. Princeton University Press.
Britton, Nicholas F. 2003. Essential Mathematical Biology. Springer Undergraduate Mathematics Series. Springer. https://doi.org/10.1007/978-1-4471-0049-2.
Einstein, Albert. 1905. “Über Die von Der Molekularkinetischen Theorie Der Wärme Geforderte Bewegung von in Ruhenden Flüssigkeiten Suspendierten Teilchen.” Annalen Der Physik 322 (8): 549–60. https://doi.org/10.1002/andp.19053220806.
Pearson, Karl. 1905. “The Problem of the Random Walk.” Nature 72: 294. https://doi.org/10.1038/072294b0.