A Spectral Characterization for Concentration of the Cover Time

Jonathan Hermon ()
Additional contact information
Jonathan Hermon: University of Cambridge

Journal of Theoretical Probability, 2020, vol. 33, issue 4, 2167-2184

Abstract: 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.

Keywords: Mixing times; Hitting times; Cover times; Vertex-transitive graphs; Spectral gap; 60J10; 60J27 (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10959-019-00946-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jotpro:v:33:y:2020:i:4:d:10.1007_s10959-019-00946-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10959

DOI: 10.1007/s10959-019-00946-5

Access Statistics for this article

Journal of Theoretical Probability is currently edited by Andrea Monica

More articles in Journal of Theoretical Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().