Random walks with memory: Background

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 $v_0$ to a neighboring vertex $v_1$ and then make a next transition from $v_1$ back to $v_0$ .

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 $\mathbb{Z}$ 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.

A self-avoiding walk that has not – yet – got stuck

Recent memory

This getting-stuck phenomenon can happen for a random walk on the infinite lattice $\mathbb{Z}\times \mathbb{Z}$ – where there is an edge from vertex (m,n) to vertex (p,q) if and only if $\vert m-p\vert + \vert n-q\vert = 1$ – when the random walk has memory 7:

Basic questions

So … for random walks with memory of the previous m sites visited where $1 \leq m \leq \infty$ 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 $\mathbb{Z}^d$ that the walk is recurrent for d = 1 or 2 and transient for $d \geq 3$ . 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 $\mathbb{Z}^d$ is recurrent only for $d=2$ .

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.

Steps in a 2-dimensional Levy flight

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