Speaker:

Yuval Peres, Microsoft Research

Title:

Can extra updates delay mixing?

Abstract:

We consider Glauber dynamics (starting from an extremal configuration) in a monotone spin system, and show that interjecting extra updates cannot increase the expected Hamming distance or the total variation distance to the stationary distribution. In particular, our result completes earlier work with Kenyon and Mossel and concerning Glauber dynamics for the Ising model on trees. Our approach also shows that on bipartite graphs, alternating updates systematically between odd and even vertices cannot improve the mixing time by more than a factor of log n compared to updates at uniform random locations on an n-vertex graph. Our result is especially effective in comparing block and single-site dynamics; it has already been used in works of Martinelli, Sinclair, Mossel, Toninelli, Sly, Ding, Lubetzky, and the speaker in various combinations. Proving an analog for the Potts model is an open problem.
(Joint work with Peter Winkler)