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.