The walk that becomes a curve

A walk of a hundred steps looks like a walk. A walk of a hundred thousand steps, drawn at the same scale, is a smear a metre wide; drawn to fit the page, it is a walk of a hundred steps again. Something is preserved by that rescaling, and it is not the steps.

The three panels are not three walks. They are the same walk under three magnifications, and the only thing done to make them comparable is the choice of vertical scale. Divide the width of the window by ten and divide the height by the square root of ten, and the picture does not change. Divide the height by ten as well and the walk flattens into a line; divide it by nothing and the walk shoots off the top. Only one exponent leaves anything behind, and finding out which is the whole content of the limit.

Why the square root, and not something else #

The reason is one line of arithmetic and it does not require any limit at all.

A step is $+1$ or $-1$ with equal probability, so its mean is zero and its variance is one. Steps are independent, so variances add: after $n$ steps the position has variance exactly $n$, and its typical size is therefore $\sqrt{n}$. Not approximately — exactly. The figure computes the distribution of the position by convolving the one-step distribution with itself and checks that its variance is $n$ before drawing anything.

So the walk’s displacement over a time $t$ has size of order $\sqrt{t}$, and any rescaling that hopes to keep the picture the same must shrink space as the square root of the factor time is shrunk by. That single relation — space like the square root of time — is what diffusion means, and every consequence below comes from it.

It is worth pausing on how badly it fits intuition about travel. Doubling the time does not double the distance covered; it multiplies it by about $1.41$. Covering ten times the distance takes a hundred times as long. A diffusing quantity is astonishingly bad at getting anywhere, and that is why a room full of still air takes hours to carry a smell across it while a draught does it in seconds.

What is left when the steps are gone #

Take the limit properly — steps of size $1/\sqrt{N}$ taken $N$ times per unit of time, with $N$ growing without bound — and the sequence of walks converges to an object called Brownian motion. It is a genuine mathematical object with three properties worth stating, and they are strange in a way the picture only hints at.

It is continuous. The path has no jumps, which is inherited from the steps shrinking to nothing.

It is nowhere differentiable. No point of the path has a tangent. The reason is the square root: over an interval of length $h$ the path moves about $\sqrt{h}$, so the difference quotient is about $\sqrt{h}/h = 1/\sqrt{h}$, which grows without bound as $h$ shrinks. That is the same arithmetic as the curve with a corner at every point, arrived at from probability rather than from a construction, and the two objects are close cousins — one built by summing a series designed to be rough, the other by summing noise that is rough for free.

It is self-similar. Multiply time by $c$ and space by $\sqrt{c}$ and the object has the same distribution as before. The three panels of the first figure are a picture of this, and the panels are honest about their status: they are one sample at three scales, and what the theorem says is that the distributions agree.

The position, exactly #

The right-hand panel of the first figure is doing something the left-hand panels cannot, and the difference matters. The three walks are one sample; the distribution is computed.

After $n$ steps the position is a sum of $n$ independent $\pm 1$ terms, whose distribution is a binomial, and the generator builds it by repeated convolution rather than by simulation. Standardised — shifted to mean zero and divided by $\sqrt{n}$ — those distributions march in on the bell curve, and the largest gap between the two cumulative distributions falls from $0.187$ at four steps to $0.025$ at two hundred and fifty-six.

That gap is the quantity to watch, because it is the whole of the convergence: the walk becomes a curve exactly to the extent that the position becomes normal. Where that convergence comes from is the first rung of a different ladder, and how fast it happens is the third rung of it. Here it is the engine rather than the subject.

The two scalings deserve separating, because they are constantly confused.

Divide by $n$ and the walk goes to zero: the average step is zero and the average of the steps converges to it. Divide by $\sqrt{n}$ and something non-trivial survives. The first scaling is why a walk has no drift; the second is why it has a shape. Both are true of the same sequence at the same time, and neither implies the other.

A recurrence that turns into an equation #

The most useful consequence of the limit is that it converts a two-line recurrence into a differential equation, and once there, everything known about that equation applies to the walk.

Write $p(x, t)$ for the chance of being at $x$ after $t$ steps. Then

$$p(x, t+1) = \tfrac{1}{2}p(x-1, t) + \tfrac{1}{2}p(x+1, t),$$

which says that to be somewhere now, the walk was next door a moment ago. Subtract $p(x,t)$ from both sides and the right-hand side becomes half the second difference in space — the discrete second derivative. Under the diffusion scaling the time step and the square of the space step vanish together, and what is left is

$$\frac{\partial p}{\partial t} = \frac{1}{2}\frac{\partial^2 p}{\partial x^2},$$

the heat equation. The rate of change in time is proportional to the curvature in space: where the distribution is peaked, it falls; where it is dished, it fills.

That the two subjects share an equation is not a metaphor. Heat spreads because energy is carried by particles that are, to a good approximation, doing exactly this walk, and the appearance of the same equation in both places is one of those coincidences that turns out to be an identity. The solution starting from a single point is the bell curve of width $\sqrt{t}$, which closes the circle: the walk’s position after $t$ steps and the temperature after time $t$ from a point source are the same function.

What survives the limit, and what does not #

