Tuesday, June 23, 2009

self avoidance

Our expeditions are but tours, and come round again at evening to the old hearthside from which we set out. Half the walk is but retracing our steps. We should go forth on the shortest walk, perchance, in the spirit of undying adventure, never to return, prepared to send back our embalmed hearts only as relics to our desolate kingdoms. If you are ready to leave father and mother, and brother and sister, and wife and child and friends, and never see them again -- if you have paid your debts, and made your will, and settled all your affairs, and are a free man - then you are ready for a walk.
from Walking, by Henry David Thoreau

If you write a program to generate self-avoiding random walks akin to the ones that Thoreau describes, I think the first thing that will strike you is how short they tend to be - you quickly end up closing yourself within the path you've already followed. It is easy to imagine infinitely long walks (a straight line, or a slightly jagged variation), but these seem to be rare.

It seems that putting the constraint of self avoidance on a walk makes it into a much nicer object of study. Depending on what other constraints you apply, you can actually enumerate the walks of a given size (see the mathworld entry).

If you let walks run until they can go no further you might notice that for some walks you can tell where the start point is (it is not closed in) and where the end point is (it is closed in). Sometimes it happens that you can't distinguish these by looking at the path (where did the walk below start, and where did it end?).

Clicking on the applet below will create a random walkers that avoid themselves and each other - pressing a key while the applet is selected will clear the screen.

This browser does not have a Java Plug-in. Get the latest Java Plug-in here.

The applet was built using Processing. See also this post about implementing random walks (non-self-avoiding) in Fathom and TinkerPlots.