Cover times, blanket times, and the Gaussian free field.

Add to your list(s) Download to your calendar using vCal

• Yuval Peres Microsoft Research, Redmond
• Tuesday 01 November 2011, 14:15-15:15
• MR12, CMS, Wilberforce Road, Cambridge, CB3 0WB.

If you have a question about this talk, please contact Julia Blackwell.

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 a bounded 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 bounded by the cover time multiplied by a universal constant.

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 positive answers to the questions of Aldous-Fill (1994) and Winkler-Zuckerman (1996). No prior familiarity with cover times or the Gaussian free field will be assumed.

Their basic properties will be explained in the talk.

(Joint work with Jian Ding and James Lee)

This talk is part of the Probability series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• DPMMS Lists
• DPMMS info aggregator
• MR12, CMS, Wilberforce Road, Cambridge, CB3 0WB
• Probability
• School of Physical Sciences
• Statistical Laboratory info aggregator

Note that ex-directory lists are not shown.