Self-Avoiding Walk

DEFINITION

walk x0..xN on Z², self-avoiding, x0..xN initially a straight line
pivot: choose interior site k, choose g in the 7 nontrivial
  symmetries of the square lattice (rotations + reflections)
x′ᵢ = g·(xᵢ − xₖ) + xₖ   for i on the shorter arm at k
accept iff {x′ᵢ} shares no site with the fixed arm
  (an isometry cannot make an arm cross itself that could not before)
⟨Rₑ²⟩ ~ N^(2ν),  ν = 3/4 exactly in two dimensions (Nienhuis, 1982)

NOTES

A self-avoiding walk of N steps on the square lattice is drawn here by folding, not by growing. It starts as a straight line and is reshaped by a sequence of pivot moves: pick a site already on the walk, pick one of the seven nontrivial symmetries of the square lattice -- a rotation or a reflection -- and apply it to whichever arm either side of that site is the shorter one to check. A lattice symmetry is an isometry, so an arm that did not cross itself before cannot cross itself after; the only real question is whether the moved arm has landed on a site the rest of the walk already occupies, which an occupancy grid answers in time proportional to the walk length rather than its square. Land clear and the move stands; land on an occupied site and it is thrown out, the walk exactly as it was a moment before. Moti Lal proposed a move of this shape in 1969, generating polymer configurations by computer rather than growing them one bond at a time. What was not understood until Neal Madras and Alan Sokal analysed the move properly in 1988 is how well it works: the number of attempted pivots needed before a walk has no statistical memory of its earlier shape grows only in proportion to the walk length, not to its square -- the highly efficient of their paper title, and why this algorithm rather than step by step growth is now the standard way to sample self-avoiding walks. Growing a walk one uncertain step at a time can paint it into a corner with no legal next step; a pivot always starts from a walk that is already valid and only ever proposes another one. Every accepted pivot below swings its arm into the new position and leaves a brief fading trace of where it was; every rejected one flashes in the same place and is discarded on the spot. What a long run of pivots settles into is not a fixed shape but a fixed statistic: the mean squared distance between the two ends of an N-step walk grows as N to the power two nu, and nu is exactly three quarters in two dimensions -- the value an excluded-volume argument published by Paul Flory in 1949 predicts once generalised to two dimensions, for reasons that happen there to be exact, and the value Bernard Nienhuis derived exactly in 1982 from the exact solution of the O(n) model on this lattice. The plate own pivot chain was measured directly against that claim: five walk lengths, hundreds of independently equilibrated samples at each, recover nu = 0.747, half a percent from 0.75.

PROVENANCE

Origin — the move

M. Lal, "Monte Carlo computer simulation of chain molecules. I", Molecular Physics 17(1), 1969, 57-64 (doi:10.1080/00268976900100781). Lal proposed generating polymer chain configurations by applying global rearrangements to a trial chain and testing the result for self-intersection, rather than growing a chain step by step and risking a dead end. That global-rearrangement idea is the pivot move this plate runs, more than fifty years later, unchanged in shape

Origin — the algorithm and its efficiency

N. Madras & A. D. Sokal, "The pivot algorithm: A highly efficient Monte Carlo method for the self-avoiding walk", Journal of Statistical Physics 50(1-2), 1988, 109-186 (doi:10.1007/BF01022990, the src link above). Lal move existed for two decades before anyone showed it was efficient rather than merely correct. Madras and Sokal analysis found that the number of ATTEMPTED pivots needed before a walk has decorrelated from its earlier shape grows only in proportion to the walk length rather than its square, the way a local, one-bond-at-a-time Monte Carlo move needs. That is the highly efficient of the paper title, and their paper also describes implementing the self-avoidance test through a hash table so each attempt costs time proportional to the walk length rather than its square as well — the occupancy grid this plate and its VEX port use is that same idea, direct-addressed rather than hashed since the coordinate range is known once the walk length is fixed

The exponent

Nu = 3/4 in two dimensions traces to two results of very different character. P. J. Flory, "The Configuration of Real Polymer Chains", The Journal of Chemical Physics 17(3), 1949, 303-310 (doi:10.1063/1.1747243) is a mean-field, three-dimensional argument about real polymer chains balancing chain entropy against excluded-volume repulsion; generalised to an arbitrary spatial dimension d it gives nu = 3/(d+2), which happens to equal exactly 3/4 at d = 2 for reasons Flory own 1949 paper, being about three dimensions, does not itself address. B. Nienhuis, "Exact Critical Point and Critical Exponents of O(n) Models in Two Dimensions", Physical Review Letters 49(15), 1982, 1062-1065 (doi:10.1103/PhysRevLett.49.1062) is the derivation that actually settles it: the self-avoiding walk is the n to 0 limit of the O(n) spin model, whose two-dimensional lattice version Nienhuis solved exactly by Coulomb-gas methods, reading nu = 3/4 off the exact solution rather than off an approximation that happens to land there

Not levyflight (PL. 134), and not a growth process

