Dynamics of vertex-reinforced random walks

Details Dynamics of vertex-reinforced random walks Dynamics of vertex-reinforced random walks

2008-09-16

arxiv.org/abs/0809.2739v4

Annals of Probability 2011, Vol. 39, No. 6, 2178-2223

Mathematics

Probability

Published in at http://dx.doi.org/10.1214/10-AOP609 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of

Scientific paper

10.1214/10-AOP609

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,j\in G}$, 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 $d\ge1$. 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 $S\cup\partial S$ (where $\partial S$ 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.

Affiliated with

Also associated with

No associations

Rating

Dynamics of vertex-reinforced random walks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Dynamics of vertex-reinforced random walks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamics of vertex-reinforced random walks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-570971