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.
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 .
4. The number of random walks starting from a fixed place – say the origin – and of length .
For non-reversing walks on the integer lattice the number of walks of length .
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 .
A walk with memory on a lattice is a walk that does not visit any of the 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 , of length 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.