TOPICS
Search

Cover Time


The cover time of a random walk on a finite connected graph is the first time by which every graph vertex has been visited (Aldous 1991). For a discrete-time random walk that chooses each adjacent vertex with equal probability, write tau_(cov)(G) for this random variable and t_(cov)(G)=max_(v)E_v[tau_(cov)(G)] for its largest expectation value over the starting graph vertex v.

Let T_n be the growing random recursive tree model in which attachment to a graph vertex with k children has weight 1+ak, where a>=0, or a=-1/d for an integer d>=2. For a random walk started at the root vertex, Angel et al. (2026) proved that

 (tau_(cov)(T_n))/(n(lnn)^2)->C(a),

in probability with respect to both the random tree and the random walk, where

 C(a)=(e^(1+2w)(1+2w))/((1+a)^2),

w=W(a/(2sqrt(e))), W(x) is the principal branch of the Lambert W-function, and ln is the natural logarithm. They also proved E[t_(cov)(T_n)]∼C(a)n(lnn)^2, with this expectation value taken over the tree. For uniform attachment, a=0 and C(0)=e.


See also

Markov Chain, Random Recursive Tree, Random Walk

Explore with Wolfram|Alpha

References

Aldous, D. J. "Random Walk Covering of Some Special Trees." J. Math. Anal. Appl. 157, 271-283, 1991. https://doi.org/10.1016/0022-247X(91)90149-T.Angel, O.; Goldschmidt, C.; and Michaeli, P. "Cover Times of Random Recursive Trees and Linear Preferential Attachment Trees." 13 Nov 2026. https://arxiv.org/abs/2611.18353v1.

Cite this as:

Weisstein, Eric W. "Cover Time." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CoverTime.html

Subject classifications