Random walk recurrence
A Socratic walk-through of random walk recurrence — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #Why is a wanderer stumbling at random across a plain certain to find home, while one wandering in three dimensions may never?
A man leaves a tavern and staggers off, each step chosen at random with no memory of the last. Left as often as right, north as often as south. Given forever, does he find his door again? The intuition splits two ways at once. He has no idea where home is, so it seems he could drift away and never come back — yet he also has forever, and forever is a long time.
The startling part is that the answer depends on nothing about him. It depends on how many directions he has. On a line and on a plane, return is certain. Add a third dimension and it is not — a walker in space returns with probability about 0.34, and with probability about two-thirds simply never comes home. Kakutani's line for it: a drunk man will find his way home, but a drunk bird may not. Why should a mere count of directions decide something so absolute?
Reasoning it through
REASONING #Start by asking a question we can actually answer. Rather than "does he ever return", ask: how many times, on average, is he standing at the origin? Count the start as one visit and every later moment he happens to be home as another.
Why is that easier? Because visits compose neatly. Suppose the chance of ever returning at least once is q. If he does return, he is at the origin having forgotten everything — the walk from there is a fresh copy of the original. So the chance of at least two returns is q², of three, q³, and the expected number of visits is the sum of that geometric series: 1/(1 − q). If return is certain, that count is infinite; if return is uncertain, it is finite. The two questions are one question — and the second yields, because the expected number of visits is simply the sum, over every time step, of the probability of being home at that step.
So how likely is he to be home at step n? After n random steps he has typically wandered a distance of about √n — the characteristic square-root spread of a random walk. In d dimensions, that puts him somewhere inside a blob of radius √n, which contains roughly n^(d/2) sites. He is not uniformly spread over that blob, but the middle of it is where he most likely is, and the chance of standing on any one particular site there — the origin included — falls off like 1/n^(d/2).
Now add those up over all n. In one dimension the terms behave like 1/√n, and that sum diverges. In two dimensions they behave like 1/n, the harmonic series — famously, just barely divergent. In three, like 1/n^(3/2), which converges. There is the whole answer, sitting in the exponent. Recurrence in one and two dimensions, and not in three, is Pólya's theorem of 1921.
Do you see what makes two dimensions the knife-edge? The plane is recurrent by the thinnest possible margin — the harmonic series diverges more slowly than almost anything. And once the sum converges, the total is a finite number G, so q = 1 − 1/G. For the three-dimensional lattice that constant works out to about 1.5164, giving a return probability of 0.3405.
The analogy
THE ANALOGY #Think of the origin as a single fixed shop, and the walker as a customer whose whereabouts each day is scattered over a town that keeps growing. In a town growing as one street, the shop keeps a decent share of the whole, and over a lifetime he is bound to pass it. In a town growing as a plane, that share shrinks faster — but only just slowly enough that the passes still accumulate without limit. In a town growing as a stack of levels, the share collapses so fast that his expected number of visits over all eternity is a small finite number.
A customer's daily positions are independent draws, whereas a walk is a continuous path with memory of place — consecutive positions are neighbours, not fresh samples — so the analogy gets the counting right while badly misrepresenting the correlations, which is exactly why the exponent, not the shrinking share alone, is what has to be summed.
Clarifying the model
THE MODEL #Three refinements, because the statement is easy to over-read.
"Certain to return" is not "returns soon". In one dimension the walker comes home with probability 1, yet the expected time until he does is infinite — the occasional excursion is so long that it swamps the average. Mathematicians call this null recurrence, and it means the guarantee is real but pays no dividend you could plan around.
The dimensions are not a metaphor for difficulty. The result holds for the simple symmetric walk on a lattice, and the exponent argument is genuinely about how fast volume grows with radius. It is also robust: by the Chung-Fuchs theorem, any walk in one or two dimensions with zero mean drift and finite variance is recurrent, whatever the step distribution — so the two-dimensional plane is recurrent for reasons deeper than the particular lattice.
And the certainty is fragile in the way certainties usually are. Give the one-dimensional walker even a slight bias — 51 to 49 — and recurrence vanishes; he escapes with positive probability. Recurrence in low dimensions is a property of perfect symmetry, not of low dimensions alone.
A picture of it
THE PICTURE #How to readEach bar is one lattice, and its height is the probability that a walker starting at the origin ever stands there again. Read left to right and the story is a cliff, not a slope: full height at one and two dimensions, then a drop to about a third at three. After that the decline is gentle and, importantly, never reaches zero — in every dimension some walkers do come home, and the bars are Pólya's constants for each lattice.
What became clearer
WHAT CLEARED #The question "will he return?" is answered by a different question: "how many visits does he expect?" Those two are linked by a geometric series, and the second reduces to summing the chance of being home at each step. That chance decays like 1/n^(d/2), so everything hangs on whether that sum diverges — and it does exactly when d is 1 or 2. The wanderer is not defeated by space being large; he is defeated by space growing faster than his path can fill it.
Where to go next
ONWARD #- Why the same divergence criterion decides whether two independent walkers ever meet.
- How recurrence changes on a tree or an expander graph, where volume grows exponentially rather than polynomially.
Key terms
TERMS #| Term | What it means |
|---|---|
| Recurrent walk | one that returns to its starting point with probability 1. |
| Transient walk | one with a positive chance of never returning. |
| Null recurrence | return is certain, but the expected time until it happens is infinite. |
| Polya's theorem | the 1921 result that the simple symmetric lattice walk is recurrent in one and two dimensions and transient in three or more. |
Every term the collection defines is gathered in the glossary.