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. 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, Toninelli, Sinclair, Mossel, Sly, Ding, Lubetzky, and Peres in various combinations.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alon, N., Spencer, J.: The Probabilistic Method, 3rd ed., Hoboken, New Jersey: John Wiley & Sons, 2008
van den Berg J., Brouwer R.: Random sampling for the monomer-dimer model on a lattice. J. Math. Phys. 41, 1585–1597 (1999)
Berger N., Kenyon C., Mossel E., Peres Y.: Glauber dynamics on trees and hyperbolic graphs. Prob. Th. Rel. Fields 131, 311–340 (2005)
Bubley, R., Dyer, M.: Path coupling: a technique for proving rapid mixing in Markov chains. In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), Los Alamitos, CA: IEEE Comp. Soc., 1997, pp. 223–231
Ding J., Lubetzky E., Peres Y.: Mixing time of critical Ising model on trees is polynomial in the height. Commun. Math. Phys. 295, 161–207 (2010)
Ding J., Peres Y.: Mixing time for the Ising model: a uniform lower bound for all graphs. Ann. l’Inst. H. Poincaré - Prob. et Stat. 47, 1020–1028 (2011)
Dyer M., Goldberg L.A., Jerrum M.: Systematic scan for sampling colourings. Ann. Appl. Prob. 16, 185–230 (2006)
Dyer M., Goldberg L.A., Jerrum M.: Dobrushin conditions and systematic scan. Comb. Prob. Comp. 17, 761–779 (2008)
Dyer M., Sinclair A., Vigoda E., Weitz D.: Mixing in time and space for lattice spin systems: A combinatorial view. Rand. Struct. Alg. 24, 461–479 (2004)
Hayes, T.P., Sinclair, A.: A general lower bound for mixing of single-site dynamics on graphs. In: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), Los Alamitos, CA: IEEE Comp. Soc., 2005, pp. 511–520
Holroyd A.: Some circumstances where extra updates can delay mixing. J. Stat. Phys. 145, 1649–1652 (2011)
Kenyon, C., Mossel, E., Peres, Y.: Glauber dynamics on trees and hyperbolic graphs (extended abstract). In: 42nd IEEE Symposium on Foundations of Computer Science (FOCS), Las Vegas, NV, 2001), Los Alamitos, CA: IEEE Computer Soc., 2001, pp. 568–578
Levin, D. A., Peres, Y., Wilmer, E.: Markov Chains and Mixing Times, Providence, RI: Amer. Math. Soc., 2008
Liggett, T.: Interacting particle systems. New York: Springer, 1985
Martinelli, F.: Lectures on Glauber dynamics for discrete spin models. In: Lectures on probability theory and statistics (Saint-Flour, 1997) Lecture Notes in Math. 1717, Berlin: Springer, 1998, pp. 93–191
Martinelli, F.: Relaxation times of Markov chains in statistical mechanics and combinatorial structures. In: Encyclopedia of Mathematical Sciences, Vol. 110, Berlin-Heidelberg-New York: Springer, 2003, pp. 175–272
Martinelli F., Olivieri E.: Approach to equilibrium of Glauber dynamics in the one phase region I: The attractive case. Commun. Math. Phys. 161, 447–486 (1994)
Martinelli, F., Sinclair, A.: Mixing time for the Solid-on-Solid model. In: Proc. ACM STOC 2009, New York: ACM, 2009, pp. 571–580
Martinelli F., Sinclair A., Weitz D.: Glauber dynamics on trees: Boundary conditions and mixing time. Commun. Math. Phys. 250, 301–334 (2004)
Martinelli F., Toninelli F.: On the mixing time of the 2D stochastic Ising model with “plus” boundary conditions at low temperature. Commun. Math. Phys. 296, 175–213 (2010)
Mossel E., Sly A.: Exact Thresholds for Ising-Gibbs Samplers on General Graphs. Ann. Prob. 41(1), 294–328 (2013)
Nacu S.: Glauber dynamics on the cycle is monotone. Prob. Th. Rel. Fields 127, 177–185 (2003)
Peres, Y.: Lectures on Mixing for Markov Chains and Spin Systems. University of British Columbia, Summary at http://www.stat.berkeley.edu/~peres/ubc.pdf, 2005
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by F. L. Toninelli
Rights and permissions
About this article
Cite this article
Peres, Y., Winkler, P. Can Extra Updates Delay Mixing?. Commun. Math. Phys. 323, 1007–1016 (2013). https://doi.org/10.1007/s00220-013-1776-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00220-013-1776-0