VRRW on completelike graphs: almost sure behavior
(2010) In Annals of Applied Probability 20(6). p.23462388 Abstract
 By a theorem of Volkov [12] we know that on most graphs with positive probability the linearly vertexreinforced 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 completelike 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 vertexreinforced 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 completelike 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:
http://lup.lub.lu.se/record/4359868
 author
 Limic, Vlada and Volkov, Stanislav ^{LU}
 publishing date
 2010
 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
 10505164
 DOI
 10.1214/10AAP687
 language
 English
 LU publication?
 no
 id
 f31a3fe758704689bde7a45dca11948f (old id 4359868)
 alternative location
 http://projecteuclid.org/euclid.aoap/1287494563
 date added to LUP
 20140317 14:57:19
 date last changed
 20180107 04:04:15
@article{f31a3fe758704689bde7a45dca11948f, abstract = {By a theorem of Volkov [12] we know that on most graphs with positive probability the linearly vertexreinforced 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 completelike 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 = {10505164}, language = {eng}, number = {6}, pages = {23462388}, publisher = {Institute of Mathematical Statistics}, series = {Annals of Applied Probability}, title = {VRRW on completelike graphs: almost sure behavior}, url = {http://dx.doi.org/10.1214/10AAP687}, volume = {20}, year = {2010}, }