Information percolation and cutoff for the stochastic Ising model

Lubetzky, Eyal¹ ; Sly, Allan²

¹ Courant Institute, New York University, 251 Mercer Street, New York, New York 10012
² Department of Statistics, UC Berkeley, Berkeley, California 94720

Journal of the American Mathematical Society, Tome 29 (2016) no. 3, pp. 729-774

Résumé

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.

Détail

DOI : 10.1090/jams/841

Bibliographie

[1] Aizenman, M., Holley, R. Rapid convergence to equilibrium of stochastic Ising models in the Dobrushin Shlosman regime 1987 1 11

[2] Aldous, David Random walks on finite groups and rapidly mixing Markov chains 1983 243 297

[3] Aldous, David, Diaconis, Persi Shuffling cards and stopping times Amer. Math. Monthly 1986 333 348

[4] Cesi, Filippo, Martinelli, Fabio On the layering transition of an SOS surface interacting with a wall. II. The Glauber dynamics Comm. Math. Phys. 1996 173 201

[5] Diaconis, Persi The cutoff phenomenon in finite Markov chains Proc. Nat. Acad. Sci. U.S.A. 1996 1659 1664

[6] Diaconis, Persi, Graham, R. L., Morrison, J. A. Asymptotic analysis of a random walk on a hypercube with many dimensions Random Structures Algorithms 1990 51 72

[7] Diaconis, Persi, Saloff-Coste, Laurent Comparison techniques for random walk on finite groups Ann. Probab. 1993 2131 2156

[8] Diaconis, Persi, Saloff-Coste, Laurent Comparison theorems for reversible Markov chains Ann. Appl. Probab. 1993 696 730

[9] Diaconis, P., Saloff-Coste, L. Logarithmic Sobolev inequalities for finite Markov chains Ann. Appl. Probab. 1996 695 750

[10] Diaconis, Persi, Shahshahani, Mehrdad Generating a random permutation with random transpositions Z. Wahrsch. Verw. Gebiete 1981 159 179

[11] Diaconis, Persi, Shahshahani, Mehrdad Time to reach stationarity in the Bernoulli-Laplace diffusion model SIAM J. Math. Anal. 1987 208 218

[12] Ding, Jian, Lubetzky, Eyal, Peres, Yuval The mixing time evolution of Glauber dynamics for the mean-field Ising model Comm. Math. Phys. 2009 725 764

[13] Holley, Richard On the asymptotics of the spin-spin autocorrelation function in stochastic Ising models near the critical temperature 1991 89 104

[14] Holley, Richard, Stroock, Daniel Logarithmic Sobolev inequalities and stochastic Ising models J. Statist. Phys. 1987 1159 1194

[15] Markov chain Monte Carlo 2005

[16] Levin, David A., Luczak, Malwina J., Peres, Yuval Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability Probab. Theory Related Fields 2010 223 265

[17] Levin, D.A., Peres, Y., Wilmer, E.L. Markov chains and mixing times American Mathematical Society 2008

[18] Liggett, Thomas M. Interacting particle systems 2005

[19] Lubetzky, Eyal, Sly, Allan Cutoff phenomena for random walks on random regular graphs Duke Math. J. 2010 475 510

[20] Lubetzky, Eyal, Sly, Allan Cutoff for the Ising model on the lattice Invent. Math. 2013 719 755

[21] Lubetzky, Eyal, Sly, Allan Cutoff for general spin systems with arbitrary boundary conditions Comm. Pure Appl. Math. 2014 982 1027

[22] Lubetzky, Eyal, Sly, Allan Universality of cutoff for the Ising model

[23] Martinelli, Fabio Lectures on Glauber dynamics for discrete spin models 1999 93 191

[24] Martinelli, F., Olivieri, E. Approach to equilibrium of Glauber dynamics in the one phase region. I. The attractive case Comm. Math. Phys. 1994 447 486

[25] Martinelli, F., Olivieri, E. Approach to equilibrium of Glauber dynamics in the one phase region. II. The general case Comm. Math. Phys. 1994 487 514

[26] Martinelli, F., Olivieri, E., Schonmann, R. H. For 2-D lattice spin systems weak mixing implies strong mixing Comm. Math. Phys. 1994 33 47

[27] Miller, Jason, Peres, Yuval Uniformity of the uncovered set of random walk and cutoff for lamplighter chains Ann. Probab. 2012 535 577

[28] Propp, James Gary, Wilson, David Bruce Exact sampling with coupled Markov chains and applications to statistical mechanics Random Structures Algorithms 1996 223 252

[29] Saloff-Coste, Laurent Lectures on finite Markov chains 1997 301 413

[30] Saloff-Coste, Laurent Random walks on finite groups 2004 263 346

[31] Sokal, Alan Monte Carlo methods in statistical mechanics: foundations and new algorithms 1989

[32] Stroock, Daniel W., Zegarliå„Ski, Boguså‚Aw The equivalence of the logarithmic Sobolev inequality and the Dobrushin-Shlosman mixing condition Comm. Math. Phys. 1992 303 323

[33] Stroock, Daniel W., Zegarliå„Ski, Boguså‚Aw The logarithmic Sobolev inequality for discrete spin systems on a lattice Comm. Math. Phys. 1992 175 193