Walking Wild III

One of the first major uses of probabilistic methods in computers was in calculating the random walks (see "Walking Wild I") of neutrons through different materials—a crucial issue in the design of nuclear weapons and atomic power plants after World War II.

Physicists applied similar techniques to show that a particle of light near the sun's center takes about fifty centuries to stroll in a random walk to the surface before finally escaping the sun and speeding to Earth in about eight minutes.

Mathematicians and scientists also extended the random-walk and Brownian-motion models (see "Quivering Particles II") to encompass other types of phenomena.

The long molecular chain of a polymer floating in a solvent, for example, resembles a miniature, truncated version of the path of a particle undergoing Brownian motion. In other words, you can imagine the chain's small molecular units (called monomers) as points and the chemical bonds between the units as the steps of a three-dimensional random walk.

However, to account for the fact that no two monomers can occupy the same region in space, the random walk has to be modified. A more realistic model is the self-avoiding random walk, which is a path that doesn't intersect itself. Such walks spread out much faster and tend to cover a larger area or volume than their standard counterparts for a certain number of steps.

A short self-avoiding random walk in three dimensions.

Using a self-avoiding random-walk model, polymer scientists can tackle such questions as: How many possible configurations can a long polymer chain adopt? What is the typical distance separating a polymer's ends.

The first question is really the same as asking for the number of different self-avoiding walks that are possible for a given number of steps. That's easy to answer in two dimensions for an ordinary random walk. There are four choices for each step, leading to four one-step walks, 4 ✕ 4 (or 16) two-step walks, and, in general, 4ⁿ n-step walks. Similar formulas can be worked out for other dimensions.

The calculations are a little trickier for a self-avoiding random walk. In two dimensions, there are four one-step walks, 4 ✕ 3 (or 12) two-step walks, and 4 ✕ 3 ✕ 3 (or 36) three-step walks. It turns out that there are 100 four-step walks.

Calculating the number of possible five-step walks is considerably more difficult, and even with computers to help out, no one has ever gone beyond about 39 steps, which has 1.13 ✕ 10¹⁷ possibilities.

Many other problems involving self-avoiding walks—including determination, in different dimensions, of the typical end-to-end distance after a certain number of steps—have turned out to be difficult to solve.

"The Brownian frontier and many other examples of random motions and their interaction properties continue to be an active area of research," commented mathematician Gordon Slade, who worked on self-avoiding random walks as models for polymers.

"Many of the remaining problems are appealing not just because of their relevance to applied fields beyond mathematics but also because the simplicity of their statements has an attraction of its own," Slade added. "This has drawn investigators from diverse backgrounds to study these problems, and there is hope that the progress of the recent past will continue in the coming years."

Next: Money Matters I