Linear cover time is exponentially unlikely

DOI10.1214/24-AOP1699MaRDI QIDQ6670804FDOQ6670804

Authors: Quentin Dubroff, J. Kahn 

Publication date: 24 January 2025

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

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

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

• Title not available (Why is that?)
• Lower bounds for covering times for reversible Markov chains and random walks on graphs
• Title not available (Why is that?)
• 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
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Exponential concentration of cover times
• Linear cover time is exponentially unlikely
• 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)