Undergraduate research project

Simulating Self Avoiding Random Walks

Office: Math 607

Phone: 621-6696

To construct a random walk, each time you take a step you randomly choose one of the four directions north, east, south or west. In a self-avoiding random walk you are not allowed to visit the same place more than once. While very little has been proved about these walks, they can be simulated rather easily on a computer, and so can be studied numerically. Here are a couple of pictures of computer generated self avoiding walks

If you run an ordinary random walk for a long time and then look at it from far away, it looks like a stochastic process called Brownian motion. Now suppose you do the same thing for self-avoiding random walks. Does it look like a stochastic process, and if so what can you say about the process ? The goal of the project is to study this question empirically, i.e., by simulating lots of self-avoiding walks and seeing what we can say.

The project requires knowing some basic probability concepts such as the distribution function of a random variable. Familiarity with some topics from Math 468, in particular Markov chains, would be useful, but not essential. Since the project will consist of computer simulations, programming skill is needed. However, programs to simulate these self-avoiding walks can be surprising short.