A walk that always comes home, until it does not

Stand on a number line. Flip a coin: heads, step right; tails, step left. Repeat forever.

Two questions have very different answers. How far does the walk get? And does it come back?

The distance is a square root #

After $n$ steps the walk is somewhere, and the obvious guess — that it drifts off in one direction or the other — is wrong. The expected position is zero, by symmetry, at every $n$.

That is not the same as saying it stays near zero. The expected distance is what matters, and it grows like $\sqrt{n}$.

The reason is a single line of algebra. Write the position as a sum of independent steps, each $\pm 1$. The variance of a sum of independent things is the sum of the variances, each step has variance $1$, so the position after $n$ steps has variance $n$ and standard deviation $\sqrt{n}$. Nothing about coins entered; it is the additivity of variance.

The consequence is worth stating plainly because it is unintuitive in both directions. A thousand steps takes the walk about thirty-two places from home, not five hundred and not zero. To get twice as far takes four times as long. A walk covering a mile of ground in an hour covers two miles in four hours, and a hundred miles in a year.

That square root is why diffusion is slow at large scales and fast at small ones, and it is the reason living things move molecules by pumping rather than by waiting. Across a cell, diffusion takes a hundredth of a second. Across a metre, at the same rate, it takes about thirty years.

It is also the reason the walk is a poor model of anything with a direction. A walk with the slightest bias — probability $0.51$ of stepping right — drifts linearly at $0.02n$, and linear growth overtakes $\sqrt{n}$ almost immediately: by step two thousand five hundred the drift is the same size as the spread, and after that the spread is a correction. Unbiased walks are the exception rather than the type, and everything in this essay depends on the exact symmetry of the coin.

The envelope is typical, not maximal #

The dashed curves are worth being careful about, because a reader will naturally take them as a bound and they are not one.

$\sqrt{n}$ is a typical distance. Walks exceed it regularly — about a third of the time, since the position is approximately normal with that standard deviation and a normal variable exceeds one standard deviation about a third of the time. The figures above show that happening, and the generator asserts that at least one walk goes outside, because a picture in which they all stayed inside would be evidence for a false statement.

There is a genuine bound and it is much weaker: the law of the iterated logarithm says the walk’s extremes track $\sqrt{2n\log\log n}$, which exceeds $\sqrt{n}$ by a factor that grows without limit, extremely slowly. A walk of a billion steps has $\sqrt{2\log\log n} \approx 2.3$, so the record excursion is a couple of standard deviations out. That factor takes astronomical $n$ to become large, which is why $\sqrt{n}$ works as a rule of thumb.

Where it ends up #

Collect the endpoints of many walks and a shape appears.

The endpoint after $n$ steps is a count of right-steps minus left-steps, so it is a binomial distribution in disguise, and the shape is the one the Galton board makes. Nothing new is happening here; the walk is a board on its side, with the time axis playing the role of the rows.

What the picture adds is the parity. After sixty steps the walk is at an even position, always, because sixty steps of $\pm 1$ sum to something with sixty’s parity. So the distribution lives on every other integer, and a smooth curve drawn through it would be wrong by a factor of two in density. This is a small point and it is exactly the sort of thing that a continuous approximation silently discards.

That the shape arrives so early is worth noticing, and it is the practical form of the central limit theorem: the sum of even a modest number of independent things is already close to normal, whatever the things were. Twenty coin flips is enough. This is why the bell curve turns up in places with no bell-shaped mechanism anywhere — it is not a fact about the ingredients but about addition.

The question that has a surprising answer #

Does the walk return to where it started?

On a line, yes — with probability one. Not merely likely: certain. And not once, but infinitely often, since after each return the walk starts afresh and must return again.

That is already odd. A walk drifts $\sqrt{n}$ away, which grows without bound, and yet it comes back every time.

The resolution is that $\sqrt{n}$ grows slowly enough. The chance of being at the origin after $2n$ steps is about $1/\sqrt{\pi n}$, and the sum of those over all $n$ diverges — it is the harmonic series with a square root in it, which still diverges. A standard argument turns a divergent sum of return probabilities into certainty of return, and a convergent one into a positive chance of escape. So recurrence versus transience is decided by whether a series converges, and the series is the one whose terms are the chances of being home at each time.

Two dimensions, and then three #

On a square grid, stepping one place in one of four directions, the same question has the same answer: return is certain.

The return probability after $2n$ steps in the plane is about $1/(\pi n)$, and the sum of $1/n$ diverges — just barely, which is the harmonic series exactly. So the plane is recurrent, and it is recurrent by the narrowest possible margin.

In three dimensions the probability is about $c/n^{3/2}$, and that sum converges. So the walk escapes.

Pólya proved this in 1921, and the constant for three dimensions is $0.340537\ldots$ — the probability that a walk on the cubic lattice never returns. Rather more than a third of walks leave home permanently.

Kakutani’s summary is the one everyone quotes and it is exact: a drunk man will find his way home, but a drunk bird may not.

What changed at three #

The jump is between two and three, and the arithmetic that decides it is worth seeing rather than accepting.

The chance of being back at the origin after $2n$ steps in $d$ dimensions falls like $n^{-d/2}$. The reason is the square root above: after $2n$ steps the walk is spread over a region of radius $\sqrt{n}$, so it occupies about $n^{d/2}$ sites, and the chance of being at any particular one — the origin included — is the reciprocal of that.

