COMPUTING SCIENCE

# How to Avoid Yourself

# Don't Look Back

An intermediate stage between a purely random walk and a self-avoiding walk is the nonreversing walk. As a recipe for an urban perambulation, it allows you to go left, right or forward at each intersection, but not to make a U-turn and go back the way you just came. Thus a nonreversing walker on a square lattice has four choices for the first step, but only three choices for each step thereafter. The number of *n*-step walks is 4 x 3^{n–1}, which for large *n* converges to 3^{n}.

Typical examples of random walks, nonreversing walks and self-avoiding walks can be distinguished at a glance. The random walk usually consists of dense regions, where most of the lattice points have been visited at least once, connected by tendrils through more sparsely settled territory. A trace of the walk looks something like a map of towns and cities along a river. The nonreversing walk is similar but suggests a more open landscape—perhaps suburban sprawl rather than the city center. And the trace of a self-avoiding walk looks not like cities along a river but like the river itself, or like a coastline.

These differences in appearance are reflected in quantitative measures of the walks' geometry. One important measure is the square of the distance between the end points of the walk. For *n*-step random walks the mean-squared displacement is *n*; for nonreversing walks it is 2*n*. Self-avoiding walks are qualitatively different. The mean-squared displacement grows as a nonlinear function of *n*, which appears to be *n*^{3/2}.

There is another important difference between random walks and self-avoiding walks. Every random walk can go on forever; you can always take one more step. But a self-avoiding walk can stumble into a blind alley, getting trapped at a lattice site where none of the neighbors are unvisited. In other words, sometimes you can't avoid yourself no matter how hard you try. On any given step the probability of getting boxed in is small—a little less than 1 percent—but if you extend a walk indefinitely, it is certain to wander into a dead end eventually. This is another way of saying that self-avoiding walks are rare and special; they have to beat the odds to survive.

EMAIL TO A FRIEND :

**Of Possible Interest**

**Computing Science**: Computer Vision and Computer Hallucinations

**Feature Article**: In Defense of Pure Mathematics

**Feature Article**: Candy Crush's Puzzling Mathematics