Self-avoiding walks
Thanks to Steve, I discovered a list of mathematical articles from the American Scientist periodical that are available for free download. Last night I printed out several, and I started reading them today. One of them, “How to avoid yourself”, is about self avoiding walks, which apparently have applications to protein folding, among other things.
A random walk takes place on a lattice, a grid in 
with each point having integer coordinates, and is a random sequence of adjacent points in this lattice which describes the ‘movement of a particle’. A self avoiding walk is a random walk in which no point appears in the sequence twice.
One interesting result by Euler is that random walks in 2 dimensions always return to the starting point (I would love to see the proof of this) if the walk goes on long enough, but in 3 dimensions, a random walk does not necessarily return to its starting point.
An interesting non-result is the fact that no one has yet proven an asymptotic formula for the number of self-avoiding walks of a given length (that is, the number of random walks of a given length which are self-avoiding) although there have been persuasive intuitive arguments to support one candidate.
Is it worth anything to calculate the probability of an 
-length self-avoiding walk becoming self-intersecting after one more move? (This seems simple enough, and the article even says it is <1%) Could this be used to put probabilistic bounds on the number of self-avoiding walks? I’m not a probability buff, but it seems like there is a way to do so…
Possibly relevant posts:
- More lattice stuff (2/18/2005)
- Stochastic Lyapunov functions (5/6/2007)
- Expected maxima of subsequences (8/4/2008)