A walk that may not step where it has been

The ground a walk covers found that an ordinary random walk spends almost all of its time where it has already been: in the plane, fewer than a third of a long walk’s steps land anywhere new. The natural opposite is a walk that is forbidden to revisit — every step must go to a site the walk has never stood on. That is a self-avoiding walk, and the rule is so simple it seems impossible that anything about it could be hard.

Almost everything about it is hard. How many self-avoiding walks of $n$ steps are there? There is no formula. How fast does their number grow? On the square grid, nobody knows the rate exactly. How far does a typical one reach? Physicists have known the answer for seventy years, and there is still no proof. The walks were introduced by the chemist Paul Flory as a model of a polymer — a long molecule that cannot pass through itself — and they remain one of the simplest questions in probability whose answers are guessed rather than proved.

Counting by hand, and then by machine #

The first step has four choices. Every later step has at most three, since it cannot go straight back. So there are $4 \cdot 3 = 12$ two-step walks, and $4 \cdot 3 \cdot 3 = 36$ three-step walks — every one of them self-avoiding, because a walk needs four steps to close a square. At four steps the first collisions appear: of the $4 \cdot 3^3 = 108$ walks that never reverse, the 8 that trace a unit square return to their start, leaving 100. The figure draws all hundred.

From there, collisions multiply. There are 284 walks of five steps, 780 of six, 2,172 of seven, and 881,500 of thirteen, and the only known way to find these numbers is to generate the walks, or to count them by increasingly clever versions of generation. The figure’s counts come from an exhaustive depth-first search, which tries every step at every length and backs up at every collision, and each was checked against the published sequence. The record enumerations, using methods that count without listing, reach beyond $n = 70$ and have required very large amounts of computer time.

No formula for $c_n$ is known, and none is expected. The counts are not generated by any finite recurrence anyone has found, and the absence is itself informative: the self-avoidance constraint looks backwards over the whole of the walk’s history, and no bounded amount of information about the recent past suffices to say which steps are allowed next.

A growth rate that exists but cannot be named #

The counts do grow at a definite rate, and the reason is a single inequality. A self-avoiding walk of $m + n$ steps splits into its first $m$ steps and its last $n$, each of which is self-avoiding; so

$$c_{m+n} \le c_m\,c_n,$$

with inequality because not every pair joins into a self-avoiding walk. Taking logarithms, $\log c_n$ is subadditive, and a lemma of Fekete then says that $\log c_n / n$ converges. Hammersley and Morton drew the conclusion in 1954: $c_n^{1/n}$ tends to a limit, the connective constant $\mu$. The same argument, word for word, gives a growth rate for the ball in a group: the number of elements within $m + n$ steps of the identity is at most the product of the numbers within $m$ and within $n$, so its $n$-th root converges. Subadditivity proves a rate exists in both settings and says nothing about its value in either.

The figure plots two estimates of it against $n$. The $n$-th roots $c_n^{1/n}$ approach from above, slowly, because of the lower-order factors hidden in $c_n$; the ratios $c_n/c_{n-1}$ approach faster and oscillate slightly, because odd and even lengths differ. Both close on about 2.638. The best estimate, from enumerations far beyond these, is $\mu = 2.638158530\ldots$, with further digits known — but no closed form is known, and it is not known whether $\mu$ is algebraic.

The constant sits where elementary bounds put it: at least 2, since walks that only ever step up or right are self-avoiding and there are $2^n$ of them, and at most 3, since every step after the first has at most three options. Cleverer families of walks that can be counted exactly push the lower bound up past 2.6, and cleverer ways of excluding collisions push the upper bound down below 2.7; everything in between is measurement.

One lattice where the answer is exact #

On the honeycomb lattice, where every site has three neighbours, the counts begin 3, 6, 12, 24, 48 — doubling, since each step has two forward choices and no collision is possible until a hexagon closes at six steps — and then 90 rather than 96. The ratios settle near 1.848.

That number is $\sqrt{2 + \sqrt 2}$, and it is known exactly. The physicist Bernard Nienhuis predicted it in 1982, from a mapping to a model of statistical physics whose exact solution was known, and Hugo Duminil-Copin and Stanislav Smirnov proved it in 2010 with an argument of remarkable shortness: a weighted sum over self-avoiding walks, with each walk weighted by how much it winds, is conserved around every hexagon when the weight per step is exactly $1/\sqrt{2 + \sqrt2}$, and that conservation forces the growth rate. The honeycomb is the only one of the regular lattices in two dimensions where $\mu$ is known. The square grid, where the walks were first studied, is not one of them.

