no. 4
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) no. 4, pp. 1020-1028

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.

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.

DOI : 10.1214/10-AIHP402
Classification : 60J10, 60K35, 68W20
Keywords: Glauber dynamics, mixing time, Ising model 
@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},
     pages = {1020--1028},
     year = {2011},
     publisher = {Gauthier-Villars},
     volume = {47},
     number = {4},
     doi = {10.1214/10-AIHP402},
     zbl = {1274.82012},
     language = {en},
     url = {https://www.numdam.org/articles/10.1214/10-AIHP402/}
}
TY  - JOUR
AU  - Ding, Jian
AU  - Peres, Yuval
TI  - Mixing time for the Ising model : a uniform lower bound for all graphs
JO  - Annales de l'I.H.P. Probabilités et statistiques
PY  - 2011
SP  - 1020
EP  - 1028
VL  - 47
IS  - 4
PB  - Gauthier-Villars
UR  - https://www.numdam.org/articles/10.1214/10-AIHP402/
DO  - 10.1214/10-AIHP402
LA  - en
ID  - AIHPB_2011__47_4_1020_0
ER  - 
%0 Journal Article
%A Ding, Jian
%A Peres, Yuval
%T Mixing time for the Ising model : a uniform lower bound for all graphs
%J Annales de l'I.H.P. Probabilités et statistiques
%D 2011
%P 1020-1028
%V 47
%N 4
%I Gauthier-Villars
%U https://www.numdam.org/articles/10.1214/10-AIHP402/
%R 10.1214/10-AIHP402
%G en
%F 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) no. 4, pp. 1020-1028. doi: 10.1214/10-AIHP402

[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. | Zbl | MR | Numdam

[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. | Zbl | MR

[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. | Zbl | MR

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

[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. | Zbl | MR

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

[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. | Zbl | MR

Cité par Sources :