The Self-Avoiding Random Walk
The molecules from which our body is made are macromolecules or
polymers. They are called ``macromolecules'' because they are very
large, thousands and sometimes millions of times larger than a single
water molecule. Some of them, such as DNA and RNA molecules, can be seen
under an electron microscope. They are also called ``polymers'' because they
are made up of long chains of ``monomer'' units. Sometimes---e.g., in
DNA---the number of monomers
The monomers can be of different natures. In DNA and RNA they are
called nucleotides; in proteins they are called amino acids. In simple
artificial polymers it can be a group of just a few atoms, e.g.,
What are the consequences of these basic properties of polymers? Actually, this question is the only one that physicists can answer. The more specific questions about the details of polymeric interactions are for chemists and biologists. Physicists attempt to simplify complex phenomena as much as possible and thus think of polymer chains as threads, shoelaces, or necklaces made of beads on a string.
These simplified models capture some essential property of a polymer. Polymers can become entangled and form messy coils like a length of thread or a shoelace. The excluded volume property of the monomers can be visualized as beads on a string.
The next level of abstraction comes when we think about some mathematical object that can formalize our notion of a shoe lace or string of beads. The best candidate for this mathematical object is a random walk. A little piece of a shoelace or a bead in a necklace can represent a step in a random walk, because each piece/bead/step can change its direction almost independently of the positions of previous pieces/beads/steps.
The random walk approximation for polymers was proposed about 60
years ago by German chemist W. Kuhn. This model allows experimental
testing: the diameter of a polymer chain or the mean-square end-to-end
distance shows that growth occurs as the square root of the degree of
Light-scattering and other experiments have shown that this is
incorrect, and that
Finding its minimum versus
In other words, the fractal dimension of a polymer chain in a
As soon as computers were invented, researchers began
modeling random walks without self-intersection. They did this on
square and cubic lattices, because that allowed the problem to be
formulated in a very obvious way. Among all random walks of length
As with the Great Fermat Theorem, which was first scrawled on the
margin of a book but then took more than 300 years to prove, it has taken a
significant amount of time to work through the Flory theorem. In 1982,
Dutch physicist B. Nienhuis found an exact solution of a certain two
dimension model similar to the famous Ising model of ferromagnetic.
If one assumes that this
model and SAW are equivalent
then the result
Activity: Find all possible random walks without self-intersections on the square lattice for length N=1,2,3, . . . and compute their mean square displacement. (In the 1940s, before the invention of computers, Japanese physicist Teramoto made these calculations by hand for
In our SAW applet we start random walks on a square lattice and
then discard them as soon as they self-intersect. If a random walk
Similar program was first written in 1954 by Wall, Hiller and
Wheeler. Unfortunately, the probability of a random walk reaching length
If one makes the random walks a little bit ``smarter'' by not allowing
them to step backwards (stepping backwards inevitably leads to
self-intersection) then SAWs will survive with higher probability of
Problem: How many attempts do you need to obtain at least one self-avoiding random walk of length 40? Of length 80? What is the half-life length of a SAW?
In 1955, a team of computer scientists (consisting A. W. Rosenbluth and M. N. Rosenbluth) decided to make random walks even smarter, allowing them to step only onto unoccupied sties. Thus the walk can choose between one, two, or three lattice sites, depending on the position of its end. If a walk ends up completely trapped, a new random walk is started from the origin.
About 30 years later the problem was revisited, and even smarter 2d
random walks were invented---walks that can never be trapped [see
K. Kremer and T. W. Lyklema, Phys. Rev. Lett. 55, 9091 (1985);
and T. M. Bishtein, S. V. Buldyrev, and A. M. Elyashivitch, Polymer
26, 1814 (1985)]. These walks have been named infinitely growing
self-avoiding walks (IGSAW). What will be the answer if one computes an
average square displacement for IGSAW? Will the
This lesson was developed by Sergey Buldyrev (BU) and the JAVA applet was written by Gary McGath. Copyright 1996-2000, Center for Polymer Studies.