Cover time

In mathematics, the cover time of a finite Markov chain is the number of steps taken by the chain, from a given starting state, until the first step at which all states have been reached. It is a random variable that depends on the Markov chain and the choice of the starting state. The cover time of a connected undirected graph is the cover time of the Markov chain that takes a random walk on the graph, at each step moving from one vertex to a uniformly-random neighbor of that vertex.^[1]

Applications

Cover times of graphs have been extensively studied in theoretical computer science for applications involving the complexity of st-connectivity, algebraic graph theory and the study of expander graphs, and modeling token ring computer networking technology.^[1]

In different classes of graphs

A classical problem in probability theory, the coupon collector's problem, can be interpreted as the result that the expected cover time of a complete graph ${\displaystyle K_{n}}$ is ${\displaystyle n\ln n(1+o(1))}$ . For every other ${\displaystyle n}$ -vertex graph, the expected cover time is at least as large as this formula.^[2] Any ${\displaystyle n}$ -vertex regular expander graph also has expected cover time ${\displaystyle \Theta (n\log n)}$ from any starting vertex, and more generally the cover time of any regular graph is $${\displaystyle O\left({\frac {n\log n}{1-\lambda _{2}}}\right),}$$ where ${\displaystyle \lambda _{2}}$ is the second-largest eigenvalue of the graph, normalized so that the largest eigenvalue is one.^[1] For arbitrary ${\displaystyle n}$ -vertex graphs, from any starting vertex, the cover time is at most $${\displaystyle \left({\frac {4}{27}}+o(1)\right)n^{3},}$$ and there exist graphs whose expected cover time is this large.^[3] In planar graphs, the expected cover time is ${\displaystyle \Omega (n\log ^{2}n)}$ and ${\displaystyle O(n^{2})}$ .^[4]

See also

• Hitting time, the number of steps until a set of states is first reached

References

1. Broder, Andrei Z.; Karlin, Anna R. (1989), "Bounds on the cover time", Journal of Theoretical Probability, 2 (1): 101–120, doi:10.1007/BF01048273, MR 0981768
2. Feige, Uriel (1995), "A tight lower bound on the cover time for random walks on graphs", Random Structures & Algorithms, 6 (4): 433–438, doi:10.1002/rsa.3240060406, MR 1368844
3. Feige, Uriel (1995), "A tight upper bound on the cover time for random walks on graphs", Random Structures & Algorithms, 6 (1): 51–54, doi:10.1002/rsa.3240060106, MR 1368834
4. Jonnason, Johan; Schramm, Oded (2000), "On the cover time of planar graphs", Electronic Communications in Probability, 5: 85–90, doi:10.1214/ECP.v5-1022