Mathematics – Probability
Scientific paper
2009-04-30
Annals of Applied Probability 2010, Vol. 20, No. 6, 2346-2388
Mathematics
Probability
Published in at http://dx.doi.org/10.1214/10-AAP687 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Inst
Scientific paper
10.1214/10-AAP687
By a theorem of Volkov (2001) 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 (1988) 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 (2001)). 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.
Limic Vlada
Volkov Stanislav
No associations
LandOfFree
VRRW on complete-like graphs: Almost sure behavior 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 VRRW on complete-like graphs: Almost sure behavior, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and VRRW on complete-like graphs: Almost sure behavior will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-442506