Vertex-reinforced random walk on arbitrary graphs (Q1872176)

Vertex-reinforced random walk (VRRW) on a graph \(G\) is a process which moves, at time \(n\), from a vertex to its neighbours with probabilities proportional to the local times of these neighbour vertices at time \(n\) (where the initial local time is set to \(1\), for all vertices of the graph). In other words, VRRW is a random process in a continuously changing random environment which is more likely to visit vertices it has visited before. The author shows that under very mild conditions on the graph, the probability that VRRW visits only finitely many vertices is strictly positive. In particular, this is the case if the graph has bounded degree or if the graph does not contain triangles. He also shows that on a tree of bounded degree, VRRW visits only finitely many vertices with probability \(1\), and conjectures that this holds true for any graph of bounded degree. Further, the paper contains several results on the patterns of localisation, i.e. on the limiting occupational measure of VRRW. While the results generalize those of Pemantle and Volkov for \(G=Z^1\), the proofs are different and use large deviation principles instead of martingale arguments.