Random Walks and Diffusion

Random walks are stochastic processes built from successive random steps; diffusion is their continuum limit, described by the heat/diffusion equation. The signature result: mean-squared displacement grows linearly with time,

⟨ x^{2} ⟩ = 2 D t

, not as

t^{2}

. Applies anywhere randomness accumulates — Brownian motion, polymer physics, finance, search algorithms, ecology. Originated with Pearson (1905), Einstein (1905), and Smoluchowski (1906).

A random walk is a sequence of positions generated by adding independent random displacements at each step; the simplest version moves $\pm 1$ on a line with equal probability. As the number of steps grows and step sizes shrink appropriately, the discrete walk converges to a continuous process whose probability density obeys the diffusion equation. This topic matters because it is the universal model for transport driven by random microscopic motion — heat conduction, molecular spreading, stock prices, and population dispersal all share its mathematics. The single most surprising fact is the $t$ scaling: after time $t$ , a diffusing particle is typically displaced only by a distance proportional to $t$ , so doubling the spread requires quadrupling the time — diffusion is intrinsically slow over long distances.

The Core Insight

Independent random steps add in variance, not in distance. Because the variance of a sum of independent random variables is the sum of variances, displacement variance grows linearly with the number of steps. Distance is the square root of variance, so typical displacement scales as $N$ (steps) or $t$ (time). Everything else — the Gaussian shape of the spreading, the diffusion equation, Fick's law — is downstream of this one fact.

Formal Statement

Simple Symmetric Random Walk

Let $X_{1}, X_{2}, \dots$ be independent, identically distributed (i.i.d.) random variables with

P (X_{i} = + 1) = P (X_{i} = - 1) = \frac{1}{2} .

⟳This is the definition of a fair single step; no derivation, it is a modeling choice.

The position after $N$ steps is the partial sum

S_{N} = i = 1 \sum N X_{i}, S_{0} = 0.

⟳Position is the cumulative sum of all displacements taken so far.

Here $S_{N}$ is the integer-valued position, $N$ the number of steps, and each $X_{i}$ a unit step. The walk is symmetric (no drift) and simple (nearest-neighbor steps).

Mean and Variance of the Walk

For the simple symmetric walk:

⟨ S_{N} ⟩ = 0, ⟨ S_{N}^{2} ⟩ = N .

⟳

⟨ X_{i} ⟩ = 0

gives zero mean by linearity; independence makes cross terms vanish, leaving

\sum ⟨ X_{i}^{2} ⟩ = N

since

X_{i}^{2} = 1

The root-mean-square displacement is therefore

x_{rms} = ⟨ S_{N}^{2} ⟩ = N .

⟳Take the square root of the variance in equation [3].

The Diffusion Equation

Let $ρ (x, t)$ be the probability density (or concentration) of a diffusing particle. It satisfies

\frac{\partial ρ}{\partial t} = D \frac{\partial ^{2} ρ}{\partial x ^{2}},

⟳Combine conservation of probability

\partial_{t} ρ = - \partial_{x} J

with Fick's law

J = - D \partial_{x} ρ

where $D$ is the diffusion coefficient (units $m^{2} /s$ ). Its fundamental solution starting from a point source at the origin is the Gaussian

ρ (x, t) = \frac{1}{4 π D t} exp (- \frac{x ^{2}}{4 D t}) .

⟳Substitute the Gaussian ansatz into [5], or use a Fourier transform that turns

\partial_{xx}

into

- k^{2}

and solve the resulting ODE in time.

This gives the continuum mean-squared displacement

⟨ x^{2} ⟩ = \int_{- \infty}^{\infty} x^{2} ρ (x, t) d x = 2 D t .

⟳Compute the second moment of the Gaussian [6]; the variance of

N (0, σ^{2})

σ^{2} = 2 D t

Diffusion Limit of the Random Walk

Take steps of length $Δ x$ every time interval $Δ t$ . If the limit $Δ x, Δ t \to 0$ is taken so that

D \equiv Δ x, Δ t \to 0 lim \frac{( Δ x ) ^{2}}{2 Δ t} is finite and nonzero,

⟳This is the only scaling that keeps the second moment finite — variance per step

(Δ x)^{2}

divided by time per step

Δ t

must stay bounded.

then the probability distribution of the random walk converges to the Gaussian solution [6] of the diffusion equation [5]. This is a manifestation of the Central Limit Theorem.

Why It Holds / Derivation

From Walk to Diffusion Equation

Step 1 — Master equation. Let

P (m, N)

be the probability of being at site

m

after

N

steps on a lattice with spacing

Δ x

. A step arrives from a neighbor:

P (m, N + 1) = \frac{1}{2} P (m - 1, N) + \frac{1}{2} P (m + 1, N) .

⟳To be at

m

now, the walker was at

m \pm 1

and stepped toward

m

, each with probability

\frac{1}{2}

Step 2 — Continuum variables. Write

P (m, N) \to ρ (x, t) Δ x

with

x = m Δ x

t = N Δ t

. Subtract

P (m, N)

from both sides:

