39 views

Skip to first unread message

Mar 4, 2002, 9:20:25 PM3/4/02

to

Some weeks ago I've posted some results on the 2-dimensional

self-avoiding random walk on a square lattice, with some feedback from

Bill Taylor. In the meantime I found some references:

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/

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu