The walk that comes home

Release a particle and let it wander at random. Ask one question about it: will it ever come back to where it started?

The answer depends on how many dimensions there are, and not by a little. On a line the return is certain. On a plane it is certain. In space it is not: about a third of walks come home and the rest never do.

The theorem, and the number #

Pólya proved the first two cases in 1921. The three-dimensional probability was computed later and is

$$p_3 = 1 - \left[\frac{1}{(2\pi)^3}\int\!\!\!\int\!\!\!\int \frac{d^3k}{1 - \tfrac13(\cos k_x + \cos k_y + \cos k_z)}\right]^{-1} = 0.340537\ldots$$

which is one of Watson’s integrals and has a closed form involving gamma functions. The simulation above reaches 0.348 after four thousand steps and stops moving, which is the sampling error of sixteen hundred walks.

The route to it is worth sketching because it explains where the dimension enters. The expected number of returns is the sum over all times of the probability of being at the origin at that time. A walk of $N$ steps is spread over a region of size $\sqrt N$ in each direction, so the probability of being at any particular site is about $N^{-d/2}$, and the expected number of returns is

$$\sum_N N^{-d/2}$$

which diverges for $d \le 2$ and converges for $d \ge 3$. That is the whole argument. The divergence at $d = 2$ is logarithmic — the sum of $1/N$ — which is why two dimensions is certain to return but takes its time about it, and why the middle curve above is still climbing at four thousand steps and would still be climbing at four million.

Certain, but not quickly #

The word “certain” is doing a lot of work and deserves unpacking, because it coexists with a rather awkward fact.

In one dimension the return is certain and the expected time to return is infinite. Both statements are true simultaneously. Every walk comes home; the distribution of homecoming times has a tail going as $t^{-3/2}$, whose mean does not exist; so the average over walks is dominated by the rare walk that wandered a very long way first.

This is the standard trap in first-passage problems and it recurs everywhere. A process can be certain to happen and have no characteristic time for happening. Anything that quotes a mean waiting time for such a process is quoting a number set by the longest run in the sample rather than by the physics, and the honest summary is the median, or the whole distribution.

The smallest amount of bias destroys all of it #

Every statement so far is about an unbiased walk. Add a drift, however small, and one dimension stops being like two and starts being like a hundred.

A walk on a line with probability $p > \tfrac12$ of stepping right returns to the origin with probability $(1-p)/p$, which is less than one for any bias at all. There is no threshold: a bias of one part in a million makes the walk transient, with a return probability of $0.999998$ rather than $1$, and the walk that does not return is gone for ever.

The reason is that the drift eventually beats the diffusion. After $N$ steps the systematic displacement is $(2p-1)N$ and the random spread is $\sqrt N$, so however small the bias the first outgrows the second — at a time $N \sim 1/(2p-1)^2$, which is where the walk stops being a random walk and becomes a slow journey with a wobble.

That crossing time is the single most useful number in the subject. Below it, transport is diffusive and the distance goes as the square root of the time; above it, transport is ballistic and the distance goes as the time. Every practical question about mixing, sedimentation or drift in an electric field is really a question about which side of that crossing the situation sits on, and the crossing is set by the ratio of the drift speed to the diffusion constant — a length, the same length that decides how far a pollutant travels before spreading dominates.

So the sharp dimensional statement at the top of this page is a statement about a symmetric world, and the symmetry is fragile. What survives generally is the crossing length, and that is what an experiment usually measures.

What the walk actually covers #

The recurrence property has a geometric shadow that is more useful than the theorem itself: how many distinct sites a walk visits.

In one dimension a walk of $N$ steps reaches about $\sqrt N$ and visits essentially all of the interval it reaches — the range and the number of distinct sites are the same order. In two dimensions it reaches $\sqrt N$, so its range has area $N$, and it visits about $\pi N/\ln N$ distinct sites: nearly the whole of its own territory, up to a logarithm. In three it reaches $\sqrt N$, its range has volume $N^{3/2}$, and it visits about $0.66 N$ sites — a vanishing fraction of the region it has been through.

Those three behaviours are usually summarised by saying that a walk in two dimensions or fewer is compact and in three or more is not, and the consequence is direct: a compact walk thoroughly searches its neighbourhood before leaving it, and a non-compact one rattles about in a region it barely touches.

Why chemistry cares #

The compactness is what makes the dimension a physical fact rather than a curiosity, and the argument is about meeting.

Two molecules diffusing toward a reaction have to find one another. In three dimensions the rate at which a diffusing partner is captured by a sphere of radius $a$ is the Smoluchowski result $4\pi D a$: it depends on the size of the target and reaches a steady value, because a walk that misses is unlikely to come back and try again. There is a well-defined rate constant.

In two dimensions there is no such constant. The steady-state capture problem has no solution — the flux depends logarithmically on the size of the whole system — because a walk that misses the target will come back and try again, and again, until it succeeds. The consequence is that a reaction confined to a membrane is far more efficient per encounter than the same reaction in solution, and its rate depends on the size of the membrane rather than on the size of the target.

