Cover times, blanket times, and the Gaussian free field

Опубликовано 17 августа 2016, 21:23

The cover time of a finite graph G (the expected time for simple random walk to visit all vertices) has been extensively studied, yet a number of fundamental questions concerning cover times have remained open: Aldous and Fill (1994) asked whether there is a deterministic polynomial-time algorithm that computes the cover time up to an O(1) factor; Winkler and Zuckerman (1996) defined the blanket time (when the empirical distribution of the walk is within a factor of 2, say, of the stationary distribution) and conjectured that the blanket time is always within O(1) of the cover time. The best approximation factor found so far for both these problems was (log log n)^2 for n-vertex graphs, due to Kahn, Kim, Lovasz, and Vu (2000). We show that the cover time of G, normalized by the number of edges, is equivalent (up to a universal constant) to the square of the expected maximum of the Gaussian free field on G. We use this connection and Talagrand's majorizing measure theory to deduce a positive answer to the question of Aldous-Fill (1994) and establish the conjecture of Winkler-Zuckerman (1996). All these results extend to arbitrary reversible finite Markov chains. Joint work with Jian Ding (U.C. Berkeley) and James Lee (University of Washington).