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), p. 1020-1028 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2011-01-01
DOI : https://doi.org/10.1214/10-AIHP402
Classification:  60J10,  60K35,  68W20 
@article{AIHPB_2011__47_4_1020_0,
     author = {Ding, Jian and Peres, Yuval},
     title = {Mixing time for the Ising model : a uniform lower bound for all graphs},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     volume = {47},
     year = {2011},
     pages = {1020-1028},
     doi = {10.1214/10-AIHP402},
     zbl = {1274.82012},
     language = {en},
     url = {http://dml.mathdoc.fr/item/AIHPB_2011__47_4_1020_0}
}

Ding, Jian; Peres, Yuval. Mixing time for the Ising model : a uniform lower bound for all graphs. Annales de l'I.H.P. Probabilités et statistiques, Tome 47 (2011) pp. 1020-1028. doi : 10.1214/10-AIHP402. http://gdmltest.u-ga.fr/item/AIHPB_2011__47_4_1020_0/

[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 770418 | Zbl 0514.60067

[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 376053

[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 2014387

[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 266507

[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 2326236 | Zbl 1125.60075

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

[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 2550363 | Zbl 1187.82076

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

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

[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 1746301 | Zbl 0930.00052

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

[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 1277.82036

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