Proving a 2009 conjecture of Itai Benjamini, we show: For any C there is an $\varepsilon>0$ such that for any simple graph $G$ on $V$ of size $n$, and $X_0,\ldots$ an ordinary random walk on $G$, $P(\{ X_0,\dots, X_{ Cn}\}= V) < e^{ -\varepsilon 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$.
Categories: math.PR math.CO