Let's suppose that you're a real snail fan, and you have this wonderful opportunity to experiment with snails. The problem is that one side of you wants to see how snails behave in a simple grid maze, but the other side of you really wants to study how snails behave when drunk. So, after downing a few beers yourself, you come up with an ingenious method of combining both: experiment with drunk snails in a simple grid maze.
After starting your experiment, you notice two fundamental characteristics of drunk snails in mazes. One, the path a drunk snail takes at each intersection is random. That is, once a snail reaches an intersection, it is equally likely to pick any of four directions to head towards. Secondly, you notice that drunk snails are not much faster than sober snails. In other words, you're getting really tired of watching snails make up their minds on which direction to head.
So (here is where the mathematics comes in,) you decide to do a simulation of the snails on a computer. A regular cartesian plane represents your grid, and each lattice point represents an intersection. You start your simulated snail at the origin, where it randomly picks a neighboring lattice point to move to, each direction having probability 1/4. You repeat this procedure several times and observe the overall behavior of snails after n moves.
In this discussion let's define a "walk" as the path a snail takes. If the distance between adjacent lattice points is 1, then there are 4^n possible walks of length n, each equally likely. That is, there is one possible walk of length 0, four walks of length 1, sixteen walks of length 2, and so on.
It's natural to ask what the "expected" final position of a walk of length n is. If you have a million snails, and you let each snail walk n moves and note its final position, what is the "average" location of the snails? This expected position turns out to be the origin, based on the following reasoning: since all paths are equally likely, for every snail which moves west, there's another which moves east. For every snail which moves north, there's one which moves south, etc. For every snail away from the origin, there's another which "cancels it out."
Because the expected final position is trivial, it is more interesting to find the "mean square displacement" -- the square of the typical distance a snail travels. If we define w(n) as the final position of a snail after n moves, <w(n)> as expected position, and |w(n)| as magnitude of distance from origin, then the expected mean square displacement is <(|w(n)|)^2>. Also, let Xi be a unit vector representing a snail's ith move and note that Xi, Xj are independent for i ‚ j.
Then,
But <w(n)> = 0, [expected position as stated above,] so
= [(j=1 to n)…<(|Xj|)^2>] + [(i ‚ j)…<Xi*Xj>] .
Now |Xj| = 1 and <Xi*Xj> = <Xi>*<Xj> = 0*0 = 0. Hence
= n
To summarize, the typical distance a snail travels from the origin after n moves is of magnitude ˆn. Using the central limit theorem, a neat theorem which helps explain all those normal curves we see in science, we can better approximate w(n). The result follows:
P[w(n)=z] = [2/(¼n)]*exp[-(|z|)^2/n], where z is a given point on the grid.
Perhaps all this mathematics is too much, but it leads to some simple general results. For example, if a snail wanders forever, we can expect it to arrive at the origin an infinite number of times. This infinitely wandering drunk snail will also arrive at certain other intersections an infinite number of times.
The behavior of our drunk snail, more commonly known in mathematics as "simple random walks," is fairly well understood. A related problem, that of "self-avoiding walks" or SAWs, is more complex. Gregory Lawler, Ph.D., a Professor of Mathematics at Duke, has been investigating SAWs for several years.
Mathematically speaking, a self-avoiding random walk is a simple random walk with no self-intersections. The set of all SAWs of length n is uniformly distributed, consisting of all simple random walks of length n minus those with intersections. We can extend our drunk snail analogy if we add the qualification that SAW snails are "high-class": they will not head in any direction where they've left a trail of slime. Thus, it's possible for a snail to trap itself in by its own trail of slime.The number of SAWs is therefore much smaller than the number of simple random walks of the same length n (for large n).
Like their lesser-evolved cousins the simple snails, high-calss snails take a long time to randomly decide in which direction to move. It would once again be nice to be able to simulate the behavior of the snails. The behavior of SAWs, however, is difficult to simulate on a computer. Often in an SAW simulation one of two problems will arise: either the simulation will be very inefficient, or it will fail to reproduce the uniform distribution of SAWs. For example, if we attempt to simulate all SAWs of length n by simulating all simple random walks of length n and ignoring those with intersections, the computational time and memory required would grow exponentially as n increases; this is extremely inefficient. Other, more efficient simulations tend to favor points which have not already been visited, and therefore fail to produce with equal probability all SAWs of a given length.
Though we are unable to carry out an effective SAW simulation, we can estimate how many SAWs of length n exist. Analogously, we can estimate the number of ways in which a high-class snail can move n times. Let Cn denote the number of SAWs of length n.
Let's first determine a lower bound for Cn. To do this we first pick a general direction for the path of the snail: either northeast, northwest, southeast, or southwest. Consider the case in which the general direction is northwest: as long as a snail moves either west or north at any point in its walk, it will never intersect its own path. At every corner, the snail can therefore go in either of two directions without fear of self-intersection. A lower bound for the number of SAWs of length n is thus 4*(2^n), since there are four general directions.
To find an upper-bound, we consider the options a snail has at each point in its walk. Its first move can be in any of four directions, and its next can be in any of three, since it's not allowed go right back where it came from. In fact, in any move other than the first, a snail can move in one of at most three directions, for this same reason. Thus an upper bound for Cn is 4*(3^n-1). (For n<4 this is also a least upper bound, since it is impossible for a snail to form a loop in less than four moves.) Combining our lower and upper bounds, we thus have 2^n < Cn < 4*(3^n-1) for all n>3. (And Cn=4*(3^n-1) for 0 <= n <= 3.) For large n, Cn is estimated to be 2.64^n.
We might consider one last SAW question: on average, how far from the origin (i.e., displacement) does a high-class snail wind up after n moves? The answer turns out to be n^(3/4), but neither the proof nor the reasoning behing this answer have been rigorously completed. Such apparently simple questions still perplex the best mathematicians.
My apologies to Dr. Lawler and the mathematics community for making the unconventional analogy to random walks. The applications of these studies naturally extend far beyond drunk snails. The walks described here have only resided in two-dimensions, but related mathematical studies extend to multiple dimensions. (Unfortunately, I personally find it difficult to describe drunk snails in four dimensions.) One application of three-dimensional self-avoiding random walks is in the modeling of long polymer chains. Such polymers consist of connected monomers which cannot cross over each other, and hence exhibit behavior similar to that found in SAWs. Many other uses of random walks exist in physics, chemistry, and biology. Yet even if potential technological applications did not exist, the study of random walks would be a worthwhile endeavor, if only for its ability to contribute to our knowledge of interesting subjects, like the behavior of drunk snails.
At the time this article was written, Tung Tran was a Trinity College sophomore majoring in mathematics.
Winter 1995 contents
Vertices web central