A random walk that never revisits a site models a polymer chain. It spreads faster than an ordinary walk, by an exponent that has never been proved.
The walkers that built the clusters of the previous essay were free to cross their own paths. A self-avoiding walk (SAW) on a grid never visits the same cell twice. It models a polymer chain, each step a monomer, since a real chain cannot pass through itself. Below, the walks are counted, sampled fairly and measured, and the obvious way to make one, growing it a step at a time, turns out to give the wrong answer.
Figure 1. Eighty walks of each kind, all exactly the chosen number of steps and drawn at the same scale (move the slider, then Redraw). The ordinary walks stay compact and revisit old ground. The self-avoiding walks, sampled uniformly by the pivot algorithm of Figure 3, cannot fold back and spread further: at 100 steps their ends land about 27 lattice units from the start on average, against about 8 for the ordinary walks.
There are $4^n$ ordinary walks of $n$ steps. Forbidding revisits removes most of them, and no formula gives the number $c_n$ left. The page counts them by listing every one, up to 20 steps.
Figure 2. Every self-avoiding walk up to 20 steps, counted by depth-first search in the page. Left: the counts (blue) fall ever further below the ordinary walks and below walks that only forbid stepping straight back (gray). Right: the growth per step. The raw ratio $c_n/c_{n-1}$ zigzags between odd and even $n$ (gray); the two-step ratio $\sqrt{c_n/c_{n-2}}$ (blue) does not, and a straight line through $n = 10$ to 20, plotted against $1/n$, reaches the infinite-length end (violet ring) close to the best estimate (amber).
If $c_n \approx A\,\mu^n n^{\gamma-1}$, the ratio approaches the growth rate $\mu$ along a line in $1/n$ with slope $\mu(\gamma-1)$. Twenty steps extrapolate to 2.637, against $\mu = 2.63815853$ from much longer series (Jacobsen, Scullard and Guttmann 2016), and the slope gives $\gamma - 1 \approx 0.348$ against Nienhuis's predicted 11/32 = 0.344. Each step multiplies the work by about 2.64; Caracciolo and coauthors counted to 59 steps in 2005. On the honeycomb lattice $\mu$ is exactly $\sqrt{2+\sqrt{2}}$, predicted by Nienhuis in 1982 and proved by Duminil-Copin and Smirnov in 2012.
Longer walks have to be sampled, with every walk equally likely. The pivot algorithm (Lal 1969; Madras and Sokal 1988) picks a site, rotates or reflects everything beyond it by one of the seven other symmetries of the grid, and keeps the result only if it does not overlap itself. Repeated, this makes every $N$-step SAW equally likely.
Figure 3. Left: one 80-step walk (green dot: start) under pivot attempts. The pivot site is marked (cyan) and the proposed tail drawn dashed, violet if it fits and red, with the first collision circled, if it does not. Right: the fraction of attempts accepted, measured in the page for walks of 16 to 2,048 steps (seed 1), with a fitted power law (violet) and Madras and Sokal's empirical exponent (amber). The cyan ring is the walk on the left.
Long walks reject most attempts, 54% accepted at 16 steps and 23% at 2,048, a slope of −0.18 against the 0.19 Madras and Sokal found. But each accepted move swings a large part of the walk, so a few of them are enough for it to forget its shape. All the SAWs in Figures 1, 4 and 5 are drawn this way.
A random walk's end distance grows as $N^{1/2}$. For the SAW in two dimensions Nienhuis predicted $\nu = 3/4$ in 1982 from a Coulomb gas argument that is not a proof, and it is still unproved. Lawler, Schramm and Werner showed that if the walk has a conformally invariant scaling limit, it is SLE with $\kappa = 8/3$, which again gives 3/4. In 3D the best estimate is $\nu \approx 0.5876$ (Clisby and Dünweg 2016). Flory's 1949 argument, $\nu = 3/(d+2)$, gives 3/5 in 3D and exactly 3/4 in 2D, though it is far from a derivation.
Figure 4. Mean end-to-end distance against chain length for pivot-sampled SAWs (blue) and ordinary random walks (gray), with best-fit power laws dashed and slopes 3/4 and 1/2 dotted. Fitted over 10 to 320 steps the SAW slope comes out near 0.74 (0.750 on the first run), a little under 3/4 because the shortest walks have not settled into the asymptotic scaling; Run again to see how far it moves between samples (0.72 to 0.76 in 40 runs at 200 walks per length).
The exponent sets the size. Divide each walk's end distance by the root-mean-square for its length, and walks of every length should also share one shape.
Figure 5. End-to-end distance in units of its root-mean-square, from 16,000 pivot-sampled walks at each of 50, 100, 200, 400 and 800 steps (blue, darker for longer), 400-step random walks (gray) and their Gaussian limit $2x e^{-x^2}$ (dashed). The slider counts the walks that end inside the shaded band.
They do, from 50 steps on, and the shape is narrower than the Gaussian at both ends. About 11% of SAWs end within half the rms distance of the start, against 23% of random walks: to come back, a walk has to thread between its own earlier steps. Des Cloizeaux (1974) predicted that the chance per unit area of ending near the start vanishes as $x^{(\gamma-1)/\nu} = x^{11/24}$ in two dimensions, where for a random walk it stays finite. Beyond 1.5 times the rms distance lie about 5% of SAWs and 10% of random walks.
The obvious way to make a SAW is to grow it, stepping at random to an unvisited neighbor. On the square lattice every such walk eventually traps itself. It cannot happen before step 7, and only about 1 walk in 70 traps within 10 steps, but by step 50 the risk is about 2% per step. Hemmer and Hemmer (1984) grew 60,000 walks and found an average length of 70.7 steps, ending about 12 lattice units from the start.
Figure 6. One growing walk (green dot: start), its head circled red when it traps, and a histogram of the lengths at which walks trapped, starting from 500 walks (seed 3). The median of a 500-walk batch lands between about 54 and 62 (58 over 200,000 walks), below the mean of 71 because a long tail of survivors pulls the mean up, and a fifth to a quarter of the walks reach 100 steps.
The hidden problem is bias. A grown walk reaches a given SAW with probability $\prod_i 1/k_i$, where $k_i$ is the number of free neighbors at step $i$, so compact walks, with fewer choices, are over-represented. Rosenbluth and Rosenbluth (1955) weighted each walk by $W = \prod_i k_i$ to undo this: weighted averages are fair, and the mean weight, trapped walks counting zero, is the number of SAWs.
Figure 7. 20,000 walks grown to 200 steps (seed 7). Left: at the chosen length, the walks still growing binned by the logarithm of their Rosenbluth weight (blue, up) and each bin's share of the total weight (amber, down). Right: root-mean-square end distance of the grown walks divided by that of uniform SAWs from the pivot algorithm, counting every survivor equally (red) or by weight (violet).
Counted equally, grown walks come out too small: rms end distance 20.6 at 100 steps against 28.2 for uniform SAWs. Weighted, 27.4, and the mean weight at 20 steps gives $10^{8.949}$ walks against the exact $10^{8.953}$ of Figure 2. But at 100 steps the weights span 7.7 decades and the heaviest 1% carry 54% of the total, so 4,305 survivors count as about 95. By 200 steps that is 10, and the weighted estimate falls 20% short (37.7 against 47.3). The mismatch grows exponentially with length (Sokal 1994), which is why long SAWs are sampled with pivots.
The 3D exponent is the one Flory was after: it sets how the size of a flexible polymer in a good solvent grows with chain length. A self-avoiding walk steers by the trail it has left. The agents in the next essay also steer by trails, their own and each other's, but they turn toward the strongest marks, and the marks fade and spread.