Information percolation and cutoff for the stochastic Ising model

Lubetzky, Eyal; Sly, Allan

doi:10.1090/jams/841

Information percolation and cutoff for the stochastic Ising model
HTML articles powered by AMS MathViewer

by Eyal Lubetzky and Allan Sly;

J. Amer. Math. Soc. 29 (2016), 729-774

DOI: https://doi.org/10.1090/jams/841

Published electronically: September 29, 2015

PDF | Request permission

Abstract:

We introduce a new framework for analyzing Glauber dynamics for the Ising model. The traditional approach for obtaining sharp mixing results has been to appeal to estimates on spatial properties of the stationary measure from within a multi-scale analysis of the dynamics. Here we propose to study these simultaneously by examining “information percolation” clusters in the space-time slab.

Using this framework, we obtain new results for the Ising model on $(\mathbb Z/n\mathbb Z)^d$ throughout the high temperature regime: total-variation mixing exhibits cutoff with an $O(1)$-window around the time at which the magnetization is the square root of the volume. (Previously, cutoff in the full high temperature regime was only known in dimensions $d\leq 2$, and only with an $O(\log \log n)$-window.)

Furthermore, the new framework opens the door to understanding the effect of the initial state on the mixing time. We demonstrate this on the 1D Ising model, showing that starting from the uniform (“disordered”) initial distribution asymptotically halves the mixing time, whereas almost every deterministic starting state is asymptotically as bad as starting from the (“ordered”) all-plus state.

References

