Vertex-reinforced random walk on arbitrary graphs

DOI10.1214/AOP/1008956322MaRDI QIDQ1872176zbMATH OpenOpenAlexFDO

Authors Stanislav Volkov

Publication date 6 May 2003

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

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

zbMATH Keywords

large deviation principlelocal timemartingalesPolya urn modelvertex-reinforced random walk

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Processes in random environments (60K37)

Abstract: Vertex-Reinforced Random Walk (VRRW), defined by Pemantle (1988a), 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 a.s., 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 (1998) for Z,ideas of proofs are different and typically based on a large deviation principle rather than a martingale approach.

Review text

Vertex-reinforced random walk (VRRW) on a graph \(G\) is a process which moves, at time \(n\), from a vertex to its neighbours with probabilities proportional to the local times of these neighbour vertices at time \(n\) (where the initial local time is set to \(1\), for all vertices of the graph). In other words, VRRW is a random process in a continuously changing random environment which is more likely to visit vertices it has visited before. The author shows that under very mild conditions on the graph, the probability that VRRW visits only finitely many vertices is strictly positive. In particular, this is the case if the graph has bounded degree or if the graph does not contain triangles. He also shows that on a tree of bounded degree, VRRW visits only finitely many vertices with probability \(1\), and conjectures that this holds true for any graph of bounded degree. Further, the paper contains several results on the patterns of localisation, i.e. on the limiting occupational measure of VRRW. While the results generalize those of Pemantle and Volkov for \(G=Z^1\), the proofs are different and use large deviation principles instead of martingale arguments.

Recommendations

• Vertex-reinforced random walk
• Strongly vertex-reinforced-random-walk on a complete graph
• Vertex reinforced random walks with exponential interaction on complete graphs
• Dynamics of vertex-reinforced random walks
• Edge-reinforced random walk on finite graphs
• A note on vertex-reinforced random walks.

Cites work

• scientific article; zbMATH DE number 41722 (Why is no real title available?)
• scientific article; zbMATH DE number 739267 (Why is no real title available?)
• scientific article; zbMATH DE number 3410334 (Why is no real title available?)
• Phase transition in reinforced random walk and RWRE on trees
• Reinforced random walk
• Reinforced random walk on the d-dimensional integer lattice
• Vertex-reinforced random walk
• Vertex-reinforced random walk on \(\mathbb Z\) has finite range
• Vertex-reinforced random walks and a conjecture of Pemantle

Cited in

(36)

• Recurrence of edge-reinforced random walk on a two-dimensional graph
• Vertex-reinforced random walk
• Vertex-reinforced random walks and a conjecture of Pemantle
• A note on vertex-reinforced random walks.
• Some results regarding vertex-reinforced random walks.
• Attracting edge property for a class of reinforced random walks
• Vertex-reinforced random walk on \(\mathbb Z\) has finite range
• Ant foraging and geodesic paths in labyrinths: analytical and computational results
• Vertex reinforced non-backtracking random walks: an example of path formation
• Vertex-reinforced random walk on Z eventually gets stuck on five points.
• Long term behaviour of a reversible system of interacting random walks
• On recurrence and transience of self-interacting random walks
• Strongly vertex-reinforced jump process on a complete graph
• The directed edge reinforced random walk: the Ant Mill phenomenon
• Vertex reinforced random walks with exponential interaction on complete graphs
• Localization on 5 sites for vertex reinforced random walks: towards a characterization
• Edge-reinforced random walk on a ladder
• Localization on 4 sites for vertex-reinforced random walks on \(\mathbb{Z}\)
• Attracting edge and strongly edge reinforced walks
• On the transience of processes defined on Galton-Watson trees
• Edge-reinforced random walk on finite graphs
• Strongly vertex-reinforced-random-walk on a complete graph
• Preferential duplication graphs
• A random Schrödinger operator associated with the Vertex Reinforced Jump Process on infinite graphs
• A PDE model for the dynamics of trail formation by ants
• THE NEAREST UNVISITED VERTEX WALK ON RANDOM GRAPHS
• Two repelling random walks on \(\mathbb{Z}\)
• Local limit theorem for a Markov additive process on with a null recurrent internal Markov chain
• VRRW on complete-like graphs: almost sure behavior
• Dynamics of vertex-reinforced random walks
• Stochastic processes with competing reinforcements
• Recurrence-transience phase transition of the step-reinforced random walk at 1/2
• An asymptotic result for Brownian polymers
• Phase transition in vertex-reinforced random walks on \({\mathbb{Z}}\) with nonlinear reinforcement
• Stability of a growth process generated by monomer filling with nearest-neighbour cooperative effects
• Attraction time for strongly reinforced walks

This page was built for publication: Vertex-reinforced random walk on arbitrary graphs

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