Dynamics of vertex-reinforced random walks

DOI10.1214/10-AOP609MaRDI QIDQ653301zbMATH OpenFDO

Authors Michel Benaïm, Pierre Tarrès

Publication date 9 January 2012

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

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)

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.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 1069282 (Why is no real title available?)
• scientific article; zbMATH DE number 1444754 (Why is no real title available?)
• scientific article; zbMATH DE number 1444762 (Why is no real title available?)
• A survey of random processes with reinforcement
• An asymptotic result for Brownian polymers
• Attracting edge and strongly edge reinforced walks
• Dynamics of games and genes: Discrete versus continuous time
• Linearly edge-reinforced random walks
• On the number of local maxima of a constrained quadratic form
• Phase transition in reinforced random walk and RWRE on trees
• Phase transition in vertex-reinforced random walks on \({\mathbb{Z}}\) with nonlinear reinforcement
• Théorèmes de convergence presque sure pour une classe d'algorithmes stochastiques à pas decroissant
• VRRW on complete-like graphs: almost sure behavior
• Vertex-reinforced random walk
• 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
• Vertex-reinforced random walks and a conjecture of Pemantle

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
• Vertex-reinforced random walk
• Preferential duplication graphs
• 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}\)
• Ant foraging and geodesic paths in labyrinths: analytical and computational results
• Vertex-reinforced random walk on arbitrary graphs

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)