The ground a walk covers

A walk that always comes home, until it does not asked where a random walk ends up and whether it comes back: on a line and on a grid it returns with certainty, in space it escapes with probability about two thirds. A different question sounds similar and has a more surprising answer. Not does the walk come back, but how much of the world does it see? Count the distinct places a walk has stood on after $n$ steps. That count, the walk’s range, is a measure of how efficiently it explores — and how efficiently a random search, a diffusing molecule or a foraging animal covers ground.

A walk is mostly revisiting #

The picture is the first surprise, and it is worth pausing on before any formula. A walk has no memory, no plan and no aversion to where it has been; nothing pushes it towards unexplored ground, and nothing holds it back from ground it has already covered. The picture is simply what that indifference looks like after 1,500 steps. A walk of 1,500 steps on the square grid stood on only 562 different squares; the rest of its time was spent on squares it had already visited, some of them many times. The shaded region is not a thin path but a blotch with holes, and the walk has criss-crossed it again and again.

On a line the effect is extreme. A walk on the integers can only ever have explored an interval — every point between the lowest it has reached and the highest — and the range is that interval’s width.

After 3,000 steps this walk has explored 111 sites. A walk’s typical distance from its start grows like $\sqrt n$, as the walk that becomes a curve showed, and the explored interval grows the same way — its expected width is $\sqrt{8n/\pi} \approx 1.6\sqrt n$, about 87 for 3,000 steps, and this walk happened to range a little wider. So in one dimension a walk of $n$ steps sees about $1.6\sqrt n$ places: after a million steps, about 1,600. The share of steps that land somewhere new falls like $1/\sqrt n$, and a long walk on a line is almost entirely repetition.

The constant has a clean origin. The width of the explored interval is the walk’s maximum minus its minimum, and each of those, by the reflection argument, is distributed like the walk’s distance from its start; the expected distance of a walk of $n$ steps from zero is about $\sqrt{2n/\pi}$, and the maximum and the minimum contribute one such amount each.

Three dimensions, three answers #

Dividing the range by the number of steps gives the share of steps that found new ground, and the three dimensions give three different kinds of answer. On the line the share falls like $1/\sqrt n$. In the plane it falls too, but only like $\pi/\log n$ — at 10,000 steps it is still 0.29, and at a billion it would be about 0.15. In space it does not fall at all: it settles at a constant, about 0.66, and two thirds of a long three-dimensional walk’s steps land on sites never visited before. In more dimensions still the walk has more ways to leave, returns less — its return probability is about 0.193 in four dimensions, 0.135 in five and 0.105 in six — and the share of new ground climbs towards 1: a walk in many dimensions almost never sets foot on the same site twice.

These are the laws Dvoretzky and Erdős established in 1951, and the figure’s dots — averages of 200 simulated walks at each length — follow them. The one- and three-dimensional dots sit on their curves. The two-dimensional dots sit below theirs by about 15% at 10,000 steps, and that gap is itself instructive: $\pi n/\log n$ is the leading term of an expansion whose next term is smaller by only a factor of $\log n$, so the law is approached at the speed of a logarithm, and no computer will ever see it closely.

The share of new ground is the chance of escape #

The three-dimensional constant, 0.6595, is not a new number. It is $1 - 0.3405$, and 0.3405 is the probability that a walk in space ever returns to its starting point — the number Pólya’s theorem made famous and a walk that comes home computed. The fraction of new sites is the fraction of walks that never come back. That is not a coincidence, and the argument is short enough to give in full.

Step $k$ of a walk lands on a new site exactly when the walk from step $k$ looking backwards never revisits its position — when none of the earlier positions equals the current one. Reverse time: the steps taken in reverse order are again a random walk with the same step distribution, starting at the current position. So the chance that step $k$ is new equals the chance that a fresh walk of $k$ steps never returns to its start. Adding over $k$,

$$\mathbb{E}[R_n] = \sum_{k=0}^{n} \Pr(\text{a walk of } k \text{ steps has not yet returned}),$$

