2010/11/13 by Itaï Benjamini, Benjamini, Itai, Ori Gurel-Gurevich +3
Computer Science · Mathematics · #05C81 #60J05 #Algorithms and Data Compression #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.1011.3118
openalex publication_date 2010/11/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that the probability that a simple random walk covers a finite, bounded degree graph in linear time is exponentially small. More precisely, for every D and C, there exists a=a(D,C)>0 such that for any graph G, with n vertices and maximal degree D, the probability that a simple random walk, started anywhere in G, will visit every vertex of G in its first Cn steps is at most exp(-an). We conjecture that the same holds for a=a(C)>0 that does not depend on D, provided that the graph G is simple.