A series of distinct vertex on a graph or lattice for which each vertex is a nearest neighbour of the previous and following vertices in the series. May also be thought of as a random walk which never visits a site more than once.

Used as a model in polymer statistical mechanics, among other systems.

The self-avoiding random walk or simply self-avoiding walk (SAW) is the random walk's (or the drunkard's walk, as it is sometimes known) austere cousin. It is a random walk which does not intersect itself. Naïvely, one might describe the SAW walk by extension of the description of the random walk: every second, a drunkard takes a step in a random direction, drawing a line on the ground tracing their step, except that the drunkard takes care never to cross a line they've already drawn. Or, in more mathematical language, at each time-step t, a vertex rt+1, adjacent to the current vertex rt on the graph on which the walk is performed, is chosen randomly to be the next time-step's "current vertex", under the condition that it has never before been the "current vertex".

This, however elegant of a description it might seem, is wrong. Or at least, it is not a description of what people refer to when they talk about SAWs, it is a description of something else. The correct description of the SAW is this: a SAW is a randomly picked member of the set of all random walks which do not intersect themselves, where each such walk has equal probability to be chosen. If you want a description using drunkards, here it is: we let the drunkard go in any random direction, but as soon as they intersect their own path, we kill them. Yes, we kill them. But we don't just have one drunkard, we have a mass of drunkards (an ensemble of drunkards, to use the technical term), and we only interest ourselves in the surviving drunkards.

So what's the difference between the two descriptions you ask? Well, the set of SAWs is the same under both descriptions, but it's the probabilty assigned to each walk that differs. Take for example these two four-step walks on the square lattice (starting at "s", terminating at "t"):

x---x       x---x---x---t
| | |
s x---t s

Under the first description, the four steps of the left-hand walk have in turn the probabilities 1/4, 1/3, 1/3, and 1/2 to have been thus performed given the state of the walk up till the time they were taken (since at the last step only two directions are possible without self-intersection). In the right-hand walk, the probabilities are 1/4, 1/3, 1/3, and 1/3. So, while the left-hand walk is generated with probability 1/72, the right-hand walk is generated with probability 1/108. Under the second description, the two walks are chosen with the same probability.

SAWs are important in the statistical physics description of polymers. In particular, an interesting property of the SAW to calculate and to measure experimentally in polymers is the end-to-end distance statistics. That is to say, the probability distribution associated with the distance from one end of the walk to the other as a function of the length of the walk. One finds that the typical distance R, for long walks (number of steps N large), goes as a distinct power law:

R =~ c Nν

The value of the exponent ν is different for SAWs of different dimensions: ν = 3/4 for SAWs on 2-dimensional lattices, ν = 0.59... (no exact value known) for SAWs in 3 dimensions, and ν = 1/2 for SAWs in 4 or more dimensions and for regular random walks (non self-avoiding) of all dimensions. ν is an example of a critical exponent. Another critical exponent shows up in the formula describing the number of SAWs of length N (again, for large enough N):

# of SAWs of length N =~ c Nγ-1 μN

Here μ is the connective constant of the lattice, and γ is another critical exponent. Note that while μ is different for different lattices, ν and γ are the same for all lattices of the same dimension. This is an example of the universality of critical exponents. It is an interesting result (due to Pierre-Gilles de Gennes) that the problem of SAWs has the same critical exponents as the problem of magnetic systems with n-component spins (a/k/a the O(n) model) in the limit that n goes to zero.

Log in or register to write something here or to contact authors.