$\sqrt{2 + \sqrt 2}$ is $2\cos(\pi/8)$, the length of a diagonal of a regular octagon with unit sides spanning three vertices, and its appearance is a sign that the answer is controlled by angles — by how self-avoiding walks wind — rather than by counting in any obvious sense.

How far a self-avoiding walk gets #

An ordinary walk of $n$ steps ends at a typical distance $\sqrt n$ from its start: its mean squared end-to-end distance is exactly $n$, because the steps are independent and their squared lengths add. A self-avoiding walk cannot fold back on itself, so it should reach further, and it does. Averaging the squared end-to-end distance over every self-avoiding walk of each length — all 881,500 of them at thirteen steps — gives a curve that rises more steeply than $n$ on logarithmic axes, with a slope of about 1.43 over the last few lengths and still rising.

The predicted exponent is $\tfrac32$: a self-avoiding walk of $n$ steps spans about $n^{3/4}$, against the ordinary walk’s $n^{1/2}$. Flory argued for $\tfrac34$ in 1949 by balancing the walk’s tendency to spread against its entropy, with a calculation that gives $3/(d + 2)$ in $d$ dimensions — exactly right in two dimensions, very nearly right in three (where the true exponent is about 0.588 against Flory’s 0.6), and right again in four, for reasons that turned out to be accidents of cancelling errors. Nienhuis’s 1982 derivation of $\tfrac34$ for the plane, from the same exactly solved model that gave $\sqrt{2+\sqrt2}$, is the one physicists trust.

Long self-avoiding walks cannot be enumerated, and they cannot be sampled by running a random walk and discarding it when it collides — at 400 steps, essentially every attempt would be discarded. The pivot algorithm, due to Moti Lal in 1969 and analysed by Madras and Sokal in 1988, samples them another way: start from any self-avoiding walk, pick a point on it, apply a rotation or reflection of the grid to everything after that point, and keep the result if it is still self-avoiding. The moves are drastic, most are rejected, and the ones accepted change the walk’s shape globally; repeated thousands of times, they produce a walk drawn from the uniform distribution on self-avoiding walks of that length. It is a Markov chain whose states are whole walks — a walk that samples a distribution describes the general method — and it works because the uniform distribution on self-avoiding walks is left unchanged by every accepted move, even though no one can count the walks it is sampling from.

The walk in the figure, 400 steps long, spans 127 sites across; an ordinary walk of the same length spans 21. The self-avoiding walk is not merely longer — it is a different shape, extended and snaking, where the ordinary walk is a tangle that has crossed itself hundreds of times.

A walk that grows itself into a corner #

The counts also explain why a self-avoiding walk cannot be generated the obvious way. Grow a walk one step at a time, choosing uniformly among the neighbours not yet visited, and it will eventually trap itself: spiral into a pocket whose every exit is already occupied, with no legal step left. The shortest walk on the square grid that can do this has seven steps, and a walk grown at random traps itself, on average, after about seventy — so the method cannot produce long walks at all.

Worse, the walks it does produce are not the uniform ones. A walk grown this way chooses among three options at one step and one at another, and it is more likely to be a walk that had few choices along the way than one that had many. Every self-avoiding walk of a given length should be equally likely, and growing them step by step makes some of them far more likely than others. Correcting for the bias — weighting each grown walk by the product of the numbers of choices it had, as Rosenbluth and Rosenbluth did in 1955 — works for short walks and degrades rapidly for long ones.

This is the other face of the fact that no recurrence counts the walks. The walk’s future depends on its entire past, not on its last step or last few steps; it is not a chain that forgets where it came from, and every tool built for chains that forget — including the ordinary walk’s elegant theory of return and escape in a walk that comes home — fails at the first step.

Why a chemist cared #

Paul Flory introduced the walks in the 1940s to answer a practical question: how large is a polymer? A long molecule of $n$ identical links, in solution, wanders like a random walk, except that two links cannot occupy the same place — the excluded volume. An ordinary random walk predicts a size proportional to $\sqrt n$; Flory’s argument that excluded volume inflates it to $n^{3/5}$ in three dimensions was one of the results for which he received the Nobel Prize in Chemistry in 1974.

