We prove that for a sequence of finite vertex-transitive graphs of increasing sizes, the cover times are asymptotically concentrated iff the product of the spectral-gap and the expected cover time diverges. In fact, we prove this for general reversible Markov chains under the much weaker assumptions (than transitivity) that the maximal hitting time of a state is comparable to the average hitting time of a state and that the maximal stationary probability of a state vanishes.
Cover times have been studied extensively for over 35 years. This is a topic with rich ties to other objects such as the Gaussian free field @cite_22 . There has been many works providing general bounds on the cover time, studying its evolution and its fluctuations in general @cite_3 @cite_26 @cite_7 @cite_10 @cite_5 , and in particular for the giant component of various random graphs @cite_16 , for trees @cite_20 @cite_1 , for the two dimensional torus @cite_24 @cite_23 @cite_8 @cite_13 and for higher dimensional tori @cite_0 . Feige @cite_18 @cite_12 proved tight extremal upper and lower bounds on cover times of graphs (by SRW). For a more comprehensive review of the literature see the related work section in @cite_22 and the references therein. For background on mixing, hitting times and cover times see @cite_21 @cite_19 .
@cite_13 @cite_18 @cite_26 @cite_22 @cite_7 @cite_8 @cite_21 @cite_1 @cite_3 @cite_24 @cite_0 @cite_19 @cite_23 @cite_5 @cite_16 @cite_10 @cite_12 @cite_20
2257118316 2170807097 1979312416 2019415463 2033953301 2099322621 2615822388 2001123643 2963180417 2120076230 1987243055 1600293573 2114344097 2136645553 1984070713 2057596055 1971599265
The ( )-cover time of the two dimensional torus by Brownian motion is the time it takes for the process to come within distance ( >0 ) from any point. Its leading order in the small ( )-regime has been established by (Ann Math 160:433–464, 2004). In this work, the second order correction is identified. The approach relies on a multi-scale refinement of the second moment method, and draws on ideas from the study of the extremes of branching Brownian motion. 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. In this paper we show that on bounded degree graphs and general trees, the cover time of the simple random walk is asymptotically equal to the product of the number of edges and the square of the expected supremum of the Gaussian free field on the graph, assuming that the maximal hitting time is significantly smaller than the cover time. Previously, this was only proved for regular trees and the 2D lattice. Furthermore, for general trees, we derive exponential concentration for the cover time, which implies that the standard deviation of the cover time is bounded by the geometric mean of the cover time and the maximal hitting time. We show that the measure on markings of Znd, d ≥ 3, with elements of 0, 1 given by i.i.d. fair coin flips on the range @math of a random walk X run until time T and 0 otherwise becomes indistinguishable from the uniform measure on such markings at the threshold T = ½Tcov(Znd). As a consequence of our methods, we show that the total variation mixing time of the random walk on the lamplighter graph Z2 ≀ Znd, d ≥ 3, has a cutoff with threshold ½Tcov(Znd). We give a general criterion under which both of these results hold; other examples for which this applies include bounded degree expander families, the intersection of an infinite supercritical percolation cluster with an increasing family of balls, the hypercube and the Caley graph of the symmetric group generated by transpositions. The proof also yields precise asymptotics for the decay of correlation in the uncovered set. Let @math be the cover time of two-dimensional discrete torus @math . We prove that @math for @math . One of the main methods used in the proofs is the decoupling of the walker's trace into independent excursions by means of soft local times. A sequence of Markov chains is said to exhibit (total variation) cutoff if the convergence to stationarity in total variation distance is abrupt. We consider reversible lazy chains. We prove a necessary and sufficient condition for the occurrence of the cutoff phenomena in terms of concentration of hitting time of “worst” (in some sense) sets of stationary measure at least αα, for some α∈(0,1)α∈(0,1). We also give general bounds on the total variation distance of a reversible chain at time tt in terms of the probability that some “worst” set of stationary measure at least αα was not hit by time tt. As an application of our techniques, we show that a sequence of lazy Markov chains on finite trees exhibits a cutoff iff the product of their spectral gaps and their (lazy) mixing-times tends to ∞∞. We compute the second order correction for the cover time of the binary tree of depth n by (continuous-time) random walk, and show that with probability approaching 1 as n increases, τcov=|E|[2log2⋅n−logn 2log2+O((loglogn)8)], thus showing that the second order correction differs from the corresponding one for the maximum of the Gaussian free field on the tree. LetT (x;") denote the rst hitting time of the disc of radius " centered at x for Brownian motion on the two dimensional torus T 2 . We prove that sup x2T2T (x;")=j log"j 2 ! 2= as " ! 0. The same applies to Brownian motion on any smooth, compact connected, two- dimensional, Riemannian manifold with unit area and no boundary. As a consequence, we prove a conjecture, due to Aldous (1989), that the number of steps it takes a simple random walk to cover all points of the lattice torus Z 2 is asymptotic to 4n 2 (logn) 2 = . Determining these asymptotics is an essential step toward analyzing the fractal structure of the set of uncovered sites before coverage is complete; so far, this structure was only studied non-rigorously in the physics literature. We also establish a conjecture, due to Kesten and R ev esz, that describes the asymptotics for the number of steps needed by simple random walk in Z 2 to cover the disc of radius n. This work proves that the fluctuations of the cover time of simple random walk in the discrete torus of dimension at least three with large side-length are governed by the Gumbel extreme value distribution. This result was conjectured for example in Aldous and Fill (Reversible Markov chains and random walks on graphs, in preparation). We also derive some corollaries which qualitatively describe “how” covering happens. In addition, we develop a new and stronger coupling of the model of random interlacements, introduced by Sznitman (Ann Math (2) 171(3):2039–2087, 2010), and random walk in the torus. This coupling is used to prove the cover time result and is also of independent interest. This book is an introduction to the modern approach to the theory of Markov chains. The main goal of this approach is to determine the rate of convergence of a Markov chain to the stationary distribution as a function of the size and geometry of the state space. The authors develop the key tools for estimating convergence times, including coupling, strong stationary times, and spectral methods. Whenever possible, probabilistic methods are emphasized. The book includes many examples and provides brief introductions to some central models of statistical mechanics. Also provided are accounts of random walks on networks, including hitting and cover times, and analyses of several methods of shuffling cards. As a prerequisite, the authors assume a modest understanding of probability theory and linear algebra at an undergraduate level. ""Markov Chains and Mixing Times"" is meant to bring the excitement of this active area of research to a wide audience. We study the cover time @math by (continuous-time) random walk on the 2D box of side length @math with wired boundary or on the 2D torus,and show that in both cases with probability approaching @math as @math increases, @math . This improves a result of Dembo, Peres, Rosen, and Zeitouni (2004) and makes progresstowards a conjecture of Bramson and Zeitouni (2009). 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 ). We study the cover time of a random walk on the largest component of the random graph Gn,p. We determine its value up to a factor 1 + o(1) whenever np = c > 1, c = O(lnn). In particular, we show that the cover time is not monotone for c = Θ(lnn). We also determine the cover time of the k-cores, k ≥ 2. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008 The cover time of a graph is a celebrated example of a parameter that is easy to approximate using a randomized algorithm, but for which no constant factor deterministic polynomial time approximation is known. A breakthrough due to Kahn, Kim, Lovasz and Vu [25] yielded a (log logn)2 polynomial time approximation. We refine the upper bound of [25], and show that the resulting bound is sharp and explicitly computable in random graphs. Cooper and Frieze showed that the cover time of the largest component of the Erdős–Renyi random graph G(n, c n) in the supercritical regime with c > 1 fixed, is asymptotic to ϕ(c)nlog2n, where ϕ(c) → 1 as c ↓ 1. However, our new bound implies that the cover time for the critical Erdős–Renyi random graph G(n, 1 n) has order n, and shows how the cover time evolves from the critical window to the supercritical phase. Our general estimate also yields the order of the cover time for a variety of other concrete graphs, including critical percolation clusters on the Hamming hypercube 0, 1 n, on high-girth expanders, and on tori ℤdn for fixed large d. This approach also gives a simpler proof of a result of Aldous [2] that the cover time of a uniform labelled tree on k vertices is of order k3 2. For the graphs we consider, our results show that the blanket time, introduced by Winkler and Zuckerman [45], is within a constant factor of the cover time. Finally, we prove that for any connected graph, adding an edge can increase the cover time by at most a factor of 4. 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.