M. Aizenman and R. Holley, Rapid convergence to equilibrium of stochastic Ising models in the Dobrushin Shlosman regime, Percolation theory and ergodic theory of infinite particle systems (Minneapolis, Minn., 1984–1985) IMA Vol. Math. Appl., vol. 8, Springer, New York, 1987, pp. 1–11. MR 894538, DOI 10.1007/978-1-4613-8734-3_{1}
David Aldous, Random walks on finite groups and rapidly mixing Markov chains, Seminar on probability, XVII, Lecture Notes in Math., vol. 986, Springer, Berlin, 1983, pp. 243–297. MR 770418, DOI 10.1007/BFb0068322
David Aldous and Persi Diaconis, Shuffling cards and stopping times, Amer. Math. Monthly 93 (1986), no. 5, 333–348. MR 841111, DOI 10.2307/2323590
Filippo Cesi and Fabio Martinelli, On the layering transition of an SOS surface interacting with a wall. II. The Glauber dynamics, Comm. Math. Phys. 177 (1996), no. 1, 173–201. MR 1382225, DOI 10.1007/BF02102435
Persi Diaconis, The cutoff phenomenon in finite Markov chains, Proc. Nat. Acad. Sci. U.S.A. 93 (1996), no. 4, 1659–1664. MR 1374011, DOI 10.1073/pnas.93.4.1659
Persi Diaconis, R. L. Graham, and J. A. Morrison, Asymptotic analysis of a random walk on a hypercube with many dimensions, Random Structures Algorithms 1 (1990), no. 1, 51–72. MR 1068491, DOI 10.1002/rsa.3240010105
Persi Diaconis and Laurent Saloff-Coste, Comparison techniques for random walk on finite groups, Ann. Probab. 21 (1993), no. 4, 2131–2156. MR 1245303
Persi Diaconis and Laurent Saloff-Coste, Comparison theorems for reversible Markov chains, Ann. Appl. Probab. 3 (1993), no. 3, 696–730. MR 1233621
P. Diaconis and L. Saloff-Coste, Logarithmic Sobolev inequalities for finite Markov chains, Ann. Appl. Probab. 6 (1996), no. 3, 695–750. MR 1410112, DOI 10.1214/aoap/1034968224
Persi Diaconis and Mehrdad Shahshahani, Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete 57 (1981), no. 2, 159–179. MR 626813, DOI 10.1007/BF00535487
Persi Diaconis and Mehrdad Shahshahani, Time to reach stationarity in the Bernoulli-Laplace diffusion model, SIAM J. Math. Anal. 18 (1987), no. 1, 208–218. MR 871832, DOI 10.1137/0518016
Jian Ding, Eyal Lubetzky, and Yuval Peres, The mixing time evolution of Glauber dynamics for the mean-field Ising model, Comm. Math. Phys. 289 (2009), no. 2, 725–764. MR 2506768, DOI 10.1007/s00220-009-0781-9
Richard Holley, On the asymptotics of the spin-spin autocorrelation function in stochastic Ising models near the critical temperature, Spatial stochastic processes, Progr. Probab., vol. 19, Birkhäuser Boston, Boston, MA, 1991, pp. 89–104. MR 1144093
Richard Holley and Daniel Stroock, Logarithmic Sobolev inequalities and stochastic Ising models, J. Statist. Phys. 46 (1987), no. 5-6, 1159–1194. MR 893137, DOI 10.1007/BF01011161
W. S. Kendall, F. Liang, and J.-S. Wang (eds.), Markov chain Monte Carlo, Lecture Notes Series. Institute for Mathematical Sciences. National University of Singapore, vol. 7, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2005. Innovations and applications. MR 2238833, DOI 10.1142/9789812700919
David A. Levin, Malwina J. Luczak, and Yuval Peres, Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability, Probab. Theory Related Fields 146 (2010), no. 1-2, 223–265. MR 2550363, DOI 10.1007/s00440-008-0189-z
D.A. Levin, Y. Peres, and E.L. Wilmer, Markov chains and mixing times, 2008., DOI 10.1090/mbk/058
Thomas M. Liggett, Interacting particle systems, Classics in Mathematics, Springer-Verlag, Berlin, 2005. Reprint of the 1985 original. MR 2108619, DOI 10.1007/b138374
Eyal Lubetzky and Allan Sly, Cutoff phenomena for random walks on random regular graphs, Duke Math. J. 153 (2010), no. 3, 475–510. MR 2667423, DOI 10.1215/00127094-2010-029
Eyal Lubetzky and Allan Sly, Cutoff for the Ising model on the lattice, Invent. Math. 191 (2013), no. 3, 719–755. MR 3020173, DOI 10.1007/s00222-012-0404-5
Eyal Lubetzky and Allan Sly, Cutoff for general spin systems with arbitrary boundary conditions, Comm. Pure Appl. Math. 67 (2014), no. 6, 982–1027. MR 3193965, DOI 10.1002/cpa.21489
Eyal Lubetzky and Allan Sly, Universality of cutoff for the Ising model, preprint. Available at arXiv:1407.1761 (2014)., DOI 10.1214/16-AOP1146
Fabio Martinelli, Lectures on Glauber dynamics for discrete spin models, Lectures on probability theory and statistics (Saint-Flour, 1997) Lecture Notes in Math., vol. 1717, Springer, Berlin, 1999, pp. 93–191. MR 1746301, DOI 10.1007/978-3-540-48115-7_{2}
F. Martinelli and E. Olivieri, Approach to equilibrium of Glauber dynamics in the one phase region. I. The attractive case, Comm. Math. Phys. 161 (1994), no. 3, 447–486. MR 1269387, DOI 10.1007/BF02101929
F. Martinelli and E. Olivieri, Approach to equilibrium of Glauber dynamics in the one phase region. II. The general case, Comm. Math. Phys. 161 (1994), no. 3, 487–514. MR 1269388, DOI 10.1007/BF02101930
F. Martinelli, E. Olivieri, and R. H. Schonmann, For $2$-D lattice spin systems weak mixing implies strong mixing, Comm. Math. Phys. 165 (1994), no. 1, 33–47. MR 1298940, DOI 10.1007/BF02099735
Jason Miller and Yuval Peres, Uniformity of the uncovered set of random walk and cutoff for lamplighter chains, Ann. Probab. 40 (2012), no. 2, 535–577. MR 2952084, DOI 10.1214/10-AOP624
James Gary Propp and David Bruce Wilson, Exact sampling with coupled Markov chains and applications to statistical mechanics, Proceedings of the Seventh International Conference on Random Structures and Algorithms (Atlanta, GA, 1995), 1996, pp. 223–252. MR 1611693, DOI 10.1002/(SICI)1098-2418(199608/09)9:1/2<223::AID-RSA14>3.3.CO;2-R
Laurent Saloff-Coste, Lectures on finite Markov chains, Lectures on probability theory and statistics (Saint-Flour, 1996) Lecture Notes in Math., vol. 1665, Springer, Berlin, 1997, pp. 301–413. MR 1490046, DOI 10.1007/BFb0092621
Laurent Saloff-Coste, Random walks on finite groups, Probability on discrete structures, Encyclopaedia Math. Sci., vol. 110, Springer, Berlin, 2004, pp. 263–346. MR 2023654, DOI 10.1007/978-3-662-09444-0_{5}
Alan Sokal, Monte Carlo methods in statistical mechanics: foundations and new algorithms, Lecture notes, Ecole Polytechnique de Lausanne, 1989.
Daniel W. Stroock and Bogusław Zegarliński, The equivalence of the logarithmic Sobolev inequality and the Dobrushin-Shlosman mixing condition, Comm. Math. Phys. 144 (1992), no. 2, 303–323. MR 1152374, DOI 10.1007/BF02101094
Daniel W. Stroock and Bogusław Zegarliński, The logarithmic Sobolev inequality for discrete spin systems on a lattice, Comm. Math. Phys. 149 (1992), no. 1, 175–193. MR 1182416, DOI 10.1007/BF02096629