Can extra updates delay mixing?

Details Can extra updates delay mixing? Can extra updates delay mixing?

2011-12-02

arxiv.org/abs/1112.0603v1

Mathematics

Probability

14 pages

Scientific paper

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. We deduce that for monotone Markov random fields, when block dynamics contracts a Hamming metric, single-site dynamics mixes in O(n log n) steps on an n-vertex graph. In particular, our result completes work of Kenyon, Mossel and Peres 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, Sly, Ding, Lubetzky, and Peres in various combinations.

Affiliated with

Also associated with

No associations

Rating

Can extra updates delay mixing? does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Can extra updates delay mixing?, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Can extra updates delay mixing? will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-697519