# Cover time

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Cover_time
> Markdown URL: https://mediated.wiki/source/Cover_time.md
> Source: https://en.wikipedia.org/wiki/Cover_time
> Source revision: 1337717635
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{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](/source/cover_time) of a finite [Markov chain](/source/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](/source/random_variable) that depends on the Markov chain and the choice of the starting state. The cover time of a connected [undirected graph](/source/undirected_graph) is the cover time of the Markov chain that takes a [random walk](/source/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](/source/theoretical_computer_science) for applications involving the complexity of [st-connectivity](/source/st-connectivity), [algebraic graph theory](/source/algebraic_graph_theory) and the study of [expander graph](/source/expander_graph)s, and modeling [Token Ring](/source/Token_Ring) computer networking technology.{{r|bk}}

==In different classes of graphs==
A classical problem in [probability theory](/source/probability_theory), the [coupon collector's problem](/source/coupon_collector's_problem), can be interpreted as the result that the expected cover time of a [complete graph](/source/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](/source/regular_graph) 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](/source/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 graph](/source/planar_graph)s, the expected cover time is <math>\Omega(n\log^2 n)</math> and <math>O(n^2)</math>.{{r|planar}}

==See also==
*[Hitting time](/source/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](/source/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

---
Adapted from the Wikipedia article [Cover time](https://en.wikipedia.org/wiki/Cover_time) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Cover_time?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.