## Information percolation and cutoff for the stochastic Ising model

HTML articles powered by AMS MathViewer

- by Eyal Lubetzky and Allan Sly PDF
- J. Amer. Math. Soc.
**29**(2016), 729-774 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

## Additional Information

**Eyal Lubetzky**- Affiliation: Courant Institute, New York University, 251 Mercer Street, New York, New York 10012
- MR Author ID: 787713
- ORCID: 0000-0002-2281-3542
- Email: eyal@courant.nyu.edu
**Allan Sly**- Affiliation: Department of Statistics, UC Berkeley, Berkeley, California 94720
- MR Author ID: 820461
- Email: sly@stat.berkeley.edu
- Received by editor(s): July 14, 2014
- Received by editor(s) in revised form: May 7, 2015
- Published electronically: September 29, 2015
- © Copyright 2015 American Mathematical Society
- Journal: J. Amer. Math. Soc.
**29**(2016), 729-774 - MSC (2010): Primary 60J27, 82C20; Secondary 60K35, 60B10
- DOI: https://doi.org/10.1090/jams/841
- MathSciNet review: 3486171