Exponential concentration of cover times
Author:
Preprint
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-Peres and Ding. 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. This stochastic domination result appeared earlier in a preprint of Lupu, but the connection to cover times was not mentioned.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Brownian motions on metric graphsJournal of Mathematical Physics, 2012
- Functionals of Brownian motion, localization and metric graphsJournal of Physics A: General Physics, 2005
- A Technique for Lower Bounding the Cover TimeSIAM Journal on Discrete Mathematics, 1992
- Random walk covering of some special treesJournal of Mathematical Analysis and Applications, 1991
- Threshold limits for cover timesJournal of Theoretical Probability, 1991
- On the cover time of random walks on graphsJournal of Theoretical Probability, 1989
- Gaussian and non-Gaussian random fields associated with Markov processesJournal of Functional Analysis, 1984
- The equivalence of diffusions on networks to Brownian motion1984
- The random walk representation of classical spin systems and correlation inequalitiesCommunications in Mathematical Physics, 1982
- Euclidean Quantum Field Theory. I. Equations for a Scalar ModelJournal of Mathematical Physics, 1966