Linear cover time is exponentially unlikely

DOI10.1214/24-AOP1699MaRDI QIDQ6670804zbMATH OpenFDO

Authors 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)

Recommendations

• Linear cover time is exponentially unlikely
• scientific article; zbMATH DE number 6292624
• Lower bounds for covering times for reversible Markov chains and random walks on graphs
• On the cover time of random walks on graphs
• The cover time of sparse random graphs

Cites work

• scientific article; zbMATH DE number 3493681 (Why is no real title available?)
• scientific article; zbMATH DE number 878897 (Why is no real title available?)
• scientific article; zbMATH DE number 6292624 (Why is no real title available?)
• A Chernoff Bound for Random Walks on Expander Graphs
• Asymptotically good list-colorings
• Asymptotics of cover times via Gaussian free fields: bounded-degree graphs and general trees
• Cover times, blanket times, and majorizing measures
• Exponential concentration of cover times
• Linear cover time is exponentially unlikely
• Lower bounds for covering times for reversible Markov chains and random walks on graphs
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.

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)