Properties of random walks with memory

Let G be a connected graph. Imagine a particle moving along the vertices of G according to the following rules:

(i) if currently at vertex v, in the next step the particle jumps to one of the neighbors of v,

(ii) the probability of a jump to a neighbor v' is proportional to the number of previous traversals of the edge connecting v and v'.

This process is the original reinforced random walk introduced by Coppersmith and Diaconis in 1987 as a model of a person exploring a new city. The reinforced random walk and its generalizations became important ingredients in models of spatial exploration and cooperative interaction. These processes often yield new and surprising behavior. There are no general techniques developed for studying them. I will list major open questions and discuss two recent results: attracting edge property under strong power law reinforcements, and transience of once-reinforced walks on regular trees.