zbMATH — the first resource for mathematics

Can extra updates delay mixing? (English) Zbl 1277.82036
Summary: 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.

MSC:
 82C20 Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics 82D40 Statistical mechanical studies of magnetic materials 60K35 Interacting random processes; statistical mechanics type models; percolation theory 60G60 Random fields
Full Text:
References:
 [1] Alon, N., Spencer, J.: The Probabilistic Method, 3\^{rd} ed., Hoboken, New Jersey: John Wiley & Sons, 2008 · Zbl 1148.05001 [2] Berg, J.; Brouwer, R., Random sampling for the monomer-dimer model on a lattice, J. Math. Phys., 41, 1585-1597, (1999) · Zbl 1034.82012 [3] Berger, N.; Kenyon, C.; Mossel, E.; Peres, Y., Glauber dynamics on trees and hyperbolic graphs, Prob. Th. Rel. Fields, 131, 311-340, (2005) · Zbl 1075.60003 [4] Bubley, R., Dyer, M.: Path coupling: a technique for proving rapid mixing in Markov chains. In: Proceedings of the 38\^{th}Annual Symposium on Foundations of Computer Science (FOCS), Los Alamitos, CA: IEEE Comp. Soc., 1997, pp. 223-231 · Zbl 1274.82012 [5] 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) · Zbl 1201.82027 [6] 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) · Zbl 1274.82012 [7] Dyer, M.; Goldberg, L.A.; Jerrum, M., Systematic scan for sampling colourings, Ann. Appl. Prob., 16, 185-230, (2006) · Zbl 1095.60024 [8] Dyer, M.; Goldberg, L.A.; Jerrum, M., Dobrushin conditions and systematic scan, Comb. Prob. Comp., 17, 761-779, (2008) · Zbl 1168.60035 [9] 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) · Zbl 1126.82021 [10] Hayes, T.P., Sinclair, A.: A general lower bound for mixing of single-site dynamics on graphs. In: 46\^{th}Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), Los Alamitos, CA: IEEE Comp. Soc., 2005, pp. 511-520 · Zbl 1076.82010 [11] Holroyd, A., Some circumstances where extra updates can delay mixing, J. Stat. Phys., 145, 1649-1652, (2011) · Zbl 1231.82039 [12] Kenyon, C., Mossel, E., Peres, Y.: Glauber dynamics on trees and hyperbolic graphs (extended abstract). In: 42\^{nd}IEEE Symposium on Foundations of Computer Science (FOCS), Las Vegas, NV, 2001), Los Alamitos, CA: IEEE Computer Soc., 2001, pp. 568-578 · Zbl 0793.60110 [13] Levin, D. A., Peres, Y., Wilmer, E.: Markov Chains and Mixing Times, Providence, RI: Amer. Math. Soc., 2008 · Zbl 1126.82021 [14] Liggett, T.: Interacting particle systems. New York: Springer, 1985 · Zbl 0559.60078 [15] 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 · Zbl 1201.82027 [16] 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 · Zbl 1206.82058 [17] 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) · Zbl 0793.60110 [18] Martinelli, F., Sinclair, A.: Mixing time for the Solid-on-Solid model. In: Proc. ACM STOC 2009, New York: ACM, 2009, pp. 571-580 · Zbl 1304.82071 [19] Martinelli, F.; Sinclair, A.; Weitz, D., Glauber dynamics on trees: boundary conditions and mixing time, Commun. Math. Phys., 250, 301-334, (2004) · Zbl 1076.82010 [20] 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) · Zbl 1191.82012 [21] Mossel, E.; Sly, A., Exact thresholds for Ising-Gibbs samplers on general graphs, Ann. Prob., 41, 294-328, (2013) · Zbl 1270.60113 [22] Nacu, S., Glauber dynamics on the cycle is monotone, Prob. Th. Rel. Fields, 127, 177-185, (2003) · Zbl 1068.82014 [23] 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 · Zbl 1231.82039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.