VRRW on complete-like graphs: almost sure behavior

DOI10.1214/10-AAP687MaRDI QIDQ614128zbMATH OpenOpenAlexFDO

Authors Vlada Limic, Stanislav Volkov

Publication date 27 December 2010

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

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

zbMATH Keywords

complete graphlarge deviationsmartingalesurn modelvertex-reinforced random walks

Mathematics Subject Classification ID

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

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.

Review text

The authors study the vertex-reinforced random walk (VRRW) on complete-like graphs, i.e., complete graphs ornamented with finitely many leaves at each vertex. They combine martingale and large deviation techniques to prove that almost surely such VRRW spends positive and equal proportions of time on each of its nonleaf vertices. Previously [\textit{S. Volkov}, Ann. Probab. 29, No.~1, 66--91 (2001; Zbl 1031.60089)], it was shown that this behavior occurs only up to an event of positive probability. The convergence rate of the empirical occupation measure is studied as well.

Recommendations

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

Cites work

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

Cited in

(2)

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

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)