Self-Avoiding Random Walks
The picture below is a snap-shot from the screen showing one example of a self-avoiding random walk.

SAW

Performing the simple sampling simulation it becomes immediately evident that we have a problem with the simple sampling technique for the self-avoiding random walk model. As we increase the number of steps the walker should travel, it becomes harder and harder to find a walk. In almost all cases the walk terminates earlier because there is a violation of the self-avoiding condition! This shows that the simple sampling, even though being the simplest and perhaps even most powerful method has clear limitations.

The way out of the disastrous dependence of the probability to generate a walk of length N, once N is large, is to start with a walk that fulfills the requirement of self-avoidance. We can then generate a new walk from the already present one. We follow up on this idea when we discuss the importance sampling techniques.

Lets assume that we have solved the problem of generating large self-avoiding random walks. What we will find is that this type of a random walk does not fill space because of its spatial correlation. The end-to-end distance scales as

Re(N) ~ Nn ~ N0.59 

Exercises

  • Calculate the average end-to-end distance of a random walk as a function of the number of steps N and the number of observations n. The end-to-end distance was defined as the Euclidean distance between the starting point and the point which the walk reached after N steps. How does the error of the distance scale with N and n? For this, compute the error at several values for N and n.
  • Redo the above exercise with the self-avoiding random walk.
  • Empirically find the relation between the length of a self-avoidingwalk N and the probability with which one generates such a walk using the simple sampling.
  • With as much effort as you are willing to invest, compute the exponent n for the scaling of the end-to-end distance with the length of the walk for the self-avoiding walk problem.

Literature

  • Binder and D.W. Heermann, Monte Carlo Simulation in Statistical Physics. An Introduction, Second Edition, Springer Verlag 1992
  • Baumgärtner, in Applications of the Monte Carlo Method in Statistical Physics, ed. K. Binder,  Topics Curr. Phys. Vol 36, 2nd Edition (1987)
previous page next page