On a two-dimensional square lattice the number of n-step random walks is 4n. What if we require that the walk is self-avoiding — that is, that it never revisits a location? The number of walks must be a multiple of an exponential to some base. Because the number of walks that never backtrack — that is, that never retrace at one step the path of the last step — is 4·3n–1 , the base must be less than 3. Not being an expert in the field, I was surprised to learn that the exact number is unknown. It is something very near to 2.63816, but the mathematics is too difficult for us to be able to pin it down exactly.
That’s too bad, because in three dimensions self-avoiding walks provide approximate models for long-chain polymers (two atoms may not, unless quantum theory has undergone a recent revision, occupy the same space at the same time) and they might be of interest or even helpful. The mathematics is of course even more difficult than in two dimensions, though the value of the exponential base is known to be about 4.68391. There are only approximations to another quantity of interest, the average displacement of the walk after n steps, something that is known for non-self-avoiding walks.
An exercise for the reader is to determine the number and average displacement of self-avoiding walks in one dimension. The answers (don’t peek!) are 2 and the exact displacement is n.
When the number of dimensions gets up to 5 or 6 or more, life gets simpler because, there being more room to roam, the likelihood that a walk is not self-avoiding goes down and eventually becomes negligible. That, however, is not going to help us with DNA molecules.
The Self-Avoiding Walk is a reprint of the original 1993 edition and is part of the Modern Birkhäuser Classics series. It provides numerous theorems and their proofs. It was complete for its time, with 237 items in its list of references; since then one large outstanding conjecture has been verified but the basics remain unchanged. It would be chore to plow through the book from beginning to end, but if you want to know anything about self-avoiding walks, it is the place to look first.
Woody Dudley, who retired in 2004, has reached such an age that his feet find it difficult to be self-avoiding when he walks.