# 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

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, of length $n$ on various 2-dimensional lattices.