The prediction can be tested, because the size of a dissolved polymer can be measured by how it scatters light. Measurements on long polymers in good solvents give exponents close to 0.59, a little below Flory’s 0.6 and in close agreement with the value 0.5876 that the best theory and simulation now give. The model is crude — real links have angles and lengths, and real solvents attract or repel — but the exponent does not care about any of that. It depends only on the dimension and on the fact that the chain cannot cross itself, which is the property physicists call universality, and which is why a walk on a square grid can say something true about molecules. The mathematics has not caught up with the chemistry: every experiment and every computation agrees that a self-avoiding walk in three dimensions spans about $n^{0.588}$, and no proof exists that it spans more than $\sqrt n$.

What the enumeration and the sample cannot show #

The two walks have opposite textures. The ground a walk covers found an ordinary walk revisiting most sites many times; a self-avoiding walk revisits none, by definition, so its range is exactly its length plus one. What the figures compare is therefore not how much ground the two walks cover — the self-avoiding walk always covers the most possible — but how that ground is arranged.

Thirteen steps is short. The end-to-end exponent the figure measures, 1.43, is not yet $\tfrac32$ and is still climbing; the approach to the limit is slow, and extrapolating from short walks is exactly how the physics literature estimated the exponent before the prediction existed. The figure’s evidence is consistent with $\tfrac32$ and would be consistent with nearby values too.

One pivot sample is one walk. Its span of 127 is a single draw from a distribution with a long tail, and a typical 400-step walk spans about $400^{3/4} \approx 89$; the figure shows the character of a self-avoiding walk, not its average.

The connective constants are quoted. The dashed lines are at the best known estimate for the square grid and at the proved value for the honeycomb, and the dots approach them; the figures do not compute the constants beyond the ratios shown.

Still open: that the exponent is three quarters #

It is not known that the end-to-end distance of a planar self-avoiding walk grows like $n^{3/4}$. It is not even known that it grows at least as fast as an ordinary walk’s $\sqrt n$ — the most basic consequence of the walk being unable to fold back on itself — nor, until Duminil-Copin and Hammond proved it in 2013, was it known that the walk falls short of a straight line, reaching $o(n)$ rather than a constant times $n$.

The conjectured picture is complete and precise: in the plane, a long self-avoiding walk, scaled down, should converge to a random curve described by the Schramm–Loewner evolution with parameter $\tfrac83$, whose properties give the exponent $\tfrac34$ and much more. Lawler, Schramm and Werner showed in 2004 that if the scaling limit exists and has a natural symmetry, it must be that curve. Proving that the limit exists is the open problem. The limiting curve would have a dimension that is not a whole number — $\tfrac43$, the reciprocal of the exponent $\tfrac34$ — which is another way of saying the same thing: a walk of $n$ steps that spans a distance $r$ has $n \approx r^{4/3}$, so its path fills space more thickly than a line and far more thinly than the ordinary walk, whose path in the plane has dimension 2. In five or more dimensions the question is settled — Hara and Slade proved in 1992 that the exponent there is $\tfrac12$, the same as an ordinary walk, because in high dimensions a walk rarely comes near its own past — and in three and four dimensions it is open as well.

The simplest rule and the hardest questions #

A walk that may not step where it has been is defined in one sentence. Its number of $n$-step paths grows at a rate that exists by a two-line argument and has been computed to many digits without being identified; on one lattice, the honeycomb, that rate is $\sqrt{2 + \sqrt 2}$, and the proof is an identity about winding. Its typical size grows like $n^{3/4}$ in the plane, a prediction seventy years old that every computation supports and no proof reaches.

The ordinary walk and the self-avoiding walk are the two extremes of one family. Between them are walks that are only discouraged from revisiting — each revisit costs a factor less than one — and it is believed, and in high dimensions proved, that any amount of discouragement puts a walk in the self-avoiding class: once the chain pays anything at all for crossing itself, it behaves in the long run as if it could not.

A constraint that looks back over the whole history of a process destroys the tools that work for processes without memory — independence of steps, recurrences, generating functions with finitely many terms — and what survives is subadditivity, which proves that a rate exists, and exact solutions of related models, which suggest what it is. The ordinary walk of the walk that becomes a curve has Brownian motion as its limit; the self-avoiding walk’s limit is conjectured, named and not yet reached.