Advanced

Edge-and vertex-reinforced random walks with super-linear reinforcement on infinite graphs

Cotar, Codina and Thacker, Debleena LU (2017) In Annals of Probability 45(4). p.2655-2706
Abstract

In this paper, we introduce a new simple but powerful general technique for the study of edge- and vertex-reinforced processes with super-linear reinforcement, based on the use of order statistics for the number of edge, respectively of vertex, traversals. The technique relies on upper bound estimates for the number of edge traversals, proved in a different context by Cotar and Limic [Ann. Appl. Probab. 19 (2009) 1972-2007] for finite graphs with edge reinforcement. We apply our new method both to edge- and to vertex-reinforced random walks with super-linear reinforcement on arbitrary infinite connected graphs of bounded degree. We stress that, unlike all previous results for processes with super-linear reinforcement, we make no other... (More)

In this paper, we introduce a new simple but powerful general technique for the study of edge- and vertex-reinforced processes with super-linear reinforcement, based on the use of order statistics for the number of edge, respectively of vertex, traversals. The technique relies on upper bound estimates for the number of edge traversals, proved in a different context by Cotar and Limic [Ann. Appl. Probab. 19 (2009) 1972-2007] for finite graphs with edge reinforcement. We apply our new method both to edge- and to vertex-reinforced random walks with super-linear reinforcement on arbitrary infinite connected graphs of bounded degree. We stress that, unlike all previous results for processes with super-linear reinforcement, we make no other assumption on the graphs. For edge-reinforced random walks, we complete the results of Limic and Tarrès [Ann. Probab. 35 (2007) 1783-1806] and we settle a conjecture of Sellke (1994) by showing that for any reciprocally summable reinforcement weight function w, the walk traverses a random attracting edge at all large times. For vertex-reinforced random walks, we extend results previously obtained on Z by Volkov [Ann. Probab. 29 (2001) 66-91] and by Basdevant, Schapira and Singh [Ann. Probab. 42 (2014) 527-558], and on complete graphs by Benaim, Raimond and Schapira [ALEA Lat. Am. J. Probab. Math. Stat. 10 (2013) 767-782]. We show that on any infinite connected graph of bounded degree, with reinforcement weight function w taken from a general class of reciprocally summable reinforcement weight functions, the walk traverses two random neighbouring attracting vertices at all large times.

(Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Attraction set, Bipartite graphs, Edge-reinforced random walk, Order statistics, Rubin's construction, Superlinear (strong) reinforcement, Vertex-reinforced random walk
in
Annals of Probability
volume
45
issue
4
pages
52 pages
publisher
Institute of Mathematical Statistics
external identifiers
  • scopus:85027372445
  • wos:000408599200016
ISSN
0091-1798
DOI
10.1214/16-AOP1122
language
English
LU publication?
yes
id
3f6f7614-971f-469f-82dd-75eb86ebeb9f
date added to LUP
2017-08-31 14:57:13
date last changed
2017-09-18 11:43:48
@article{3f6f7614-971f-469f-82dd-75eb86ebeb9f,
  abstract     = {<p>In this paper, we introduce a new simple but powerful general technique for the study of edge- and vertex-reinforced processes with super-linear reinforcement, based on the use of order statistics for the number of edge, respectively of vertex, traversals. The technique relies on upper bound estimates for the number of edge traversals, proved in a different context by Cotar and Limic [Ann. Appl. Probab. 19 (2009) 1972-2007] for finite graphs with edge reinforcement. We apply our new method both to edge- and to vertex-reinforced random walks with super-linear reinforcement on arbitrary infinite connected graphs of bounded degree. We stress that, unlike all previous results for processes with super-linear reinforcement, we make no other assumption on the graphs. For edge-reinforced random walks, we complete the results of Limic and Tarrès [Ann. Probab. 35 (2007) 1783-1806] and we settle a conjecture of Sellke (1994) by showing that for any reciprocally summable reinforcement weight function w, the walk traverses a random attracting edge at all large times. For vertex-reinforced random walks, we extend results previously obtained on Z by Volkov [Ann. Probab. 29 (2001) 66-91] and by Basdevant, Schapira and Singh [Ann. Probab. 42 (2014) 527-558], and on complete graphs by Benaim, Raimond and Schapira [ALEA Lat. Am. J. Probab. Math. Stat. 10 (2013) 767-782]. We show that on any infinite connected graph of bounded degree, with reinforcement weight function w taken from a general class of reciprocally summable reinforcement weight functions, the walk traverses two random neighbouring attracting vertices at all large times.</p>},
  author       = {Cotar, Codina and Thacker, Debleena},
  issn         = {0091-1798},
  keyword      = {Attraction set,Bipartite graphs,Edge-reinforced random walk,Order statistics,Rubin's construction,Superlinear (strong) reinforcement,Vertex-reinforced random walk},
  language     = {eng},
  month        = {07},
  number       = {4},
  pages        = {2655--2706},
  publisher    = {Institute of Mathematical Statistics},
  series       = {Annals of Probability},
  title        = {Edge-and vertex-reinforced random walks with super-linear reinforcement on infinite graphs},
  url          = {http://dx.doi.org/10.1214/16-AOP1122},
  volume       = {45},
  year         = {2017},
}