A result on the expected number of moves to termination was published in
S.Hemmer and P.Hemmer: An average self-avoiding walk on the square
lattice lasts 71 steps. J.Chem.Phys. 81, 584-585, 1984
Martin Z. Bazant held a graduate course for Spring 2001 at the
Massachusetts Institute for Technology "18.325: Topics in Random Walks
Among the problems was:
4.Problem Set 2b: Non-reversing random walk, self-trapping random walk,
self-avoiding random walk.
Solutions by D. Harmon:
Solutions by E. Silva:
In 1994 Alexander Renner wrote a "Diplomarbeit" (German equiv. master's
thesis) at the Institute of Theoretical Chemistry of the University of
Vienna "Self Avoiding Walks and Lattice Polymers", where he gave some
results on "Grown SAWs and Self Trapping"
Using 60000 samples he found an expected average length for the 2-D path
on the square lattice of 71.7 +- 0.2 moves.
With 10000 samples his 3-D result for the "grown SAW" on the simple
cubic lattice was 3997 +- 38 moves.
He also provides distributions of walk lengths as histograms.
More accurate results are provided by Dion Harmon:
2D: n_trap = 70.8 using 10^6 walks
3D: n_trap = 3960 using 10^5 walks
2D: n_trap = 71.8 using 10^5 walks
3D: n_trap = 3676 using 1.5*10^4 walks
After some optimization of my Fortran programs I was able to improve my
2D: n_trap = 70.7598 +- 0.0010 using 10^10 walks (40 hrs CPU on PC
Athlon 800 MHz)
3D: n_trap = 3953.3 using 10^8 walks (80 hrs CPU)
Average number of attempts to select already visited position: 45.0295
Manhattan distance of outmost visited position: 20.38284+-0.00032
Histograms of path lengths:
For low path lengths the distribution is significantly different for odd
and even numbers: More walks with odd step number get trapped than those
with even step number. This structure persists up to N around 70. Dion
Harmon misinterpreted this as "high frequency jitter". An attempt to
express the distribution shape by a formula would have to take into
account these two branches in the low lenght part of the distribution.
Hemmer/Hemmer and Renner did not recognize this structure.
A suffient period length and quality of the pseudo random number
generator is necessary to avoid repeated paths and distorsions of the
path geometry. The occurrence of an extremely unlikely walk of length
957 in only 10^6 walks observed by D. Harmon might be an indication of
some problem with the applied PRNG. In all my present simulation runs
the latest (2002) issue of the Mersenne twister generator was used.
Failed step attempts:
In 8*10^9 trials there were 14598970 walks (0.18%) that moved into the
final trap situation making only successful steps (perfect avoidance).
Spatial distribution of trap locations:
Coordinate list of all lattice points with > 0 hits, after summing the 8
symmetric index permutations:
(cols 1,2: index of lattice point, col 3: count of paths trapped here,
col 4: average moves of all paths trapped here.
Plotted versus Euclidean distance of termination point:
Probability to stop at given point with Euclidean distance from start:
Outmost visited point during walk (Manhattan distance):
Count tables (one one given for 4*10^9 walks)
(Col1: number, moves: 2:trap 3:failed, 4:max vis Manh.dist)
Fortran program for 2-D:
Some additional information on the 3D-results will be posted here later
(if anybody is interested). For those being curious, here are the
Move counts (see 3rd sheet for the odd/even structure also present in
Failed step attempts:
Manhattan Distances: Termination, Max Visited:
Zipped result tables:
Contact Info: htp://www.pfoertner.org/