Cover Times, Blanket Times, And The Gaussian Free Field

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).

Speaker Details

Yuval Peres is a Principal Researcher and manager of the Theory group at Microsoft Research. Before joining MSR in 2006, he was a Professor at UC Berkeley.
He has also taught at Yale and at the Hebrew University. Yuval has published more than 160 papers with 90 co-authors and has mentored 15 PhD theses. His research encompasses most areas of probability theory, including random walks, Brownian motion, percolation, and random graphs. He has recently co-authored books on Markov chains and mixing times, on zeros of Gaussian analytic functions, and on Brownian motion. Yuval is an IMS fellow and a recipient of the Rollo Davidson prize. In 2001 he received the Loeve prize, awarded once every two years to a leading probabilist under the age of 45. In 2002, Yuval was an invited speaker at the International Congress of Mathematicians in Beijing and in 2009, he delivered a plenary talk at SODA. His favorite quote is from his son Alon, who was overheard at age 6 asking a friend: “Leo, do you have a religion? You know, a religion, like Christian, or Jewish, or Mathematics….?”

Date:
Speakers:
Yuval Peres
Affiliation:
MSR Redmond
    • Portrait of Jeff Running

      Jeff Running

    • Portrait of Yuval Peres

      Yuval Peres

      Principal Researcher