Vertex-Reinforced Random Walks: What's New?
Vertex-Reinforced Random Walk (VRRW) is a non-Markovian random process which "prefers" to visit the states it has visited before. The questions about VRRW are classical examples of problems which are very easy to formulate but extremely hard to solve. We consider VRRW on a very general class of infinite graphs and show that, with a positive probability, VRRW on them visits only finitely many points. We conjecture that on all graphs of bounded degree this takes place a.s. (this has only been shown for the case of trees). The proof is based on identifying a "trapping" subgraph on which VRRW can get stuck and showing how this actually happens (and what the limiting empirical occupational measure is). An interesting finding is that this limiting measure is dependent on whether the graph contains triangles or not. These results represent my on-going research and generalize those obtained by Pemantle and Volkov (1998) for $\Z^1$, though using a different technique.