P (m, N + 1) - P (m, N) = \frac{1}{2} [P (m - 1, N) - 2 P (m, N) + P (m + 1, N)] .

⟳Add and subtract

P (m, N)

on the right of [9] to expose the discrete second difference.

Step 3 — Taylor expand. The left side

\approx Δ t \partial_{t} ρ \cdot Δ x

; the bracket is the discrete second derivative

\approx (Δ x)^{2} \partial_{xx} ρ \cdot Δ x

Δ t \frac{\partial ρ}{\partial t} = \frac{( Δ x ) ^{2}}{2} \frac{\partial ^{2} ρ}{\partial x ^{2}} .

⟳Expand

ρ (x \pm Δ x)

to second order; first-order terms cancel by symmetry, leaving

(Δ x)^{2} \partial_{xx} ρ

Step 4 — Identify $D$ . Divide by

Δ t

and use [8]:

\frac{\partial ρ}{\partial t} = \frac{( Δ x ) ^{2}}{2 Δ t} \frac{\partial ^{2} ρ}{\partial x ^{2}} = D \frac{\partial ^{2} ρ}{\partial x ^{2}} . ■

⟳Substitute the definition of

D

from [8]; this recovers the diffusion equation [5].

Albert Einstein | 1879–1955

In his annus mirabilis of 1905, Einstein published a paper on Brownian motion that derived the diffusion of suspended particles from molecular kinetics. He showed that observing a pollen grain's $t$ wandering yields the diffusion coefficient, and through the relation $D = k_{B} T / (6 π η a)$ (the Stokes–Einstein relation), a direct measurement of Avogadro's number. This provided some of the strongest contemporary evidence for the physical reality of atoms — later confirmed experimentally by Jean Perrin (Nobel Prize 1926). Marian Smoluchowski reached equivalent conclusions independently in 1906.

Building Intuition

Picture a drunk leaving a lamppost, stepping left or right at random. After one step he is one unit away. After four steps, naive intuition says four units — but the steps partly cancel. On average he ends back at the lamppost ( $⟨ S_{N} ⟩ = 0$ ), yet he is rarely exactly there. The typical distance is $N$ : after 100 steps, about 10 units away, not 100.

Why $N$ ? Imagine the displacement as a tug-of-war between left and right steps. Random cancellation means the imbalance between the two grows like the square root of the count — the same reason a coin flipped 100 times gives roughly $50 \pm 5$ heads, not $50 \pm 50$ . The " $\pm 5$ " is the $N$ fluctuation.

The crucial consequence: diffusion is a fast spreader at short range and a hopeless one at long range. A molecule diffuses across a cell ( $\sim 10 μ m$ ) in milliseconds, but would take years to diffuse across a room — which is why we rely on convection (stirring, breezes) for macroscopic transport.

Random walk trajectory (jagged) versus the smooth $\sqrt{t}$ envelope of typical displacement

Worked Examples

Diffusion of ink in water

Given. A drop of ink is placed at one point in still water. The diffusion coefficient of the dye molecules is

D = 1.0 \times 1 0^{- 9} m^{2} /s

. How long until the dye spreads to an rms distance of

1 cm

? Step 1 — Choose the dimension. In three dimensions,

⟨ r^{2} ⟩ = 6 D t

. We want

⟨ r^{2} ⟩ = 1 cm = 0.01 m

, so

⟨ r^{2} ⟩ = 1 \times 1 0^{- 4} m^{2}

. Step 2 — Solve for time.

t = \frac{⟨ r ^{2} ⟩}{6 D} = \frac{1 \times 1 0 ^{- 4} m ^{2}}{6 ( 1.0 \times 1 0 ^{- 9} m ^{2} /s )} .

Step 3 — Compute.

t = \frac{1 0 ^{- 4}}{6 \times 1 0 ^{- 9}} s = 1.67 \times 1 0^{4} s .

Answer.

t \approx 1.7 \times 1 0^{4} s \approx 4.6 hours

This is why ink spreads visibly only when stirred — pure diffusion over centimeters takes hours.

Counting steps for a target spread

Given. A simple symmetric 1-D walk has step length

Δ x = 0.5 nm

and step interval

Δ t = 1 ns

. (a) Find

D

. (b) How many steps

N

are needed to reach

x_{rms} = 1 μ m

? Step 1 — Diffusion coefficient (part a). Using [8],

D = \frac{( Δ x ) ^{2}}{2 Δ t} = \frac{( 0.5 \times 1 0 ^{- 9} m ) ^{2}}{2 ( 1 \times 1 0 ^{- 9} s )} = \frac{2.5 \times 1 0 ^{- 19}}{2 \times 1 0 ^{- 9}} m^{2} /s .

D = 1.25 \times 1 0^{- 10} m^{2} /s

Step 2 — Steps required (part b). From [4],

x_{rms} = N Δ x

, so

N = (\frac{x _{rms}}{Δ x})^{2} = (\frac{1 \times 1 0 ^{- 6} m}{0.5 \times 1 0 ^{- 9} m})^{2} = (2000)^{2} .

Answer.

N = 4 \times 1 0^{6} steps

