Mixing time for the Ising model : a uniform lower bound for all graphs

Ding, Jian; Peres, Yuval

Annales de l'I.H.P. Probabilités et statistiques, Tome 47 (2011) no. 4, pp. 1020-1028.

Dans cet article nous étudions la dynamique de Glauber du modèle d'Ising sur un graphe fini à n sommets. Hayes et Sinclair ont montré que le temps de mélange de cette dynamique est au moins de nlog(n)f(Δ), où Δ est le degré maximum d'un sommet du graphe et f(Δ) = Θ(Δ log2(Δ)). Leur résultat s'applique également à des modèles de spins généraux où la dépendance en Δ est nécessaire. Dans ce travail nous nous concentrons sur le modèle d'Ising ferromagnétique et montrons que le temps de mélange de la dynamique de Glauber est au moins de (1/4 + o(1))n log(n) sur n'importe quel graphe à n sommets.

Consider Glauber dynamics for the Ising model on a graph of n vertices. Hayes and Sinclair showed that the mixing time for this dynamics is at least nlog n/f(Δ), where Δ is the maximum degree and f(Δ) = Θ(Δlog2Δ). Their result applies to more general spin systems, and in that generality, they showed that some dependence on Δ is necessary. In this paper, we focus on the ferromagnetic Ising model and prove that the mixing time of Glauber dynamics on any n-vertex graph is at least (1/4 + o(1))nlog n.

Classification : 60J10, 60K35, 68W20
Mots clés : Glauber dynamics, mixing time, Ising model

[1] D. Aldous. Random walks on finite groups and rapidly mixing Markov chains. In Seminar on Probability, XVII 243-297. Lecture Notes in Math. 986. Springer, Berlin, 1983. | Numdam | MR | Zbl

[2] D. Aldous and J. A. Fill. Reversible Markov chains and random walks on graphs. Available at http://www.stat.berkeley.edu/~aldous/RWG/book.html. To appear.

[3] R. S. Ellis and J. L. Monroe. A simple proof of the GHS and further inequalities. Comm. Math. Phys. 41 (1975) 33-38. | MR

[4] H.-O. Georgii, O. Häggström and C. Maes. The random geometry of equilibrium phases. In Phase Transitions and Critical Phenomena 1-142. Phase Transit. Crit. Phenom. 18. Academic Press, San Diego, CA, 2001. | MR

[5] R. B. Griffiths, C. A. Hurst and S. Sherman. Concavity of magnetization of an Ising ferromagnet in a positive external field. J. Math. Phys. 11 (1970) 790-795. | MR

[6] T. P. Hayes and A. Sinclair. A general lower bound for mixing of single-site dynamics on graphs. Ann. Appl. Probab. 17 (2007) 931-952. Preliminary version appeared in Proceedings of IEEE FOCS 2005 511-520. | MR | Zbl

[7] J. L. Lebowitz. GHS and other inequalities. Comm. Math. Phys. 35 (1974) 87-92. | MR

[8] D. A. Levin, M. Luczak and Y. Peres. Glauber dynamics for the mean-field Ising model: Cut-off, critical power law, and metastability. Probab. Theory Related Fields 146 (2009) 223-265. | MR | Zbl

[9] D. A. Levin, Y. Peres and E. L. Wilmer. Markov Chains and Mixing Times. Amer. Math. Soc., Providence, RI, 2009. | MR | Zbl

[10] E. Lubetzky and A. Sly. Cutoff for the Ising model on the lattice. Preprint, 2009. | Zbl

[11] F. Martinelli. Lectures on Glauber dynamics for discrete spin models. In Lectures on Probability Theory and Statistics (Saint-Flour, 1997) 93-191. Lecture Notes in Math. 1717. Springer, Berlin, 1999. | MR | Zbl

[12] Ş. Nacu. Glauber dynamics on the cycle is monotone. Probab. Theory Related Fields 127 (2003) 177-185. | MR | Zbl

[13] Y. Peres. Lectures on “Mixing for Markov Chains and Spin Systems,” Univ. British Columbia, August 2005. Available at http://www.stat.berkeley.edu/~peres/ubc.pdf.

[14] Y. Peres and P. Winkler. Can extra updates delay mixing? To appear. | Zbl

[15] A. Sinclair. Algorithms for Random Generation and Counting. Progress in Theoretical Computer Science. Birkhäuser, Boston, MA, 1993. | MR | Zbl