Vertex-reinforced random walk on ℤ eventually gets stuck on five points

2004/07/01 by Pierre Tarres, Pierre Tarrès · 6 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics #math.PR #msc:34F05 #msc:60G17 #msc:60J20.

paper · pdf · doi:10.1214/009117907000000694

published as Annals of Probability 2004, Vol. 32, No. 3B, 2650-2701 · Published by the Institute of Mathematical Statistics (http://www.imstat.org) in the Annals of Probability (http://www.imstat.org/aop/) at http://dx.doi.org/10.1214/009117907000000694

openalex publication_date 2004/07/01 · arxiv created 2004/10/06 · arxiv updated 2009/12/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/01

Abstract

Vertex-reinforced random walk (VRRW), defined by Pemantle in 1988, is a random process that takes values in the vertex set of a graph G, which is more likely to visit vertices it has visited before. Pemantle and Volkov considered the case when the underlying graph is the one-dimensional integer lattice ℤ. They proved that the range is almost surely finite and that with positive probability the range contains exactly five points. They conjectured that this second event holds with probability 1. The proof of this conjecture is the main purpose of this paper.

Cited by

• Intermittent localization and fast spatial learning by non-Markov random walks with decaying memory
• Interacting vertex reinforced random walks on complete sub-graphs
• An asymptotic result for Brownian polymers
• Reinforcement learning in signaling game
• VRRW on complete-like graphs: Almost sure behavior
• Limit theorems for vertex-reinforced jump processes on regular trees

Related

• Vertex-reinforced random walk on arbitrary graphs
• Vertex-reinfoced random walk on Z visits finitely many states
• Localization on 4 sites for Vertex-reinforced random walks on \mathbb Z
• Localization of reinforced random walks
• Strongly Vertex-Reinforced-Random-Walk on the complete graph