Linear cover time is exponentially unlikely

DOI10.1214/24-AOP1699MaRDI QIDQ6670804FDOQ6670804

Quentin Dubroff, J. Kahn

Publication date: 24 January 2025

Published in: The Annals of Probability (Search for Journal in Brave)

zbMATH Keywords

Markov chainscover timerandom walks on graphs

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Discrete-time Markov processes on general state spaces (60J05) Random walks on graphs (05C81)

Cites Work

• Lower bounds for covering times for reversible Markov chains and random walks on graphs
• Cover times, blanket times, and majorizing measures
• A Chernoff Bound for Random Walks on Expander Graphs
• Asymptotics of cover times via Gaussian free fields: bounded-degree graphs and general trees
• Asymptotically good list-colorings
• Exponential concentration of cover times
• Linear cover time is exponentially unlikely
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: Linear cover time is exponentially unlikely

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6670804)