Levyflight is independent draws from a heavy-tailed step distribution -- step i places no constraint on step i+1, and the whole exhibit is what a single steps own tail does to a walk. This plate is the opposite structure: an ordinary unconstrained random walk already has nu = 1/2 in any dimension, and the ONLY thing added here is a single global constraint, no two lattice sites may coincide -- and that constraint alone is what moves nu from 1/2 to 3/4. It is also not the more obvious way to generate a self-avoiding walk, one step at a time with a self-avoidance check at each step: that process (kinetic growth) samples a BIASED distribution over walks, over-weighting the ones that had an easy time avoiding themselves early on, a well known trap in this literature. The pivot algorithm avoids it entirely by never growing anything -- every state in the chain is already a complete, valid walk of the target length

Standing

Public domain -- a Monte Carlo move, a convergence analysis, and two theoretical-physics results, dated 1949 to 1988. No patent is possible on any of it

Checked, not just plotted

Independent restarts (fresh straight walk, run to 2N accepted pivots, the plate own equilibration threshold, then record end-to-end distance squared), 600 samples per length, at N = 40, 80, 160, 320 and 500: a log-log least-squares fit gives 2*nu = 1.4939, nu = 0.7469, four tenths of one percent from the exact 0.75. Separately, whether "2N accepted pivots between samples" is actually enough decorrelation to call two samples independent was checked directly rather than assumed: at N = 160, one continuous chain sampled every 2N accepted pivots gives a mean end-to-end-squared of 1573.9 against 1657.6 from 600 fully independent restarts, 1.35 combined standard errors apart, and the chain-spaced series has a lag-1 autocorrelation of 0.043. The same threshold that measures the exponent is the one the live plate below fires its equilibration event at

Implementation

The self-avoidance test only ever checks the moved arm against the fixed one, never the moved arm against itself. That is not an approximation: a lattice symmetry is an isometry, so it cannot introduce a self-crossing into an arm that had none, and every arm here is a piece of a walk that was self-avoiding to begin with. What remains is exactly the O(N) test Madras and Sokal own paper describes -- mark every fixed-arm site once under a fresh generation stamp, then look up each proposed site from the moved arm against those marks, both passes bounded by the walk length rather than its square

Constants

length (N) is the plate own independent variable in the relation it exists to show and is locked for that reason, not primarily for cost -- see the LOCKED note above for the measured numbers. tries paces how many pivot attempts run before each paint (2 to 20 a frame); hold paces how many frames the equilibrated walk is held on screen before the next epoch begins growing or restarting. Both are jitterable pacing dials: swept together across six seeds at three lengths (the two declared ends and the default), 108 trials of 600 frames each, every one eventually reaches its equilibration event, 105 of 108 within ten seconds and the slowest declared corner (length at its ceiling, tries at its floor) within about twelve -- reported rather than tuned away, since narrowing the tries floor to hide one slow corner would cost the reader the ability to watch a small number of attempts per frame at all

Source

doi:10.1007/BF01022990

HOUDINI · VEX

The same published mathematics as a Detail Wrangle body. Paste it into a Wrangle with Run Over set to Detail; every constant is the published value plus a tweak channel, so Create Spare Parameters gives a slider that starts where the paper does.

// FORMA — PL. 142 · SELF-AVOIDING WALK — Moti Lal, 1969 · efficiency proof: Neal Madras & Alan D. Sokal, 1988
//   walk x0..xN on Z², self-avoiding, x0..xN initially a straight line
//   pivot: choose interior site k, choose g in the 7 nontrivial
//     symmetries of the square lattice (rotations + reflections)
//   x′ᵢ = g·(xᵢ − xₖ) + xₖ   for i on the shorter arm at k
//   accept iff {x′ᵢ} shares no site with the fixed arm
//     (an isometry cannot make an arm cross itself that could not before)
//   ⟨Rₑ²⟩ ~ N^(2ν),  ν = 3/4 exactly in two dimensions (Nienhuis, 1982)
// Paste into a Detail Wrangle (Run Over: Detail), no inputs needed.
// Written from the published mathematics, not adapted from any code.
// Constants arrive at their published values. Press the node's Create
// Spare Parameters button and every tweak becomes a slider — starting
// at 0, the published figure, and moving in the constant's own units.
// https://forma-gen.com/#plate=selfavoiding

float p_length = 160 + chf('length_tweak');     // walk length N · live 40 .. 260

// The plate's own colour: FORMA's LATTICES accent as a cosine ramp,
// brightest near t = 0 and t = 1, near-black around t = 0.5.
vector forma_ramp(float t){
  return set(
    0.46 + 0.5 * cos(6.28318530718 * (t + 0)),
    0.4185 + 0.4549 * cos(6.28318530718 * (t + 0.05)),
    0.1389 + 0.151 * cos(6.28318530718 * (t + 0.1)));
}

