Random Walks: The √t Law, Recurrence and Lévy Flights

The drunkard's walk

Stand at position 0 on a number line. At every tick of a clock, flip a fair coin: heads means step right, tails means step left. That's the entire definition of the simplest possible random walk, and yet it underlies phenomena as different as pollen grains jittering in water, gas molecules diffusing across a room, and the day-to-day path of a stock price. The walk's simplicity is exactly what makes it powerful — the same handful of statistical facts apply no matter what the "step" physically represents.

Why √t, not t

After n steps of ±1, the position is a sum of n independent random signs. The expected position is exactly zero — positive and negative steps cancel on average — but variance behaves completely differently from expectation: for independent random variables, variances simply add. That single fact drives the whole subject.

X_n = S1 + S2 + ... + Sn        // each Si = +1 or -1, equal probability

E[X_n]   = 0                    // expected position: back at the origin
Var(X_n) = n                    // variance grows LINEARLY with steps
sigma(X_n) = sqrt(n)            // typical displacement grows as sqrt(n)

// After 1,000,000 steps: typically only ~1,000 steps from the start

By the Central Limit Theorem, the distribution of X_n converges to a Gaussian, X_n ~ N(0, n), even though each individual step is a discrete coin flip with no bell curve in sight — a striking emergent regularity out of pure randomness. Shrink the step size and time interval together while keeping this scaling fixed, and the discrete walk becomes continuous-time Brownian motion, whose mean-squared displacement obeys ⟨r²⟩ = 2dDt (d = dimensions, D = diffusion coefficient) — Einstein's 1905 result, later confirmed experimentally by Jean Perrin, which provided some of the first hard evidence that atoms are real.

The diffusion equation is a random walk in disguise

Take the probability distribution of a random walker's position and let the number of steps grow large; it obeys the same partial differential equation as heat flowing through a solid or ink dispersing in water:

dP/dt = D * d2P/dx2                          // the diffusion (heat) equation

P(x, t) = 1/sqrt(4*PI*D*t) * exp(-x^2 / (4*D*t))   // point-source solution

// A Gaussian that widens as sqrt(t)  --  the same sqrt(n) scaling, again

The correspondence runs both ways in practice: physicists solve the heat equation numerically by simulating swarms of independent random walkers (a Monte Carlo method), and conversely compute walk statistics by solving the differential equation directly — two views of the same underlying process.

Recurrent in 1D and 2D, transient in 3D

One of the most surprising results in probability theory, due to George Pólya in 1921, is that dimensionality alone decides whether a random walker is guaranteed to come home:

P(eventually returns to origin):
  1D:  P = 1        // recurrent -- certain to return
  2D:  P = 1        // recurrent -- "a drunk always finds home"
  3D:  P ≈ 0.3405   // transient -- "a drunk bird may be lost forever"
  4D+: P -> 0        // almost never returns

The cutoff at two dimensions has real physical consequences: two diffusing defects confined to a 2D surface are mathematically guaranteed to eventually collide and can react or annihilate, while the same two particles diffusing freely in 3D space can — and often do — drift apart permanently, which is why diffusion-limited reactions behave qualitatively differently in a membrane than in a bulk fluid. A related but distinct variant is the self-avoiding walk, which can never revisit a site it has already occupied — the standard model for a polymer chain in solution, whose end-to-end distance grows as n^ν with the Flory exponent ν ≈ 0.588 in 3D, not the 0.5 of an ordinary unconstrained walk.

Lévy flights, lattices, and where the model bends

Real-world "random walks" rarely draw step lengths from a nice bounded distribution. A lattice random walk restricts steps to discrete grid directions — the classic model for a diffusing gas molecule or a naive maze-solving algorithm. A Lévy flight instead draws step lengths from a heavy-tailed power law: mostly short local hops, punctuated occasionally by a very long jump. That mixture has been observed in the foraging trajectories of albatrosses and sharks hunting sparse, unpredictably distributed prey, and it turns out to be close to the mathematically optimal search strategy whenever targets are scarce and randomly scattered — a genuinely different scaling regime from the tidy √t law of Gaussian random walks.

Financial markets are the most consequential place the pure random-walk assumption breaks down. Louis Bachelier modelled stock prices as Brownian motion back in 1900, five years before Einstein, and geometric Brownian motion still underlies the Black-Scholes option-pricing model — but real markets show fat tails (extreme moves far more frequent than a Gaussian predicts), volatility clustering, and long-range correlations that a simple random walk cannot capture, which is exactly why quantitative finance reaches for Lévy processes and fractional Brownian motion instead.

Where else the walk shows up

Google's original PageRank algorithm models a web surfer as a random walker clicking links; a page's importance is simply the probability the walker sits there at steady state. Markov Chain Monte Carlo constructs a random walk through a space of possible states so that time spent in each state matches its target probability, powering everything from Bayesian statistics to protein-folding simulations. Bacterial chemotaxis achieves directed motion from a biased random walk — E. coli alternates straight "runs" with random "tumbles," simply extending its runs when things are improving up a chemical gradient. And in quantum computing, the quantum walk is the coherent analogue of all this: because probability amplitudes can interfere rather than just add, a quantum walk spreads as t instead of √t, the mathematical engine behind the quadratic speedup in Grover's search algorithm.

Frequently asked questions

Try it live

Every trajectory, distribution and dimension above runs live in Random Walk. Switch between 1D, 2D and 3D, add thousands of walkers, and watch the √t envelope emerge from pure chance in real time.