Vertex-reinforced random walk (VRRW), defined by Pemantle, is a
random process in a continuously changing environment which is more likely to
visit states it has visited before. We consider VRRW on arbitrary graphs and
show that on almost all of them, VRRW visits only finitely many vertices with a
positive probability. We conjecture that on all graphs of bounded degree, this
happens with probability 1, and provide a proof only for trees of this
type.
¶ We distinguish between several different patterns of localization
and explicitly describe the long-run structure of VRRW, which depends on
whether a graph contains triangles or not.
¶ While the results of this paper generalize those obtained by
Pemantle and Volkov for Z1, ideas of proofs are
different and typically based on a large deviation principle rather than a
martingale approach.