Repository logo
 

A Spectral Characterization for Concentration of the Cover Time

Accepted version
Peer-reviewed

Type

Article

Change log

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

Volume Title

33

Publisher

Springer Science and Business Media LLC

Rights

All rights reserved
Sponsorship
Engineering and Physical Sciences Research Council (EP/L018896/1)
EPSRC grant EP/L018896/1