an identity of Kesten, Spitzer and Whitman. The summands tend to the probability of never returning at all, so the range divided by $n$ tends to it too. In one and two dimensions that probability is zero — the walk is recurrent — and the share of new ground falls to zero; in three it is 0.6595, and the share settles there.

The words are the general ones for chains of states. The rule that forgets where it came from calls a state recurrent when a chain started there is certain to return, and transient otherwise; a random walk on a grid is a chain whose states are the sites, every site looks like every other, and so either all of them are recurrent or none is. The range identity holds for any such chain that looks the same from every state, and it turns the qualitative distinction — returns or not — into a quantity that can be measured on a single long run: the share of the run spent finding states for the first time.

The survival curves make the identity visible. Each curve is the chance that a walk has not returned by step $k$, and the range is the area under it. In one dimension the chance falls like $1/\sqrt k$ — exactly $\binom{2m}{m}/4^m$ at step $2m$, the formula the figure checked its simulated curve against — and the area up to $n$ grows like $\sqrt n$. In two dimensions it falls like $1/\log k$, and the area grows like $n/\log n$. In three it levels off, and the area grows like $n$. Recurrence and the range are one fact seen twice: a walk that is certain to come back is a walk that spends almost all its time where it has already been.

What the second walk shows #

A longer walk in the plane covers a larger blotch with the same character — 1,493 sites for 4,000 steps, 37.3% new against 37.4% for the first walk’s 1,500. The share has barely moved, as $\pi/\log n$ predicts: going from 1,500 steps to 4,000 changes $\log n$ by only 13%. The holes inside the blotch are the other thing to look at. The walk has passed around them many times without stepping in, and yet it will certainly step into each of them eventually, because a two-dimensional walk visits every site of the grid with probability one. That it takes so long is the slow $\log n$ at work: the walk is recurrent, but barely.

This is why two dimensions is called the critical dimension for a random walk. Above it, the walk escapes and explores efficiently; below it, the walk is trapped near home; in the plane it is exactly on the edge — certain to return, but taking so long about it that it covers nearly a constant share of new ground over any length a computer can simulate. The same criticality makes a fair game between two players last so long, and it is why so many quantities in two-dimensional probability come with logarithms attached.

How many times each site is visited #

The escape identity says more than how many sites are visited; it says how often. In three dimensions, a walk standing on a site it has just discovered will come back to that site with probability 0.3405 and leave it for good with probability 0.6595, and each return is a fresh chance of the same kind. So the number of visits to a site, once discovered, is a geometric count: one visit with probability 0.6595, two with probability $0.3405 \times 0.6595$, three with $0.3405^2 \times 0.6595$, and so on.

The expected number of sites visited exactly $k$ times by a long walk is therefore about $n \times 0.6595^2 \times 0.3405^{k-1}$: roughly $0.43n$ sites visited once, $0.15n$ twice, $0.05n$ three times. Adding over all $k$ gives back $0.6595n$, the range. The walk’s footprint has a definite texture — mostly single visits, a steady fraction of doubles, geometrically fewer of everything above — and the texture is set by the single number that decides whether the walk returns.

In two dimensions there is no such texture. The return probability is 1, the count of visits to a discovered site has no finite average, and a long walk’s footprint is dominated by sites visited many times, with the heavily visited region near the start growing slowly outwards. The blotches in the figures are that footprint: dark with repetition, and ragged at the edge where new ground is still being found.

Covering everything, and the coupon collector #

The range asks how much of an infinite grid a walk sees. The opposite question asks how long a walk takes to see all of a finite graph. On the simplest finite graph — every site joined to every other — a walk is just a sequence of independent uniform choices, and covering all $m$ sites is the coupon collector’s problem: about $m \log m$ steps, the last few sites taking most of the time because each is found only once in $m$ draws.

On a grid the walk cannot jump, so it pays twice: once for revisiting, which the range measures, and once for the last sites, which the collector’s problem measures. That combination is what makes the cover time of a square grid grow like $N^2 (\log N)^2$ rather than the collector’s $N^2 \log N$, and it is the subject of the question below. Randomised algorithms that explore a graph by walking on it — including the Markov chain samplers that explore a distribution rather than a grid — are judged by the same two costs: how quickly they find new states, and how long the last states take to appear.

