Скачать или смотреть Cover times, blanket times, and the Gaussian free field - Microsoft Research 2010

Speaker: #Yuval_Peres

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

More Information:
▪ Related presentation: Cover times, blanket times and majorizing measures
https://yuval-peres-presentations.com/cove...

▪ Related publication: Ding, Jian, James R. Lee, and Yuval Peres. "Cover times, blanket times, and majorizing measures." In Proceedings of the forty-third annual ACM symposium on Theory of computing, pp. 61-70. 2011. https://dl.acm.org/doi/pdf/10.1145/1993636...

▪ Related publication: Ding, Jian, James R. Lee, and Yuval Peres. "Cover times, blanket times, and majorizing measures." Annals of Mathematics 175, no. 3 (2012): 1409-1471. https://annals.math.princeton.edu/2012/175...