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

Jian Ding; Yuval Peres

Annales de l'I.H.P. Probabilités et statistiques (2011)

  • Volume: 47, Issue: 4, page 1020-1028
  • ISSN: 0246-0203

Abstract

top
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.

How to cite

top

Ding, Jian, and 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 47.4 (2011): 1020-1028. <http://eudml.org/doc/243582>.

@article{Ding2011,
abstract = {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.},
author = {Ding, Jian, Peres, Yuval},
journal = {Annales de l'I.H.P. Probabilités et statistiques},
keywords = {Glauber dynamics; mixing time; Ising model; Galuber dynamics},
language = {eng},
number = {4},
pages = {1020-1028},
publisher = {Gauthier-Villars},
title = {Mixing time for the Ising model : a uniform lower bound for all graphs},
url = {http://eudml.org/doc/243582},
volume = {47},
year = {2011},
}

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
PB - Gauthier-Villars
VL - 47
IS - 4
SP - 1020
EP - 1028
AB - 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.
LA - eng
KW - Glauber dynamics; mixing time; Ising model; Galuber dynamics
UR - http://eudml.org/doc/243582
ER -

References

top
  1. [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. Zbl0514.60067MR770418
  2. [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. [3] R. S. Ellis and J. L. Monroe. A simple proof of the GHS and further inequalities. Comm. Math. Phys. 41 (1975) 33–38. MR376053
  4. [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. MR2014387
  5. [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. MR266507
  6. [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 2005511–520. Zbl1125.60075MR2326236
  7. [7] J. L. Lebowitz. GHS and other inequalities. Comm. Math. Phys. 35 (1974) 87–92. MR339738
  8. [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. Zbl1187.82076MR2550363
  9. [9] D. A. Levin, Y. Peres and E. L. Wilmer. Markov Chains and Mixing Times. Amer. Math. Soc., Providence, RI, 2009. Zbl1160.60001MR2466937
  10. [10] E. Lubetzky and A. Sly. Cutoff for the Ising model on the lattice. Preprint, 2009. Zbl1273.82014
  11. [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. Zbl0930.00052MR1746301
  12. [12] Ş. Nacu. Glauber dynamics on the cycle is monotone. Probab. Theory Related Fields 127 (2003) 177–185. Zbl1068.82014MR2013980
  13. [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. [14] Y. Peres and P. Winkler. Can extra updates delay mixing? To appear. 
  15. [15] A. Sinclair. Algorithms for Random Generation and Counting. Progress in Theoretical Computer Science. Birkhäuser, Boston, MA, 1993. Zbl0780.68096MR1201590

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.