Exponential concentration of cover times
Author:
- Alex ZhaiAZAlex Zhai
Open Access
- 1 January 2018
- journal article
- research article
- Published by Institute of Mathematical Statistics in Electronic Journal of Probability
- Vol. 23 (none) , 1-22
Abstract
We prove an exponential concentration bound for cover times of general graphs in terms of the Gaussian free field, extending the work of Ding, Lee, and Peres [8] and Ding [7]. The estimate is asymptotically sharp as the ratio of hitting time to cover time goes to zero. The bounds are obtained by showing a stochastic domination in the generalized second Ray-Knight theorem, which was shown to imply exponential concentration of cover times by Ding in [7]. This stochastic domination result appeared earlier in a preprint of Lupu [22], but the connection to cover times was not mentioned.Keywords
All Related Versions
This publication has 31 references indexed in Scilit:
- Cover times, blanket times, and majorizing measuresAnnals of Mathematics, 2012
- Markov loops and renormalizationThe Annals of Probability, 2010
- A Ray-Knight theorem for symmetric Markov processesThe Annals of Probability, 2000
- Une version sans conditionnement du theoreme d’isomorphisme de Dynkin1995
- Sample Path Properties of the Local Times of Strongly Symmetric Markov Processes Via Gaussian ProcessesThe Annals of Probability, 1992
- Threshold limits for cover timesJournal of Theoretical Probability, 1991
- On the cover time of random walks on graphsJournal of Theoretical Probability, 1989
- Covering Problems for Markov ChainsThe Annals of Probability, 1988
- The random walk representation of classical spin systems and correlation inequalitiesCommunications in Mathematical Physics, 1982
- Random walks and a sojourn density process of Brownian motionTransactions of the American Mathematical Society, 1963