Research in Scientific Computing in Undergraduate Education

Walks with memory

A walk with no memory is a random walk. A walk with unlimited memory is a self-avoiding walk. In between no memory and unlimited memory we can have bounds on the amount of memory possessed by a walker.  A walk with memory 1 – that is, a walk in which the walker avoids the last spot visited – is just a walk with no back-tracking, also known as a non-reversing walk.

Let’s restrict walks to lattices, such as integer lattice, hexagonal, or cubic lattice in the plane.

A hexagonal and a cubic lattice

A hexagonal and a cubic lattice

Quite a bit is known about random walks on an integer lattice. For example:

1.The walk is recurrent – that is, the walker returns to the starting point with probability 1.

2. The expected number of steps to return to the starting point is infinite.

3. The distance from the starting point of a random walker who has taken n steps is on the order of \sqrt{n}.

4. The number of random walks starting from a fixed place – say the origin (0,0) – and of length n \textrm{ is } 4^n.

For non-reversing walks on the integer lattice the number of walks of length n \textrm{ is } 4 \times 3^{n-1}.

For self-avoiding walks on the integer lattice the number of walks of length n is not known in a closed form. It is approximated as 2.64^n.

A walk with memory m on a lattice is a walk that does not visit any of the m previous places it has visited. The aim of this project is to examine the growth rate of the number of walks with a finite memory m \textrm{, where } 0<m<\infty, of length n on various 2-dimensional lattices.

References & readings

Tony Guttman (2003) Random and self-avoiding walks (guttman_random_and_self-avoiding_walks)

Brian Hayes. How to avoid yourself. American Scientist.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: