DYNAMICS OF VERTEX-REINFORCED RANDOM WALKS
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, ~) and symmetric reinforcement matrices a = (a i,j ) i,j∈G, the vertex-reinforced random walk (VRRW) eventually localizes with positive probabil...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Published: |
2011
|
| _version_ | 1826281477236588544 |
|---|---|
| author | Benaim, M Tarres, P |
| author_facet | Benaim, M Tarres, P |
| author_sort | Benaim, M |
| collection | OXFORD |
| description | 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, ~) and symmetric reinforcement matrices a = (a i,j ) i,j∈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 ≥ 1. 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ï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 ∪ ∂ S (where ∂ 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. © 2011 Institute of Mathematical Statistics. |
| first_indexed | 2024-03-07T00:29:24Z |
| format | Journal article |
| id | oxford-uuid:7f3d9c6b-b463-4bcd-b201-b2ee62a7879f |
| institution | University of Oxford |
| last_indexed | 2024-03-07T00:29:24Z |
| publishDate | 2011 |
| record_format | dspace |
| spelling | oxford-uuid:7f3d9c6b-b463-4bcd-b201-b2ee62a7879f2022-03-26T21:15:35ZDYNAMICS OF VERTEX-REINFORCED RANDOM WALKSJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:7f3d9c6b-b463-4bcd-b201-b2ee62a7879fSymplectic Elements at Oxford2011Benaim, MTarres, PWe 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, ~) and symmetric reinforcement matrices a = (a i,j ) i,j∈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 ≥ 1. 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ï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 ∪ ∂ S (where ∂ 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. © 2011 Institute of Mathematical Statistics. |
| spellingShingle | Benaim, M Tarres, P DYNAMICS OF VERTEX-REINFORCED RANDOM WALKS |
| title | DYNAMICS OF VERTEX-REINFORCED RANDOM WALKS |
| title_full | DYNAMICS OF VERTEX-REINFORCED RANDOM WALKS |
| title_fullStr | DYNAMICS OF VERTEX-REINFORCED RANDOM WALKS |
| title_full_unstemmed | DYNAMICS OF VERTEX-REINFORCED RANDOM WALKS |
| title_short | DYNAMICS OF VERTEX-REINFORCED RANDOM WALKS |
| title_sort | dynamics of vertex reinforced random walks |
| work_keys_str_mv | AT benaimm dynamicsofvertexreinforcedrandomwalks AT tarresp dynamicsofvertexreinforcedrandomwalks |