Some facts about walks pass to the curve unchanged and some are destroyed, and which is which is not obvious from the outside.

Recurrence survives. A one-dimensional walk returns to its start infinitely often, and so does Brownian motion. The dimension at which this stops being true is the same in both, which is a strong hint that the property belongs to the scaling rather than to the steps.

The arcsine law survives. The fraction of time a walk spends on one side of its start has the same distribution in the limit, and the limit is where the law is cleanest to state.

Total length does not survive. A walk of $n$ steps has travelled a distance $n$, and the limiting curve has infinite length over every interval, however short. The path length goes to infinity while the displacement stays finite, which is why the limit has no velocity and why an integral against it needs a definition of its own.

And the lattice does not survive. A walk is on the integers; the limit is on the whole line, and questions about the walk’s parity — that it can only be at an even position after an even number of steps — have no counterpart at all. That is the cleanest example of a property that is real, checkable, and simply not there afterwards.

Two dimensions, and the same exponent #

Nothing in the argument used the line. A walk on the plane takes a step north, south, east or west; its two coordinates are independent walks of their own, each with variance $t$; and the same rescaling produces the same limit in each coordinate at once.

The picture makes the exponent visible in a way the one-dimensional version does not. A walk that got anywhere would fill a disc of radius proportional to its step count; this one fills a disc of radius proportional to the square root, so quadrupling the number of steps doubles the width of the blot and leaves it looking exactly the same. Everything about the drawing except its scale is unchanged, which is self-similarity seen sideways.

Two dimensions is also where the limit acquires a property the line does not have. Planar Brownian motion visits every neighbourhood of the plane, again and again, and yet the set of points it actually lands on has zero area — a curve of infinite length that misses almost everything it passes through. That combination is not available to any object that can be drawn, and it is the point at which the limit stops being a tidied-up walk and becomes something else.

Where it fails #

The limit requires the step distribution to have a finite variance, and the requirement is not a technicality.

If the steps are drawn from a distribution with heavy tails, the sum is dominated by its largest term rather than by the accumulation of many, and no rescaling produces a bell curve. The average of such quantities never settles at all, and the corresponding limit is a jump process rather than a continuous curve — a path that sits still and then leaps, at every scale.

This is the sharpest available answer to why the diffusion limit looks universal. It is not that any random walk becomes Brownian motion; it is that any walk with a finite step variance does, and the shape of the limit depends on the step distribution only through that one number. The condition is invisible in the picture and decisive in the mathematics.

What the picture cannot show #

The three panels show one walk, and the claim is about a distribution. A different seed gives three different panels that are, again, the same picture as each other — and no number of seeds establishes the theorem, which is about all of them at once.

The limit object cannot be drawn at all. Every drawn path has finitely many vertices and is therefore piecewise straight, so it has a tangent almost everywhere, which the limit does not have anywhere. What is on the page is always a walk pretending to be a curve, and the pretence gets better as the vertices get closer without ever arriving.

Nor does the picture show the convergence in the sense the theorem means. Two random objects are close when the probabilities they assign to sets are close — not when their sample paths are near each other, which they need not be. The right-hand panel is the honest half: it draws distributions, and distributions are what converge.

Where it came from, three times #

The limit was found three times in twenty-three years by people who were not looking for each other’s problem, which is a fair sign that it is the natural object rather than a construction.

Bachelier wrote it down first, in 1900, in a thesis about prices on the Paris exchange. He derived the heat equation for the distribution of a price, solved it, and used the solution to value an option — five years before Einstein and seventy before the subject caught up with him. His examiners thought the topic beneath the mathematics, and the thesis was ignored for half a century.

Einstein reached the same equation in 1905 from the opposite end: he wanted an observable consequence of the atomic hypothesis, argued that a suspended grain is bombarded by molecules and therefore performs a walk, and predicted that the mean square displacement grows in proportion to time rather than to its square. That prediction is the square root again, stated as a claim about the world, and Perrin’s measurements of it a few years later are what settled the existence of atoms.

Wiener supplied what neither had: a proof that an object with the required properties exists at all. Constructing a random continuous function is not free — most attempts produce something with no paths, or with paths that are not continuous — and the measure he built in 1923 is why the limit can be treated as an object rather than as a manner of speaking.

The ladder from here #

Below: the walk that comes home, the fold that counts constrained paths, the time spent one-sided and the game between two barriers, whose parabola $k(N-k)$ is the same parabola the continuous version gives. Sideways: the bell curve from coin flips and the shape that averaging leaves alone, which is why the limit is this curve and not another. Above: stochastic calculus, where the fact that the limiting path has infinite length forces a new definition of the integral, and the correction term that definition carries is the reason the subject exists.

One exponent, and what it decides #

The lasting point is that a limit had to be searched for. Shrinking the steps of a walk destroys it; stretching the time destroys it the other way; and between the two failures there is exactly one exponent that leaves something behind.

That is a common shape and it is worth recognising in the wild. The rescaling that turns a lopsided distribution into a bell is the same manoeuvre, and so is the magnification under which a curve becomes straight — in each case the object of interest is invisible until the right power is divided out, and finding that power is most of the work. The answer here is one half, it comes from variances adding, and everything else in this rung is a consequence of it.