// The pivot algorithm (Lal 1969, proved efficient by Madras and Sokal 1988)
// run to one fixed, generous ATTEMPT count rather than to the page's own
// accepted-pivot threshold -- a cook has no frame budget to spend attempts
// against, so it is simply given far more attempts than the busiest
// measured case ever needed (drafts/wave19: 1352-1414 attempts to reach
// 2*N accepted pivots at N = 260, the page's own equilibration rule; twenty
// times N here is comfortably past that at every declared length). Same
// move as the page: pick an interior site, pick one of the seven
// nontrivial symmetries of the square lattice, apply it to whichever arm
// either side of that site is the shorter one to check, and accept the
// result only if the moved arm has landed nowhere the fixed arm already
// occupies -- a lattice symmetry is an isometry, so the moved arm cannot
// have crossed itself, which is why only the fixed arm needs marking.
// One polyline: the walk at whatever attempt count the loop reaches.
// The live pivot flash and the two endpoint marks are page-only cursors --
// a moment inside an animation a cook has no clock for -- and are not
// ported, DLA's own precedent cited by name in its own port comment for
// its HILITE growth cursor. Canvas y runs down; this cook negates y to
// match Houdini own up, the corpus convention.
// Deterministic: every draw is random(counted seed) on the plate's own
// first-era seed.
// waived: tries, hold — both are animation pacing on the page (attempts
// run per frame; frames the finished walk is held before the next epoch
// begins); a cook has no frame loop to pace and emits one finished walk

int N = int(rint(p_length));
int ATTEMPTS = int(rint(20.0 * p_length));   // headroom measured against the page's own 2N-accepted rule
int seed = 1969;                             // the plate's own seed, counted upward

int x[], y[];
resize(x, N + 1);  resize(y, N + 1);
for (int i = 0; i <= N; i++){ x[i] = i;  y[i] = 0; }

// the square lattice symmetry group minus the identity: four rotations
// short one, four reflections, as (a,b,c,d) with q = (a*dx+b*dy, c*dx+d*dy)
int SYM[] = {
     0,-1, 1, 0,   // rotate 90
    -1, 0, 0,-1,   // rotate 180
     0, 1,-1, 0,   // rotate 270
     1, 0, 0,-1,   // reflect across the x-axis
    -1, 0, 0, 1,   // reflect across the y-axis
     0, 1, 1, 0,   // reflect across y = x
     0,-1,-1, 0    // reflect across y = -x
};

// occupancy grid, sized to this walk's own worst-case reach; VEX zero-fills
// a freshly resized array, the same assumption DLA own port relies on for
// its lattice
int GN = 2 * N + 5, OFF = N + 2;
int mark[];  resize(mark, GN * GN);
int stamp = 0;

int nx[], ny[];  resize(nx, N + 1);  resize(ny, N + 1);

for (int a = 0; a < ATTEMPTS; a++){
    // pivot at an interior site only -- the two ends move the whole walk
    // rigidly and can never be refused, which tests nothing
    int k = 1 + int(random(seed) * float(N - 1));  seed++;

    // move the SHORTER arm: Madras and Sokal own optimisation, inverting
    // the walk (relabelling 0..N as N..0) leaves the same distribution, so
    // the algorithm may always choose whichever side is cheaper to check
    int moveLeft = 1;  if (k > N - k) moveLeft = 0;
    int fixedLo = k, fixedHi = N, moveLo = 0, moveHi = k;
    if (moveLeft == 0){ fixedLo = 0;  fixedHi = k;  moveLo = k;  moveHi = N; }

    int gi = int(random(seed) * 7.0);  seed++;
    int g0 = SYM[gi * 4], g1 = SYM[gi * 4 + 1], g2 = SYM[gi * 4 + 2], g3 = SYM[gi * 4 + 3];
    int px = x[k], py = y[k];

    // mark every fixed-arm site under a fresh stamp, so testing the moved
    // arm is a lookup rather than a search -- the O(N) implementation
    // Madras and Sokal describe
    stamp++;
    for (int i = fixedLo; i <= fixedHi; i++) mark[(y[i] + OFF) * GN + (x[i] + OFF)] = stamp;

    // only the moved arm needs testing against the fixed one: a lattice
    // symmetry is an isometry, so an arm that was self-avoiding before
    // stays self-avoiding after g is applied to it, whatever g is
    int ok = 1;
    for (int i = moveLo; i <= moveHi; i++){
        int j = i - moveLo;
        int dx = x[i] - px, dy = y[i] - py;
        int qx = px + g0 * dx + g1 * dy;
        int qy = py + g2 * dx + g3 * dy;
        nx[j] = qx;  ny[j] = qy;
        if (i != k && mark[(qy + OFF) * GN + (qx + OFF)] == stamp) ok = 0;
    }
    if (ok == 1){
        for (int i = moveLo; i <= moveHi; i++){
            int j = i - moveLo;
            x[i] = nx[j];  y[i] = ny[j];
        }
    }
}

int prim = addprim(0, "polyline");
vector col = forma_ramp(0.94);
for (int i = 0; i <= N; i++){
    int pt = addpoint(0, set(float(x[i]), -float(y[i]), 0.0));
    setpointattrib(0, "Cd", pt, col);
    setpointattrib(0, "Alpha", pt, 0.92);
    addvertex(0, prim, pt);
}