Where range is the thing measured #

The range is not only a curiosity of lattice walks. A molecule diffusing through a solution, looking for a binding site, performs something close to a three-dimensional random walk, and the efficiency of its search is its range: a searcher in three dimensions finds new ground two thirds of the time and a searcher confined to a membrane, in two dimensions, far less. The difference between the two is the reason a protein searching along a strand of DNA — in one dimension — is thought to alternate one-dimensional sliding with three-dimensional hops through the solution rather than doing either alone.

The same arithmetic governs foraging, the spread of a signal through a network, and the cost of certain randomised algorithms that explore a graph by walking on it. In every case the question is how much of the space the walk has seen, and the answer depends on whether the walk is recurrent: a recurrent walk, however long, revisits far more than it discovers. The time a one-dimensional walk spends on one side of its start, which half the time is the rarest shows is usually lopsided, is another face of the same recurrence — a walk that keeps returning keeps getting stuck in whichever half it last entered.

What the pictures and dots cannot show #

The dots are simulations. Each point on the growth figure is an average of 200 walks, and each survival curve comes from 4,000; they carry sampling noise, and the one-dimensional curve’s agreement with the exact formula is the check that the noise is of the expected size. The laws they are compared with are theorems, and the figures confirm them rather than establish them.

The two-dimensional law is asymptotic. At every length a computer can reach, $\pi n/\log n$ overestimates the mean range, because the correction terms shrink only like $1/\log n$. The figure shows a 15% gap at 10,000 steps, and the gap would still be several per cent at a billion.

The walks are simple walks on grids. Every step is to a neighbour chosen uniformly, on the integers, the square grid and the cubic grid. Walks with longer steps, walks on other lattices, and walks with a drift all have ranges of their own, and the escape identity covers every one of them that looks the same from every site; only the constants change.

And 0.3405 is quoted. Pólya’s return probability in three dimensions is known exactly, as an integral that Watson evaluated in 1939 in terms of complete elliptic integrals; the figure uses its value and checks that the simulated three-dimensional walks level off near $1 - 0.3405$, but it does not compute the integral.

Still open: when the plane is finally covered #

A walk in the plane visits every site eventually, and a natural finer question is how long it takes to cover a region completely. On a finite piece of the plane — a square grid of side $N$ with its opposite edges glued, a torus — the cover time, the number of steps until every site has been visited, grows like $\tfrac{4}{\pi} N^2 (\log N)^2$, a result proved by Dembo, Peres, Rosen and Zeitouni in 2004 after Aldous and others had conjectured its form.

The fluctuations are much harder. The leading term was the work of decades, the size of the next correction was identified only in the last few years, and whether the cover time, suitably centred and scaled, settles to a definite limiting distribution — and what that distribution is — is still being worked out. The difficulty is the one the survival curves show: in the plane, whether a particular site has been visited depends on a logarithmically slow competition between the walk’s tendency to return and its tendency to wander, and the last few unvisited sites are exactly where that competition is closest.

Seeing the world, and coming home #

A random walk’s range is the number of places it has seen, and it grows like $\sqrt n$ on a line, like $n/\log n$ in the plane and like $n$ in space. The three laws are three answers to one question — does the walk come back? — because by a reversal of time, the chance that a step lands somewhere new is the chance that a walk that long has not yet returned. A walker certain to come home spends almost all of its time where it has been before; a walker that can escape keeps finding somewhere new.

The pictures carry the whole argument in miniature. The shaded blotch is the range; its darkness would be the number of visits; its ragged edge is where new sites are still being found; and the fraction of the walk’s steps spent at that edge is, in the limit, the fraction of walks that leave for good.

When a process can revisit its past, the rate at which it finds new states is the probability that it never revisits — which turns a question about exploration into a question about return, and lets the most famous number about random walks, Pólya’s two-thirds, measure how much of space a walker sees.