Mathematics – Probability
Scientific paper
2000-05-12
Mathematics
Probability
9 page article on random walks
Scientific paper
The 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(\pi) 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'.
Kahn Jeff
Kim Heon Jung
Lovasz Laszlo
Vu Van H.
No associations
LandOfFree
The cover time, the blanket time, and the Matthews bound does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The cover time, the blanket time, and the Matthews bound, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The cover time, the blanket time, and the Matthews bound will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-436874