Asymptotics of cover times via Gaussian free fields: Bounded-degree graphs and general trees

Abstract

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.

Published in at http://dx.doi.org/10.1214/12-AOP822 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (6)

• Minima in branching random walks
• Percolation on finite graphs and isoperimetric inequalities
• Tightness for a family of recursion equations
• Chaos, concentration, and multiple valleys
• Uniformity of the uncovered set of random walk and cutoff for lamplighter chains
• Deterministic approximation for the cover time of trees

Cited by in corpus (5)

• Maxima of branching random walks with piecewise constant variance
• A polynomial time approximation scheme for computing the supremum of Gaussian processes
• A spectral characterization for concentration of the cover time
• A limit law for the most favorite point of simple random walk on a regular tree
• A Ray-Knight theorem for $\nabla \varphi$ interface models and scaling limits