Up to now, each step in the random walk was completely independent of the steps before - these are the simple random walks. There is, however, another class of random walks, called self-avoiding walks, which emerge after adding a seemingly banal and trivial constraint: Such a SAW is not allowed to come back to any position it has visited before. In order to see where this may be relevant, consider the example of long polymers. Typically they are long molecules, made of long chains of simpler units, called monomers. In different phases they are coiled up, with potentially many turns and twists to form a three-dimensional form. Its shape is often important for the properties of the polymer. In order to describe this configuration, a random walk seems to be an obvious candidate, where each step corresponds to one link or monomer stretching into the corresponding x-, y-, or z-direction. Since the links between the monomers typically are flexible, the relative angle between them is not fixed, and each step is more or less independent from the previous one, i.e. from the previous orientation. However, this ignores a simple piece of physics:
This constraint renders the random walk self-avoiding.
Clearly, there are certain conditions on such SAWs: For instance, each SAW
with the same number of links (steps) in the same number of dimensions in a volume
of the same size should occur with the same probability. A collection of such
SAWs is often called a SAW ensemble - like the ensemble of the random walks
discussed previously. The study of such a SAW ensemble and the description of its
properties is called the SAW problem.
The main problem in so doing, however, is to construct the ensemble. There are two approaches doing that: Enumeration and simulation. While enumeration is the explicit construction of all SAWs, simulation refers to sampling from the full ensemble. Both methods are tricky: Enumeration clearly is limited by computer power, since the number of possible SAWs increases dramatically with the number of steps. For the simulation approach one must keep track of the sites visited so far and ensure that they are not included twice. Naively, this sounds simple: At each step, just pick one site of the allowed ones with uniform probability. This, however, has a subtle flaw, since such an algorithm would not lead to all SAWs in the ensemble having the same probability. The solution is to choose any site for a new step, not just restricting to the allowed ones. If a disallowed site is picked, then the full SAW is discarded and a new walk is started from scratch. This is a very inefficient way of simulating, leading to burning CPU time in large proportions.
We will leave this issue here, since a further discussion would lead us too far away from the main goal of this lecture, the discussion of diffusion as a random process.