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)