Chapter 7: Mechanisms in Programs and Nature

Section 6: The Phenomenon of Continuity

Self-avoiding [random] walks

Any walk where the probabilities for a given step depend only on a fixed number of preceding steps gives the same kind of limiting Gaussian distribution. But imposing the constraint that a walk must always avoid anywhere it has been before (as for example in an idealized polymer molecule) leads to correlations over arbitrary times. If one adds individual steps at random then in 2D one typically gets stuck after perhaps a few tens of steps. But tricks are known for generating long self-avoiding walks by combining shorter walks or successively pivoting pieces starting with a simple line. The pictures below show some 1000-step examples. They look in many ways similar to ordinary random walks, but their limiting distribution is no longer strictly Gaussian, and their root mean square displacement after t steps varies like t^(3/4). (In d<=4 dimensions the exponent is close to the Flory mean field theory value 3/(2+d); for d>4 the results are the same as without self-avoidance.)

From Stephen Wolfram: A New Kind of Science [citation]