Check: total time $= N Δ t = 4 \times 1 0^{6} \times 1 0^{- 9} s = 4 ms$ , and indeed $2 D t = 2 (1.25 \times 1 0^{- 10}) (4 \times 1 0^{- 3}) = 1 μ m$ . ✓

Common Misconceptions

"Displacement grows linearly with time." It does not — for diffusive motion,

⟨ x^{2} ⟩ \propto t

, so displacement

\propto t

. Linear-in-

t

displacement is ballistic motion (

⟨ x^{2} ⟩ \propto t^{2}

), which describes a particle with constant velocity, not a random walker. Confusing these gives errors of many orders of magnitude over long times. "The walker drifts away from the start." With no bias, the expected position stays at the origin forever (

⟨ S_{N} ⟩ = 0

). What grows is the spread (variance), not the mean. A symmetric walk has no preferred direction; it simply becomes more uncertain about where it is.

Recurrence depends on dimension

A natural guess: "a random walker always returns to its starting point eventually." This is true in 1-D and 2-D but false in 3-D. Pólya's theorem (1921) states the simple symmetric walk is recurrent (returns with probability 1) in dimensions 1 and 2, but transient in dimension $\geq 3$ (returns with probability $< 1$ , about $0.34$ in 3-D). As the folklore goes: "A drunk man will find his way home, but a drunk bird may not." See Recurrence and Transience.

Connections

Random walks and diffusion sit at a crossroads of mathematics and physics. The convergence of the rescaled walk to a Gaussian is the Central Limit Theorem in action, since position is a sum of i.i.d. steps. The continuous-time, continuous-path limit is Brownian Motion (the Wiener process), whose increments are Gaussian and independent. The diffusion equation [5] is the Heat Equation under a different name — Fourier's 1822 study of heat conduction and Einstein's 1905 study of particles solve the same PDE. The pathwise calculus of these processes is Itô Calculus and Stochastic Differential Equations, and the macroscopic transport law $J = - D \partial_{x} ρ$ is Fick's Laws of Diffusion. Adding a drift term yields the Fokker–Planck Equation.

Real-World Applications

Brownian motion & atomic theory. Perrin's experiments (1908) on suspended particles confirmed Einstein's prediction and measured Avogadro's number, settling the atomic hypothesis.
Quantitative finance. The Black–Scholes option-pricing model treats log stock prices as a Brownian motion with drift; volatility is the diffusion coefficient.
Polymer physics. A flexible polymer chain is modeled as a random walk of monomers; its size scales as $N$ (ideal chain) or $N^{0.588}$ (self-avoiding walk), governing viscosity and elasticity.
Search and PageRank. Google's original PageRank is the stationary distribution of a random walk on the web graph; randomized search algorithms (random restarts, MCMC) exploit walk mixing.
Heat and mass transport in engineering. Doping profiles in semiconductors, drug release from capsules, and heat treatment of metals are all solved with the diffusion equation [5].
Population ecology & epidemiology. Dispersal of organisms and the spread of genes or disease over space use reaction–diffusion models (Fisher–KPP equation).
Neuroscience. Membrane potential to a firing threshold is modeled as a drift–diffusion process; reaction times in decision tasks fit the drift-diffusion model.

Historical Development

1827 — Robert Brown observes the erratic jittering of pollen grains in water, later called Brownian motion.
1880 — Thorvald Thiele develops an early mathematical treatment of Brownian-like processes in actuarial work.
1900 — Louis Bachelier, in Théorie de la spéculation, models stock prices as Brownian motion — five years before Einstein and decades ahead of his time.
1905 — Albert Einstein derives the diffusion of suspended particles from molecular kinetics, linking $D$ to Avogadro's number.
1905 — Karl Pearson coins the term "random walk" in a letter to Nature, posing the drunkard's-walk problem.
1906 — Marian Smoluchowski independently develops the kinetic theory of Brownian motion.
1908 — Jean Perrin experimentally verifies Einstein's predictions (Nobel Prize, 1926).
1921 — George Pólya proves recurrence in 1-D/2-D and transience in higher dimensions.
1923 — Norbert Wiener gives the first rigorous construction of Brownian motion (the Wiener process), making the continuum limit mathematically precise.

Subtleties & Limits

The clean picture above breaks in several regimes of active research. Anomalous diffusion occurs when $⟨ x^{2} ⟩ \propto t^{α}$ with $α \neq = 1$ : subdiffusion ( $α < 1$ ) appears in crowded cells and disordered media; superdiffusion ( $α > 1$ ) appears in turbulent flows and Lévy flights with heavy-tailed step distributions (where the variance of a single step diverges and the ordinary Central Limit Theorem fails). On disordered lattices and fractals, the effective dimension is fractional and even defining $D$ is subtle. Rigorous understanding of random walks in random environments — where the hopping rates themselves are random — remains incomplete, with surprising phenomena like Sinai's logarithmically slow diffusion. The infinitely jagged, nowhere-differentiable paths of Brownian motion also force a rethinking of calculus, resolved only by Itô Calculus and Stochastic Differential Equations.