We present a deterministic algorithm that given a tree T with n vertices, a starting vertex v and a slackness parameter epsilon > 0, estimates within an additive error of epsilon the cover and return time, namely, the expected time it takes a simple random walk that starts at v to visit all vertices of T and return to v. The running time of our algorithm is polynomial in n epsilon, and hence remains polynomial in n also for epsilon = 1 n^ O(1) . We also show how the algorithm can be extended to estimate the expected cover (without return) time on trees.
We prove upper and lower bounds and give an approximation algorithm for the cover time of the random walk on a graph. We introduce a parameter M motivated by the well-known Matthews bounds (P. Matthews, 1988) on the cover time, C, and prove that M 2<C= O(M(lnlnn) sup 2 ). We give a deterministic-polynomial time algorithm to approximate M within a factor of 2; this then approximates C within a factor of O((lnlnn) sup 2 ), improving the previous bound O(lnn) due to Matthews. The blanket time B was introduced by P. Winkler and D. Zuckerman (1996): it is the expectation of the first time when all vertices are visited within a constant factor of the number of times suggested by the stationary distribution. Obviously C spl les B. Winkler and Zuckerman conjectured B=O(C) and proved B=O(Clnn). Our bounds above are also valid for the blanket time, and so it follows that B=O(C(lnlnn) sup 2 ). On donne des bornes superieures et inferieures sur la fonction generatrice des moments du temps pris par une chaine de Markov pour visiter au moins n des N sous-ensembles selectionnes de son espace d'etats We prove that the expected time for a random walk to cover all n vertices of a graph is at least (1 + o(1))n In n. © 1995 Wiley Periodicals, Inc. 