Then the whole question is whether $\sum n^{-d/2}$ converges, which it does exactly when $d/2 > 1$, that is $d > 2$. Two dimensions sits precisely on the boundary and falls on the divergent side, because $\sum 1/n$ diverges.

So the threshold is not a fact about grids or about randomness. It is the convergence of a $p$-series at $p = 1$, which is the same boundary the harmonic series sits on, showing up as a fact about drunks and birds. The same boundary decides whether reordering the terms can change the answer, which is a question about addition and has nothing to do with walking — and yet it is the same threshold, met from the other side.

That is the most satisfying thing in this essay. A question about walking in space is answered by a question about a sum, and the sum is the one that was already famous for sitting on a knife edge.

What it costs #

Simulating a walk is trivial and estimating anything from simulation is not, which is the standing bargain of Monte Carlo methods.

The escape probabilities in the figure above are computed from four thousand walks each, with a cut-off at three thousand steps. Both choices bias the answer, in a known direction: a finite horizon can only over-count escapes, since a walk that would have returned at step ten thousand is recorded as escaped. That is why the one- and two-dimensional bars are not zero, and the essay’s assertions are one-sided accordingly — the generator requires the measured rates to be small rather than zero, and says why.

The error in such an estimate falls as $1/\sqrt{N}$ in the number of trials, which is the same square root as the walk’s own displacement and for the same reason. So a hundred times more computation buys ten times more precision, which is a poor rate and is often the only rate available — the same trade Buffon’s needle makes for $\pi$.

Where random walks earn their cost is in problems no other method reaches: high-dimensional integration, sampling from distributions known only up to a constant, and the whole of Markov chain Monte Carlo. The property that makes them work is exactly the one this essay is about — that a walk explores the space it is in, and whether it explores it exhaustively or escapes depends on the space rather than on the walk.

The recurrence result is what licenses the method. A sampler is a walk on the space of configurations, and the guarantee that it eventually visits everywhere in proportion to the right weights is a recurrence statement about that walk. Where the walk is transient the sampler is broken — it wanders off and never returns to report — and a great deal of the practical craft is in constructing walks that are recurrent on spaces where the obvious walk is not. The drunk-and-bird distinction is not a curiosity here; it is the correctness condition.

Where the small cases lie #

The line is a bad guide to everything above it, and the plane is a bad guide to space.

On the line, return is certain and the number of returns is infinite; the walk crosses the origin over and over, which invites the intuition that random motion is exploratory and thorough. On the plane the same is true, though the returns are much rarer. In three dimensions the intuition is simply false, and there is no smooth transition — the change happens at an integer, and the case that decides it is exactly the boundary case of a series.

A reader forming intuitions from the one-dimensional picture will also expect the walk to spend its time near the origin, and it does not. The arcsine law says that the fraction of time a walk spends on the positive side is least likely to be near a half and most likely to be near zero or one — a walk typically stays on one side for long stretches rather than oscillating. That is the opposite of what the nine-walk figure suggests to most readers, and it is one of the least intuitive facts in elementary probability.

The consequence is worth spelling out because it is routinely misread in practice. In a fair game played a very large number of times, the lead changes hands rarely, and one player is ahead for most of the duration. Long runs are the expectation rather than evidence of anything, which is the same correction the birthday problem makes to intuitions about coincidence — in both cases the naive expectation is of more regularity than randomness actually produces, and in both cases the arithmetic says otherwise.

What the picture cannot show #

Every figure is finite and every claim is about the infinite walk. The lattice figure shows four thousand steps and several returns, and the theorem is that returns happen infinitely often — which no finite drawing can display, and which is the entire content.

The escape figure is worse in an instructive way: it shows a simulation, cut off, of a limit that the cut-off biases. The generator states the horizon and the trial count in the caption for that reason, and asserts only what a finite simulation can support. The true value $0.340537$ is quoted from theory and is not what the bars measure.

Nothing here can show the dimensional threshold, because the threshold is a statement about a series and the two-dimensional case fails to escape by an amount that is invisible at any finite time. A plot of returns in two dimensions against three, run to any length anyone can afford, looks like two similar pictures.

The ladder from here #

Rungs above: the arcsine law, drawn — the time spent on one side, and why a half is the least likely answer. The reflection principle, which counts paths by flipping them and gives the ballot problem and the gambler’s ruin. Gambler’s ruin proper, and why a finite bankroll against an infinite one loses with probability one. The connection to the heat equation, where the walk’s density is a diffusion. Brownian motion as the limit, and the fact that its paths are continuous and nowhere differentiable — which connects this anchor to the slope of a single point. Self-avoiding walks, where almost nothing is proved. And electrical networks, where recurrence becomes a question about the resistance of an infinite grid.

The answer was in a series all along #

The lasting point is where the theorem’s content turned out to live.

The question was geometric and physical: does a wandering particle come home? The answer is decided by whether $\sum n^{-d/2}$ converges. There is no drunk in that sum and no grid, and the number that settles it is the exponent $d/2$, which came from the walk’s spread being $\sqrt{n}$ in each of $d$ directions.

That is the recurring pattern of probability at this level. A question about a process is converted into a question about a series or an integral, and the process’s behaviour is read off the convergence. It is worth carrying because it explains why the subject leans so heavily on analysis, and why a fact about the harmonic series — the most elementary divergent series there is — turns out to be the reason a bird can get lost and a drunk cannot.