The Self-Avoiding Random Walk

Self-Avoiding Random Walk Java Applet

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 N (the degree of polymerization) is as high as 108. At other times there are only several hundred, as in small proteins.

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., CH2 in polyethylene. The attraction between monomers can be stronger than their attraction to the molecules of the surrounding solvent, for example, water. When this is the case, they are called hydrophobic. When the attraction between monomers is weaker than their attraction to the molecules of the surrounding solvent, they are called hydrophilic. But common to all polymers are long monomer chains in which no two monomers can occupy the same place, i.e., they have an ``excluded volume.'' In other words, polymer chains cannot self-intersect.

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 polymerization R ~ N1/2. Or, since every monomer has approximately the same mass, the mass of the polymer chain is proportional to the square of its linear dimension: M ~ R2. This means that the fractal dimension of a polymer chain should be two.

Light-scattering and other experiments have shown that this is incorrect, and that R grows more quickly than N1/2. The answer to this puzzle was discovered by Nobel Laureate Paul Flory, who suggested that this discrepancy must be due to the excluded volume effect. The random walk tends to entangle, while the monomers try to bounce away from each other as molecules of gas. Thus he calculated the free energy of a polymer chain as a sum of the free energy of the real gas and the entropic contribution from the random walk.

Finding its minimum versus R, he derived that, at equilibrium,

In other words, the fractal dimension of a polymer chain in a solvent is 5/3 in three dimensions and 4/3 in two dimensions. Flory's theory was successfully tested by experimentalists. Ever since Flory presented his heuristic solution, physicists and mathematicians have tried to solve the problem of the random walk with excluded volume, also called the self-avoiding random walk (SAW). Significant progress was made by S. Edwards and P.G. de Gennes, who understood that the problem of SAW could be treated the same way as the problem of ferromagnetic material near its critical temperature, known as Curie point. But still the exact solution was missing.

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 N, the task was to find those that do not self-intersect and to compute the average square distance they travel. (For all random walks the answer is known exactly: < R2 > = N).

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 R ~ N3/4 when N goes to infinity for two dimensional SAWs is exact. But this assumpion has never been proven in a rigous mathematical sense. In three dimensions, no exactly solved models are known, however Flory's approximation for the average size of three dimensional SAWs is now believed to be slightly above its true value.

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 N <= 9. How many random walks did he study? How many years did he spend if it took him one minute to draw each random walk and to find its square displacement? (Assume he worked 8 hours a day, 5 days a week.)

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 survives after N steps, we compute the square of the distance from the origin, sum it up, and divide by the number of survivals. This variable is plotted on the vertical axis of the graph, which is plotted to the right of the field where random walks travel. You see that the graph is not straight, but looks like a parabola---suggesting that R2 grows faster than N. If we take logarithms of both R and N (applying the log-log graph option) we get a straight line log R = b + k log N, which means that R=a NK (where a and b is an unimportant constant, but K gives the answer to Flory's problem in two dimensions! Test Flory's hypothesis using as many random walks as possible.

Similar program was first written in 1954 by Wall, Hiller and Wheeler. Unfortunately, the probability of a random walk reaching length N before self-intersecting decreases approximately as (0.66)N.

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 (0.88)N. We apply this method in order to save computer time in our simulations.

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 R2 still grow as N3/2? What is the relevance of the IGSAW to polymer science?