Cover time

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]

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