Vertex-reinforced random walk on arbitrary graphs

S Volkov

Research output: Contribution to journalArticle (Academic Journal)peer-review

38 Citations (Scopus)


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 Z(1), ideas of proofs are different and typically based on a large deviation principle rather than a martingale approach.
Translated title of the contributionVertex-reinforced random walk on arbitrary graphs
Original languageEnglish
Pages (from-to)66 - 91
Number of pages26
JournalAnnals of Probability
Volume29 (1)
Publication statusPublished - Feb 2001

Bibliographical note

Publisher: Institute of Mathematical Statistics


Dive into the research topics of 'Vertex-reinforced random walk on arbitrary graphs'. Together they form a unique fingerprint.

Cite this