Advanced

VRRW on complete-like graphs: almost sure behavior

Limic, Vlada and Volkov, Stanislav LU (2010) In Annals of Applied Probability 20(6). p.2346-2388
Abstract
By a theorem of Volkov [12] we know that on most graphs with positive probability the linearly vertex-reinforced random walk (VRRW) stays within a finite “trapping” subgraph at all large times. The question of whether this tail behavior occurs with probability one is open in general. In his thesis, Pemantle [5] proved, via a dynamical system approach, that for a VRRW on any complete graph the asymptotic frequency of visits is uniform over vertices. These techniques do not easily extend even to the setting of complete-like graphs, that is, complete graphs ornamented with finitely many leaves at each vertex. In this work we combine martingale and large deviation techniques to prove that almost surely the VRRW on any such graph spends... (More)
By a theorem of Volkov [12] we know that on most graphs with positive probability the linearly vertex-reinforced random walk (VRRW) stays within a finite “trapping” subgraph at all large times. The question of whether this tail behavior occurs with probability one is open in general. In his thesis, Pemantle [5] proved, via a dynamical system approach, that for a VRRW on any complete graph the asymptotic frequency of visits is uniform over vertices. These techniques do not easily extend even to the setting of complete-like graphs, that is, complete graphs ornamented with finitely many leaves at each vertex. In this work we combine martingale and large deviation techniques to prove that almost surely the VRRW on any such graph spends positive (and equal) proportions of time on each of its nonleaf vertices. This behavior was previously shown to occur only up to event of positive probability (cf. Volkov [12]). We believe that our approach can be used as a building block in studying related questions on more general graphs. The same set of techniques is used to obtain explicit bounds on the speed of convergence of the empirical occupation measure. (Less)
Please use this url to cite or link to this publication:
author
publishing date
type
Contribution to journal
publication status
published
subject
in
Annals of Applied Probability
volume
20
issue
6
pages
2346 - 2388
publisher
Institute of Mathematical Statistics
external identifiers
  • scopus:78650467185
ISSN
1050-5164
DOI
10.1214/10-AAP687
language
English
LU publication?
no
id
f31a3fe7-5870-4689-bde7-a45dca11948f (old id 4359868)
alternative location
http://projecteuclid.org/euclid.aoap/1287494563
date added to LUP
2014-03-17 14:57:19
date last changed
2018-05-29 10:40:48
@article{f31a3fe7-5870-4689-bde7-a45dca11948f,
  abstract     = {By a theorem of Volkov [12] we know that on most graphs with positive probability the linearly vertex-reinforced random walk (VRRW) stays within a finite “trapping” subgraph at all large times. The question of whether this tail behavior occurs with probability one is open in general. In his thesis, Pemantle [5] proved, via a dynamical system approach, that for a VRRW on any complete graph the asymptotic frequency of visits is uniform over vertices. These techniques do not easily extend even to the setting of complete-like graphs, that is, complete graphs ornamented with finitely many leaves at each vertex. In this work we combine martingale and large deviation techniques to prove that almost surely the VRRW on any such graph spends positive (and equal) proportions of time on each of its nonleaf vertices. This behavior was previously shown to occur only up to event of positive probability (cf. Volkov [12]). We believe that our approach can be used as a building block in studying related questions on more general graphs. The same set of techniques is used to obtain explicit bounds on the speed of convergence of the empirical occupation measure.},
  author       = {Limic, Vlada and Volkov, Stanislav},
  issn         = {1050-5164},
  language     = {eng},
  number       = {6},
  pages        = {2346--2388},
  publisher    = {Institute of Mathematical Statistics},
  series       = {Annals of Applied Probability},
  title        = {VRRW on complete-like graphs: almost sure behavior},
  url          = {http://dx.doi.org/10.1214/10-AAP687},
  volume       = {20},
  year         = {2010},
}