Lower bounds for covering times for reversible Markov chains and random walks on graphs
For simple random walk on an N-vertex graph the mean time to cover all vertices is at least cN log N where c is an absolute constant. This result is deduced from a more general result about a lower bound for the mean coverage time for stationary finite-state reversible Markov chains, starting with the stationary distribution.
scientific article; zbMATH DE number 4121162