The same reasoning explains a fact about heat that looks unrelated: conduction through a gas is a random walk carrying energy, and the reason it is so much slower than convection is that a compact search of a small region is a poor way to cross a large one.

This is not a small effect and biology exploits it heavily. Reducing a search from three dimensions to two — by binding to a surface, threading along a polymer, or confining to a lipid bilayer — converts a non-compact search into a compact one and dramatically raises the chance of finding a specific site. A protein looking for a particular sequence on a long molecule of DNA does exactly this: it binds non-specifically, slides in one dimension, releases, and repeats, and the alternation between one dimension and three is what makes the search fast.

A target presenting an area to something arriving at random is the whole story in three dimensions: the capture rate follows from the size of the target, and doubling the radius doubles the rate. In two it is not the story at all. The arriving particle keeps coming back — it is recurrent — so it samples the neighbourhood over and over, and the rate stops depending on the target’s size in the way the picture suggests. Doubling the radius in two dimensions changes the rate by a logarithm.

The version with money in it #

The one-dimensional case has an old name and an old application, and it makes the certainty concrete.

A gambler with $n$ pounds playing a fair game against an opponent with $m$ is executing a symmetric random walk between two absorbing walls. The probability of reaching $n+m$ before reaching zero is $n/(n+m)$, exactly, and the expected number of games is $nm$. Against an infinitely rich opponent — $m \to \infty$ — the probability of eventual ruin is one.

That is the recurrence theorem wearing a hat. The walk is certain to reach zero because it is certain to reach every value, and the only thing the opponent’s wealth buys is time. The expected duration $nm$ is the useful part: a gambler with a hundred pounds against a house with a million plays a hundred million games on average before being ruined, which is why a fair game feels safe and is not.

The physical versions are the same arithmetic. A colloidal particle in a well of finite depth escapes with certainty; an ion crossing a membrane channel either reaches the far side or comes back; a nucleus above the fission barrier separates or reassembles. In each case what is wanted is not whether the event happens but the splitting probability between two outcomes, and the answer is a ratio of distances exactly as it is for the gambler.

The number of ways of arriving at each net displacement after a fixed number of symmetric steps has its peak at zero, and that peak is why the walk keeps coming back in low dimensions. The width of the distribution grows as the square root of the count, so the density at the origin falls as $n^{-d/2}$ — and whether the walk returns infinitely often is decided by whether the sum of those densities diverges, which it does for $d \le 2$ and does not for $d \ge 3$.

The step of the walk this essay counts is a molecule’s path between collisions, and the step length sets the scale on which any of it becomes physical. Below the mean free path there is no walk at all, only free flight — so a “random walk” description of a gas is a statement about distances much longer than one collision, and every result here is asymptotic in that ratio.

Where the dimension is not an integer #

Several physical situations are effectively neither two-dimensional nor three, and the criterion generalises cleanly enough to say what happens.

The condition for recurrence is that $\sum N^{-d_s/2}$ diverges, where $d_s$ is the spectral dimension — the exponent governing how the return probability falls with time, which for an ordinary lattice equals the geometric dimension and for a disordered structure does not. A percolation cluster at its threshold has $d_s \approx 1.33$ regardless of the space it is embedded in, so a walk on one is recurrent even in three dimensions. The same is true on many polymer networks and porous solids.

So the correct statement of the theorem is not about space but about connectivity, and the number two is a property of how a structure branches rather than of how many directions there are. That is a good example of a rule whose obvious variable turns out not to be the operative one.

A spreading concentration profile is the continuum face of the same walk, and everything about it is identical in every dimension up to a constant. That is exactly why the diffusion equation on its own never reveals the property this essay is about: recurrence is a statement about individual trajectories, and the averaged description has thrown those away. Two descriptions of the same process, and only one of them can be asked whether a particle comes home.

The continuum has the same problem, in different words #

Nothing above needs a lattice. The continuum version is the return of a Brownian path to a point, and it fails in a way that says something.

A Brownian path in two or more dimensions never returns to the point it started from — the point has measure zero and the probability of hitting it exactly is zero in every dimension above one. What survives is the return to a small ball around the origin, and the answers reproduce the lattice ones: in two dimensions the ball is hit with certainty however small it is, and in three the probability is $a/r$ for a ball of radius $a$ starting at distance $r$, which goes to zero as the ball shrinks.

That $a/r$ is worth recognising: it is the same function as an electrostatic potential, and the connection is exact. The probability of a Brownian path ever hitting a region is a harmonic function of where it starts, satisfying Laplace’s equation with the value one on the region and zero at infinity — so it is literally the potential of a conductor held at unit voltage, and the capacitance of a shape is, up to constants, the rate at which random walks find it. Rate constants for diffusion-limited reactions and capacitances of oddly shaped electrodes are the same table of numbers.

What it means for a measurement #

The practical residue of all this is a warning about what a diffusion experiment can be expected to show.

