Attraction time for strongly reinforced walks

DOI10.1214/08-AAP564MaRDI QIDQ983889zbMATH OpenFDO

Authors Codina Cotar, Vlada Limic

Publication date 13 July 2010

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

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

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)

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$.

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

Cites work

• scientific article; zbMATH DE number 1480194 (Why is no real title available?)
• A survey of random processes with reinforcement
• 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
• Edge-reinforced random walk on a ladder
• Phase transition in reinforced random walk and RWRE on trees
• Reinforced random walk
• Reinforced random walk on the \(d\)-dimensional integer lattice

Cited in

(12)

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

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)