Dynamics of vertex-reinforced random walks

DOI10.1214/10-AOP609zbMATH Open1242.60044arXiv0809.2739MaRDI QIDQ653301FDOQ653301

Michel Benaïm, Pierre Tarrès

Publication date: 9 January 2012

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

Abstract: We generalize a result from Volkov [Ann. Probab. 29 (2001) 66--91] and prove that, on a large class of locally finite connected graphs of bounded degree $(G,sim)$ and symmetric reinforcement matrices $a=(a_{i,j}{)}_{i,jinG}$, the vertex-reinforced random walk (VRRW) eventually localizes with positive probability on subsets which consist of a complete $d$-partite subgraph with possible loops plus its outer boundary. We first show that, in general, any stable equilibrium of a linear symmetric replicator dynamics with positive payoffs on a graph $G$ satisfies the property that its support is a complete $d$-partite subgraph of $G$ with possible loops, for some $dge1$. This result is used here for the study of VRRWs, but also applies to other contexts such as evolutionary models in population genetics and game theory. Next we generalize the result of Pemantle [Probab. Theory Related Fields 92 (1992) 117--136] and Bena"{{i}}m [Ann. Probab. 25 (1997) 361--392] relating the asymptotic behavior of the VRRW to replicator dynamics. This enables us to conclude that, given any neighborhood of a strictly stable equilibrium with support $S$, the following event occurs with positive probability: the walk localizes on $ScuppartialS$ (where $partialS$ is the outer boundary of $S$) and the density of occupation of the VRRW converges, with polynomial rate, to a strictly stable equilibrium in this neighborhood.

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

zbMATH Keywords

replicator dynamicsreinforced random walkslocalization propertyrandom perturbations of dynamical systems

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Sums of independent random variables; random walks (60G50) Ordinary differential equations and systems with randomness (34F05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Phase transition in reinforced random walk and RWRE on trees
• Vertex-reinforced random walks and a conjecture of Pemantle
• Vertex-reinforced random walk on \(\mathbb Z\) has finite range
• Vertex-reinforced random walk on \(\mathbb Z\) eventually gets stuck on five points.
• A survey of random processes with reinforcement
• Dynamics of games and genes: Discrete versus continuous time
• On the number of local maxima of a constrained quadratic form
• An asymptotic result for Brownian polymers
• Vertex-reinforced random walk
• Phase transition in vertex-reinforced random walks on \({\mathbb{Z}}\) with nonlinear reinforcement
• Vertex-reinforced random walk on arbitrary graphs
• Linearly edge-reinforced random walks
• VRRW on complete-like graphs: almost sure behavior
• Théorèmes de convergence presque sure pour une classe d'algorithmes stochastiques à pas decroissant
• Attracting edge and strongly edge reinforced walks

Cited In (14)

• Pattern formation in auxin flux
• Vertex reinforced non-backtracking random walks: an example of path formation
• Convergence of vertex-reinforced jump processes to an extension of the supersymmetric hyperbolic nonlinear sigma model
• Vertex reinforced random walks with exponential interaction on complete graphs
• Lyapunov function for interacting reinforced stochastic processes via Hopfield's energy function
• Localization on 5 sites for vertex reinforced random walks: towards a characterization
• Vertex-reinforced random walks and a conjecture of Pemantle
• VRRW on complete-like graphs: almost sure behavior
• Preferential duplication graphs
• Localization of a vertex reinforced random walk on \(\mathbb Z\) with sub-linear weight
• Vertex-reinforced random walk
• Localization on 4 sites for vertex-reinforced random walks on \(\mathbb{Z}\)
• Ant foraging and geodesic paths in labyrinths: analytical and computational results
• Vertex-reinforced random walk on arbitrary graphs

Recommendations

• Localization of a vertex reinforced random walk on \(\mathbb Z\) with sub-linear weight 👍 👎
• Localization on 4 sites for vertex-reinforced random walks on \(\mathbb{Z}\) 👍 👎
• Strongly vertex-reinforced-random-walk on a complete graph 👍 👎
• Vertex-reinforced random walk on arbitrary graphs 👍 👎
• VRRW on complete-like graphs: almost sure behavior 👍 👎
• Vertex reinforced non-backtracking random walks: an example of path formation 👍 👎
• Vertex reinforced random walks with exponential interaction on complete graphs 👍 👎
• Attraction time for strongly reinforced walks 👍 👎

This page was built for publication: Dynamics of vertex-reinforced random walks

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