Linear cover time is exponentially unlikely

2021/09/02 by Quentin Dubroff, Jeff Kahn, Dubroff, Quentin +1
Computer Science · Mathematics · #05C81 #60J05 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2109.01237

openalex publication_date 2021/09/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Proving a 2009 conjecture of Itai Benjamini, we show: For any C there is an ε>0 such that for any simple graph G on V of size n, and X₀,… an ordinary random walk on G, P(\X₀,…, X_Cn\= V) < e^{-ε n}. A first ingredient in the proof of this is a similar statement for Markov chains in which all transition probabilities are sufficiently small relative to C.

Related

• Linear Cover Time is Exponentially Unlikely
• On the universality of fluctuations for the cover time
• Cover times and generic chaining
• The Cover Time of Random Walks on Graphs
• The cover time, the blanket time, and the Matthews bound