The mean square displacement is the standard observable and it is blind to everything in this essay. It grows in proportion to time in one dimension, two and three; it is identical for a compact walk and a non-compact one; and a curve of it carries no information at all about whether the walker has been anywhere twice. Two systems whose reaction kinetics differ completely can have indistinguishable mean square displacements.

What does distinguish them is anything that counts encounters: a reaction rate, a fluorescence quenching, a survival probability, the number of distinct sites visited. Those quantities are hard to measure and they are where the dimension shows up.

The general shape of the lesson is one this collection meets often. An averaged quantity can be complete about the average and silent about the property that matters, and the remedy is to find an observable that depends on individual histories rather than on the ensemble. The distribution of molecular speeds carries information the mean speed cannot, for the same reason and in the same way.

The other recurrence theorem, and the objection it answered #

There is a second theorem with the same headline and a very different reach, and putting the two side by side sharpens what “certain” is worth.

Poincaré showed in 1890 that any bounded mechanical system whose energy is conserved returns arbitrarily close to its starting configuration, given long enough. The argument is a counting one: the system’s state wanders through a region of finite volume without ever visiting the same point twice at the same energy, so the neighbourhoods it visits must eventually overlap.

Zermelo turned that on Boltzmann in 1896 as an objection of exactly Loschmidt’s kind. If every gas returns to its initial state, no quantity describing it can increase for ever, and the second law cannot be a theorem of mechanics.

The answer is the one this essay’s first section gives about the walk on a line: certain and useless. The recurrence time for a mole of gas is of order $e^{N}$ with $N$ around $10^{23}$ — a number whose exponent is larger than any count of anything, and against which the age of the universe is indistinguishable from zero. Boltzmann’s reported reply to Zermelo was that he should wait that long.

The pairing is worth carrying. Both theorems establish that something must happen; neither says anything about when; and in both cases the physics is entirely in the waiting time rather than in the certainty. A proof of inevitability that carries no timescale is compatible with the thing never being observed.

The same theorem, in a grid of resistors #

Pólya’s result has a restatement that involves no probability at all, and the translation is exact rather than analogical.

Replace every bond of the lattice with a one-ohm resistor and ask for the resistance between one node and infinity. In one and two dimensions that resistance is infinite; in three and above it is finite. And the theorem is that a walk is recurrent precisely when the resistance to infinity is infinite.

The reason the two questions are the same is that both are governed by the same discrete Laplace equation. The probability that a walk starting at a node reaches infinity before returning home is, node for node, the voltage that appears there when the origin is held at zero and infinity at one — so a walk escapes with some probability exactly when a current can escape, and the escape probability is a conductance.

Read physically, the statement is about how many routes there are. A two-dimensional lattice offers a number of parallel paths to distance $r$ that grows too slowly to keep the resistance bounded; a three-dimensional one offers enough. The walk gets away for the same reason the current does, and neither is more fundamental than the other.

It is a good example of a translation that makes a hard question easy. Comparing resistances is something anyone can do by inspection and bounding, and Pólya’s theorem follows from a network argument in a page — which is considerably shorter than the integral this essay quotes for the three-dimensional case.

What the picture cannot show #

The three-dimensional curve is flat only in the sense that its remaining growth is invisible. The simulation runs four thousand steps and the return probability at infinite time is 0.3405; at four thousand steps it is a fraction below it, and the approach goes as $N^{-1/2}$, so a run a hundred times longer would move the figure in the third decimal place. Nothing finite can distinguish a curve that has stopped from one still creeping.

The walk drawn is on a lattice with unit steps. The theorem does not care — any walk with finite step variance is recurrent or transient according to the same rule — but a walk whose step lengths have an infinite variance, a Lévy flight, is a different problem with a different answer, and several physical searches are better described that way.

The two-dimensional certainty is a statement about infinite time in an infinite plane. Any real membrane has an edge, and a walk on a finite domain either leaves or is reflected; both boundary conditions change the answer, and for a small enough domain the distinction between two and three dimensions stops meaning anything.

And nothing here is about interaction. The walkers do not see each other and do not see the medium. Real diffusion in a crowded cell is hindered, correlated and often not even proportional to time — the mean square displacement can grow as a power less than one — and where that happens the exponent, not the dimension, decides the recurrence.

The ladder from here #

Later rungs on this anchor: first-passage times and their heavy tails, and why a mean waiting time is often the wrong summary; the Smoluchowski rate and its two-dimensional failure worked out properly; anomalous diffusion, where the mean square displacement is not proportional to time and the whole classification has to be redone against the exponent; the equivalence between hitting probabilities and electrostatic potentials, which turns a table of capacitances into a table of reaction rates; and diffusion-limited aggregation, where the walkers stick when they meet and build a fractal whose dimension is set by the same argument.

The neighbouring ladders are the diffusion equation, which is the averaged description this essay’s property is invisible in, and Brownian motion as evidence for atoms, where the individual trajectory was first taken seriously. How far a molecule gets between collisions sets the step length that everything here is counted in.