A Spectral Characterization for Concentration of the Cover Time
Accepted version
Peer-reviewed
Repository URI
Repository DOI
Change log
Authors
Hermon, J https://orcid.org/0000-0002-2935-3999
Abstract
We prove that for a sequence of finite vertex-transitive graphs of increasing sizes, the cover times are asymptotically concentrated if and only if the product of the spectral-gap and the expected cover time diverges. In fact, we prove this for general reversible Markov chains under the much weaker assumption (than transitivity) that the maximal hitting time of a state is of the same order as the average hitting time.
Description
Keywords
Mixing times, Hitting times, Cover times, Vertex-transitive graphs, Spectral gap
Journal Title
Journal of Theoretical Probability
Conference Name
Journal ISSN
0894-9840
1572-9230
1572-9230
Volume Title
33
Publisher
Springer Science and Business Media LLC
Publisher DOI
Rights
All rights reserved
Sponsorship
Engineering and Physical Sciences Research Council (EP/L018896/1)
EPSRC grant EP/L018896/1