Attraction time for strongly reinforced walks

DOI10.1214/08-AAP564zbMATH Open1213.60087arXivmath/0612048MaRDI QIDQ983889FDOQ983889

Authors: Codina Cotar, Vlada Limic 

Publication date: 13 July 2010

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

Abstract: We consider a class of strongly edge-reinforced random walks, where the corresponding reinforcement weight function is nondecreasing. It is known, from Limic and Tarr`{e}s [Ann. Probab. (2007), to appear], that the attracting edge emerges with probability 1 whenever the underlying graph is locally bounded. We study the asymptotic behavior of the tail distribution of the (random) time of attraction. In particular, we obtain exact (up to a multiplicative constant) asymptotics if the underlying graph has two edges. Next, we show some extensions in the setting of finite graphs, and infinite graphs with bounded degree. As a corollary, we obtain the fact that if the reinforcement weight has the form $w(k)=k^{ho}$, $ho>1$, then (universally over finite graphs) the expected time to attraction is infinite if and only if $holeq1+frac1+sqrt52$.

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

Recommendations

• Attracting edge property for a class of reinforced random walks
• Bounding a random environment bounding a random environment for two-dimensional edge-reinforced random walk
• Edge-reinforced random walk on finite graphs
• A random environment for linearly edge-reinforced random walks on infinite graphs
• Vertex-reinforced random walk on arbitrary graphs
• Phase transition in vertex-reinforced random walks on \({\mathbb{Z}}\) with nonlinear reinforcement
• Localization for linearly edge reinforced random walks
• Tubular recurrence
• Recurrence of edge-reinforced random walk on a two-dimensional graph

zbMATH Keywords

attracting edgereinforced walkstrong reinforcementtime of attraction

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)

Cites Work

• Title not available (Why is that?)
• Phase transition in reinforced random walk and RWRE on trees
• Reinforced random walk
• Reinforced random walk on the \(d\)-dimensional integer lattice
• A survey of random processes with reinforcement
• Edge-reinforced random walk on a ladder
• Attracting edge and strongly edge reinforced walks
• Attracting edge property for a class of reinforced random walks
• Connectivity Transitions in Networks with Super-Linear Preferential Attachment

Cited In (12)

• Large deviations for generalized Polya urns with arbitrary urn function
• Edge-attractor random walks on dynamic networks
• Attracting edge and strongly edge reinforced walks
• Asymptotics of generalized Pólya urns with non-linear feedback
• Edge- and vertex-reinforced random walks with super-linear reinforcement on infinite graphs
• On a preferential attachment and generalized Pólya's urn model
• Dynamics of vertex-reinforced random walks
• Attracting edge property for a class of reinforced random walks
• Infinite WARM graphs III: strong reinforcement regime
• By force of habit: self-trapping in a dynamical utility landscape
• Linear de-preferential urn models
• What is the difference between a square and a triangle?

This page was built for publication: Attraction time for strongly reinforced walks

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