Linear cover time is exponentially unlikely

Abstract: Proving a 2009 conjecture of Itai Benjamini, we show:

For any $C$ there is $c > 0$ so that for any simple random walk on an $n$-vertex graph $G$, the probability that the first $Cn$ steps of the walk see every vertex is less than $\exp[-cn]$.

A first ingredient in the proof of this is a similar statement for Markov chains in which all transition probabilities are less than a suitable function of $C$.

Joint with Quentin Dubroff.

mathematical physicsprobability

Audience: researchers in the topic

---

Probability and the City Seminar

Series comments: The Probability and the City Seminar is organized jointly by the probability groups of Columbia University and New York University.

Video recordings of talks are posted online at www.youtube.com/channel/UC0CXjG-ZSIZHy0S40Px2FEQ .

---