For a simple (unbiased) random walk on a connected graph with @math vertices, the cover time (the expected number of steps it takes to visit all vertices) is at most @math . We consider locally biased random walks, in which the probability of traversing an edge depends on the degrees of its endpoints. We confirm a conjecture of Abdullah, Cooper and Draief [2015] that the min-degree local bias rule ensures a cover time of @math . For this we formulate and prove the following lemma about spanning trees. Let @math denote for edge @math the minimum degree among its two endpoints. We say that a weight function @math for the edges is feasible if it is nonnegative, dominated by @math (for every edge @math ) and the sum over all edges of the ratios @math equals @math . For example, in trees @math , and in regular graphs the sum of edge weights is @math . Lemma: for every feasible @math , the minimum weight spanning tree has total weight @math . For regular graphs, a similar lemma was proved by Kahn, Linial, Nisan and Saks [1989].
For simple random walks, the range of possible values of the cover time is well understood. Aleliunas al @cite_0 showed that for any connected graph, @math . That work also introduced the spanning tree argument that is used also in establishing other upper bounds cited below, and in fact provides upper bounds on @math and not just on @math . For regular graphs the upper bound can be improved to @math , as shown by Kahn al in @cite_10 . A more refined connection between regularity and cyclic cover time was provided by Coppersmith al @cite_8 who proved that for any connected graph @math ,
@cite_0 @cite_10 @cite_8
2084768526 2091147489 1564693713 1971599265
This article deals with random walks on arbitrary graphs. We consider the cover time of finite graphs. That is, we study the expected time needed for a random walk on a finite graph to visit every vertex at least once. We establish an upper bound ofO(n2) for the expectation of the cover time for regular (or nearly regular) graphs. We prove a lower bound of Ω(n logn) for the expected cover time for trees. We present examples showing all our bounds to be tight. For an undirected graph and an optimal cyclic list of all its vertices, the cyclic cover time is the expected time it takes a simple random walk to travel from vertex to vertex along the list until it completes a full cycle. The main result of this paper is a characterization of the cyclic cover time in terms of simple and easy-to-compute graph properties. Namely, for any connected graph, the cyclic cover time is @math , where @math is the number of vertices in the graph, @math is the average degree of its vertices, and @math is the average of the inverse of the degree of its vertices. Other results obtained in the processes of proving the main theorem are a similar characterization of minimum resistance spanning trees of graphs, improved bounds on the cover time of graphs, and a simplified proof that the maximum commute time in any connected graph is at most @math . We study the cover time of multiple random walks. Given a graph G of n vertices, assume that k independent random walks start from the same vertex. The parameter of interest is the speed-up defined as the ratio between the cover time of one and the cover time of k random walks. Recently developed several bounds that are based on the quotient between the cover time and maximum hitting times. Their technique gives a speed-up of *** (k ) on many graphs, however, for many graph classes, k has to be bounded by @math . They also conjectured that, for any 1 ≤ k ≤ n , the speed-up is at most @math on any graph. As our main results, we prove the following: We present a new lower bound on the speed-up that depends on the mixing-time. It gives a speed-up of *** (k ) on many graphs, even if k is as large as n . We prove that the speed-up is @math on any graph. Under rather mild conditions, we can also improve this bound to @math , matching exactly the conjecture of We find the correct order of the speed-up for any value of 1 ≤ k ≤ n on hypercubes, random graphs and expanders. For d -dimensional torus graphs (d > 2), our bounds are tight up to a factor of @math . Our findings also reveal a surprisingly sharp dichotomy on several graphs (including d -dim. torus and hypercubes): up to a certain threshold the speed-up is k , while there is no additional speed-up above the threshold. Abstract For simple random walk on a finite tree, the cover time is the time taken to visit every vertex. For the balanced b-ary tree of height m, the cover time is shown to be asymptotic to 2m 2 b m + 1 ( log b) (b − 1) as m → ∞ . On the uniform random labeled tree on n vertices, we give a convincing heuristic argument that the mean time to cover and return to the root is asymptotic to 6(2π) 1 2 n 3 2 , and prove a weak O(n 3 2 ) upper bound. The argument rests upon a recursive formula for cover time of trees generated by a simple branching process.