The cover time, the blanket time, and the Matthews bound

Simple item page
dc.creatorKahn, J.
dc.creatorKim, J. H.
dc.creatorLovasz, L.
dc.creatorVu, V. H.
dc.date2000-05-12
dc.date.accessioned2026-07-07T04:35:13Z
dc.date.available2026-07-07T04:35:13Z
dc.descriptionThe cover time C of a graph G is the expected time for a random walk starting from the worst vertex to cover all vertices in G. Similarly, the blanket time B is the expected time to visit all vertices within a constant factor of number of times suggested by the stationary distribution. (Our definition will be slightly stronger than this.) Obviously, all vertices are covered when the graph is blanketed, and hence C <= B. The blanket time is introduced by Winkler and Zuckerman motivated by applications in Markov estimation and distributed computing. They conjectured B =O(C) and proved B=O(C ln n ). In this paper, we introduce another parameter M motivated by Matthews' theorem and prove M/2 <= C <= B = O(( M ln ln n)^2). In particular, B = O(C (ln ln n)^2). The lower bound is still valid for the cover time C(π) starting from the stationary distribution. We also show that there is a polynomial time algorithm to approximate M within a factor of 2 and so does for C within a factor of O((ln ln n)^2), improving previous bound of O(ln n) of Matthews'.
dc.description9 page article on random walks
dc.identifierhttps://arxiv.org/abs/math/0005121
dc.identifierhttp://arxiv.org/abs/math/0005121
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/59180
dc.subjectProbability
dc.subjectCombinatorics
dc.titleThe cover time, the blanket time, and the Matthews bound
dc.typetext

Files

Collections

arXiv