Logo IMG
HOME > PAST ISSUE > Article Detail


How to Avoid Yourself

Brian Hayes

Counting Your Steps

Just how many distinct n-step self-avoiding walks can you take on a square lattice? There is no simple exact formula, analogous to the expression 4n that enumerates random walks, but upper and lower bounds can be stated. The number of self-avoiding walks has to be less than 3n because that is the number of nonreversing walks, which include the self-avoiding walks as a subset. Similarly, it's easy to construct subsets of the self-avoiding walks whose numbers grow as 2n; an example is the family of walks that move only north or east at each step. Thus the number of n-step self-avoiding walks should lie between 2n and 3n. Tighter bounds than these have been established, but still the only known way to get an exact tally is to actually trace out all the n-step walks and count them.

If you were asked to enumerate all the self-avoiding walks of, say, 15 steps, how would you answer? One useful rejoinder would be: Show me all the 14-step walks and I'll construct the 15-step ones. Adding the final step to each walk is straightforward: Just try each of the four possible directions, accepting a move if the neighboring site is vacant, and otherwise rejecting it. Then the question becomes how do you generate all the 14-step walks, and of course the answer is first to produce the 13-step walks. This regress continues back to the 0-step walk, which is just the single point at the origin.

The procedure is uncomplicated, but the counting itself is arduous. There are 284 walks of five steps, and 44,100 of 10 steps. By n=15 the number of walks has reached 6,416,596, and at n=20 it is 897,697,164. The rate of growth is so steep and relentless that merely fine-tuning a program to improve its efficiency yields only a paltry reward. Counting the walks of n+1 steps takes longer than counting all the walks from 1 through n steps.

Figure 2. Lattice walksClick to Enlarge ImageFigure 3. SymmetriesClick to Enlarge Image

Most of the records for counting self-avoiding walks belong to A. J. Guttmann and his colleagues at the University of Melbourne. As early as 1972 Guttmann was part of a group (led by M. F. Sykes of the University of London) that counted all walks of up to 24 steps. In 1987 Guttmann raised the bar to 27 steps, then later to 29. Others then reached 30 and 34 steps, and Guttmann's group went on to 39. Then in 1996, in an extraordinary feat of computing, A. R. Conway and Guttmann enumerated all the self-avoiding walks through n=51. There are 14,059,415,980,606,050,644,844 walks of 51 steps. Performing this computation required an algorithm more sophisticated than the one sketched here, as well as an Intel Paragon supercomputer that dedicated 1,024 processors and 10 gigabytes of memory to the task.

Guttmann's long series of enumerations yields an estimate of the asymptotic growth rate in the number of walks—the rate to which the series apparently converges in the limit of large n. Based on the known data, increasing n by 1 multiplies the number of self-avoiding walks by about 2.638; in other words, the number of n-step walks is proportional to 2.638n.

Even though self-avoiding walks are so numerous we can't count any but the shortest of them, they still remain rarities among all possible lattice walks. At n=20 fewer than one walk in 1,200 is self-avoiding. At n=50, the ratio is one out of 240 million.

comments powered by Disqus


Of Possible Interest

Computing Science: Computer Vision and Computer Hallucinations

Feature Article: In Defense of Pure Mathematics

Feature Article: Candy Crush's Puzzling Mathematics

Subscribe to American Scientist