{{Short description|Time to reach all states of a Markov chain}} {{Use dmy dates|cs1-dates=ly|date=November 2025}} {{Use list-defined references|date=November 2025}} {{CS1 config|mode=cs2}}
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.{{r|bk}}
==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.{{r|bk}}
==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 <math>K_n</math> is <math>n\ln n(1+o(1))</math>. For every other <math>n</math>-vertex graph, the expected cover time is at least as large as this formula.{{r|lower}} Any <math>n</math>-vertex regular expander graph also has expected cover time <math>\Theta(n\log n)</math> from any starting vertex, and more generally the cover time of any regular graph is <math display=block>O\left(\frac{n\log n}{1-\lambda_2}\right),</math> where <math>\lambda_2</math> is the second-largest eigenvalue of the graph, normalized so that the largest eigenvalue is one.{{r|bk}} For arbitrary <math>n</math>-vertex graphs, from any starting vertex, the cover time is at most <math display=block>\left(\frac{4}{27}+o(1)\right)n^3,</math> and there exist graphs whose expected cover time is this large.{{r|upper}} In planar graphs, the expected cover time is <math>\Omega(n\log^2 n)</math> and <math>O(n^2)</math>.{{r|planar}}
==See also== *Hitting time, the number of steps until a set of states is first reached
==References== <references>
<ref name=bk>{{citation | last1 = Broder | first1 = Andrei Z. | author1-link = Andrei Broder | last2 = Karlin | first2 = Anna R. | author2-link = Anna Karlin | doi = 10.1007/BF01048273 | issue = 1 | journal = Journal of Theoretical Probability | mr = 981768 | pages = 101–120 | title = Bounds on the cover time | volume = 2 | year = 1989}}</ref>
<ref name=lower>{{citation | last = Feige | first = Uriel | doi = 10.1002/rsa.3240060406 | issue = 4 | journal = Random Structures & Algorithms | mr = 1368844 | pages = 433–438 | title = A tight lower bound on the cover time for random walks on graphs | volume = 6 | year = 1995}}</ref>
<ref name=planar>{{citation | last1 = Jonnason | first1 = Johan | last2 = Schramm | first2 = Oded | author2-link = Oded Schramm | doi = 10.1214/ECP.v5-1022 | journal = Electronic Communications in Probability | pages = 85–90 | title = On the cover time of planar graphs | url = https://scholar.archive.org/work/ob5qlkvmufdvtge3i7a5ldeode | volume = 5 | year = 2000| doi-access = free }}</ref>
<ref name=upper>{{citation | last = Feige | first = Uriel | author-link = Uriel Feige | doi = 10.1002/rsa.3240060106 | issue = 1 | journal = Random Structures & Algorithms | mr = 1368834 | pages = 51–54 | title = A tight upper bound on the cover time for random walks on graphs | volume = 6 | year = 1995}}</ref>
</references>
Category:Probability theory Category:Graph theory