VRRW on complete-like graphs: almost sure behavior

DOI10.1214/10-AAP687zbMATH Open1229.60057arXiv0904.4722OpenAlexW3098553937MaRDI QIDQ614128FDOQ614128

Authors: Vlada Limic, Stanislav Volkov 

Publication date: 27 December 2010

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Abstract: By a theorem of Volkov (2001) we know that on most graphs with positive probability the linearly vertex-reinforced random walk (VRRW) stays within a finite "trapping" subgraph at all large times. The question of whether this tail behavior occurs with probability one is open in general. In his thesis, Pemantle (1988) proved, via a dynamical system approach, that for a VRRW on any complete graph the asymptotic frequency of visits is uniform over vertices. These techniques do not easily extend even to the setting of complete-like graphs, that is, complete graphs ornamented with finitely many leaves at each vertex. In this work we combine martingale and large deviation techniques to prove that almost surely the VRRW on any such graph spends positive (and equal) proportions of time on each of its nonleaf vertices. This behavior was previously shown to occur only up to event of positive probability (cf. Volkov (2001)). We believe that our approach can be used as a building block in studying related questions on more general graphs. The same set of techniques is used to obtain explicit bounds on the speed of convergence of the empirical occupation measure.

Full work available at URL: https://arxiv.org/abs/0904.4722

Recommendations

• Strongly vertex-reinforced-random-walk on a complete graph
• Vertex-reinforced random walk on arbitrary graphs
• Vertex-reinforced random walk on \(\mathbb Z\) eventually gets stuck on five points.
• Dynamics of vertex-reinforced random walks
• Strongly vertex-reinforced jump process on a complete graph

zbMATH Keywords

martingaleslarge deviationscomplete graphurn modelvertex-reinforced random walks

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Sums of independent random variables; random walks (60G50)

Cites Work

• Phase transition in reinforced random walk and RWRE on trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• Vertex-reinforced random walk on \(\mathbb Z\) has finite range
• Vertex-reinforced random walk on \(\mathbb Z\) eventually gets stuck on five points.
• Functional limit theorems for multitype branching processes and generalized Pólya urns.
• A survey of random processes with reinforcement
• Network formation by reinforcement learning: the long and medium run
• Bernard Friedman's Urn
• Phase transition in vertex-reinforced random walks on \({\mathbb{Z}}\) with nonlinear reinforcement
• Vertex-reinforced random walk on arbitrary graphs
• Dynamics of vertex-reinforced random walks

Cited In (2)

• Dynamics of vertex-reinforced random walks
• Strongly vertex-reinforced-random-walk on a complete graph

This page was built for publication: VRRW on complete-like graphs: almost sure behavior

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q614128)