Self-trapping random walks on square lattice in 2-D (cubic in 3-D)
Hugo Pfoertner
self-avoiding random walk on a square lattice, with some feedback from
Bill Taylor. In the meantime I found some references:
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
and Diffusion"
http://www-math.mit.edu/~bazant/teach/18.325/index.html
Among the problems was:
4.Problem Set 2b: Non-reversing random walk, self-trapping random walk,
self-avoiding random walk.
http://www-math.mit.edu/~bazant/teach/18.325/problems/ps2-325.ps
Solutions by D. Harmon:
http://www-math.mit.edu/~bazant/teach/18.325/problems/PS2b-Harmon.ps
Solutions by E. Silva:
http://www-math.mit.edu/~bazant/teach/18.325/problems/PS2b-Silva.ps
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"
http://www.tbi.univie.ac.at/papers/Abstracts/alex_dipl.pdf
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
E.C.Silva's results:
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
own results:
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)
Detailed Results:
2D:
Average number of attempts to select already visited position: 45.0295
+-0.0010
Manhattan distance of outmost visited position: 20.38284+-0.00032
Histograms of path lengths:
http://www.enginemonitoring.org/random/stwalk2d/stwalk.pdf
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:
http://www.enginemonitoring.org/random/stwalk2d/fails.pdf
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:
http://www.enginemonitoring.org/random/stwalk2d/hit4e9.txt (197kB)
(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:
http://www.enginemonitoring.org/random/stwalk2d/movdis.pdf
Probability to stop at given point with Euclidean distance from start:
http://www.enginemonitoring.org/random/stwalk2d/ediscnt.pdf
Outmost visited point during walk (Manhattan distance):
http://www.enginemonitoring.org/random/stwalk2d/maxdis.pdf
Count tables (one one given for 4*10^9 walks)
(Col1: number, moves: 2:trap 3:failed, 4:max vis Manh.dist)
http://www.enginemonitoring.org/random/stwalk2d/cnt4e9.txt
Fortran program for 2-D:
http://www.enginemonitoring.org/random/stwalk2d/stwalk.for
3-D:
Some additional information on the 3D-results will be posted here later
(if anybody is interested). For those being curious, here are the
corresponding links:
Move counts (see 3rd sheet for the odd/even structure also present in
3d):
http://www.enginemonitoring.org/random/stwalk3d/mov1e8.pdf
Failed step attempts:
http://www.enginemonitoring.org/random/stwalk3d/fai1e8.pdf
Manhattan Distances: Termination, Max Visited:
http://www.enginemonitoring.org/random/stwalk3d/dis1e8.pdf
Zipped result tables:
http://www.enginemonitoring.org/random/stwalk3d/stw1e8.zip
Fortran program:
http://www.enginemonitoring.org/random/stwalk3d/walk3d2.for
Hugo Pfoertner
Contact Info: htp://www.pfoertner.org/