Cover time

Short description: Time to reach all states of a Markov chain

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.

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.

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 $K_n$ is $n\ln n(1+o(1))$. For every other $n$-vertex graph, the expected cover time is at least as large as this formula. Any $n$-vertex regular expander graph also has expected cover time $\mathrm{\Theta }(n\log n)$ from any starting vertex, and more generally the cover time of any regular graph is $$O\left(\frac{n\log n}{1-{\lambda }_2}\right),$$ where ${\lambda }_2$ is the second-largest eigenvalue of the graph, normalized so that the largest eigenvalue is one. For arbitrary $n$-vertex graphs, from any starting vertex, the cover time is at most $$(\frac{4}{27}+o(1))n^3,$$ and there exist graphs whose expected cover time is this large. In planar graphs, the expected cover time is $\mathrm{\Omega }(n{\log }^{2}n)$ and $O(n^2)$.

See also

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