A simple random walk on a graph (finite or infinite) is a sequence of transitions from a vertex to a neighboring vertex where the transition to a neighboring vertex is given by a probability distribution.

Commonly, in a so-called *symmetric* simple random walk, the probability of making a transition from a vertex v to a neighboring vertex is 1/p where p is the number of neighboring vertices for v: in other words the random walk transitions from vertex v to each of the neighboring vertices with equal probability. This assumes, of course, that the graph is *locally finite*: each vertex has only a finite number of neighboring vertices.

## No backtracking

Simple random walks do not have memory: a random walk may transition from a vertex to a neighboring vertex and then make a next transition from back to .

Random walks that never do this – that is, have a memory of the previous vertex last visited and do not immediately re-visit it – are called random walks with *no-backtracking*. They are, in an obvious sense of the phrase, random walks with memory 1.

Random walks with memory 1 generally cover all, or a significant portion, of the graph faster then random walks with no memory. This takes some work to prove in particular cases, yet is sort of obvious in that a random walk with memory 1 is prohibited from going back to whence it immediately came, and so will spread to its other neighbors with slightly greater probability.

Yet a random walk pays a price for memory. On the graph consisting of the integers with an edge joining successive integers, a random walk with memory 1 must head off entirely in one direction after the first step:

## Total recall

Random walks with *total recall* – also known, for obvious reasons, as self-avoiding walks – have an additional issue in that they commonly become trapped: because such a random walk remembers every place it has ever been, and typically gets stuck in a *cul-de-sac* where each of the possible next transition vertices have been visited already.

## Recent memory

This getting-stuck phenomenon can happen for a random walk on the infinite lattice – where there is an edge from vertex (m,n) to vertex (p,q) if and only if – when the random walk has memory 7:

## Basic questions

So … for random walks with memory of the previous m sites visited where there are a number of issues to settle:

- With what probability will the random walk get trapped?
- Will the walk be transient or recurrent? (A random walk is
*recurrent*if it visits its starting position infinitely often with probability one and*transient*if it visits its starting position finitely often with probability one.) - At what rate will the random walk cover the graph (if at all)?

We know, for example, that for a simple random walk with memory 0 on the integer lattice that the walk is recurrent for d = 1 or 2 and transient for . This is a basic result of George Polya. Recently, Mark Kempton has proved that a simple random walk with memory 1 (i.e. no backtracking) on the integer lattice is recurrent only for .

## And then there’s Levy flights …

A Levy flight is a random walk in which step lengths are not discrete but are given by some – usually heavy-tailed- probability distribution.

One can think of foragers, such as birds pecking in a region and then flying off in a uniformly random direction for a random distance and pecking around that region before repeating the action.

A Levy flight, by definition, has memory 0. What, however, if we introduce a small amount of memory, in that the Levy walk could not return to a region of radius around its last transition point? What would such Levy flights with memory look like?