Attraction time for strongly reinforced walks

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è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^{\rho }$, $\rho >1$, then (universally over finite graphs) the expected time to attraction is infinite if and only if $\rho \le 1+\frac{1+\sqrt{5}}{2}$.

Published in at http://dx.doi.org/10.1214/08-AAP564 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (3)

• A survey of random processes with reinforcement
• Attracting edge and strongly edge reinforced walks
• Edge-reinforced random walk on a ladder

Cited by in corpus (5)

• On a preferential attachment and generalized Pólya's urn model
• By Force of Habit: Self-Trapping in a Dynamical Utility Landscape
• Large deviations for Generalized Polya Urns with arbitrary urn function
• Pólya Urn Schemes with Infinitely Many Colors
• Asymptotics of generalized Pólya urns with non-linear feedback