Abstract
In the heat-bath Glauber dynamics for the Ising model on the lattice, physicists believe that the spectral gap of the continuous-time chain exhibits the following behavior. For some critical inverse-temperature β c , the inverse-gap is O(1) for β < β c , polynomial in the surface area for β = β c and exponential in it for β > β c . This has been proved for \({\mathbb{Z}^2}\) except at criticality. So far, the only underlying geometry where the critical behavior has been confirmed is the complete graph. Recently, the dynamics for the Ising model on a regular tree, also known as the Bethe lattice, has been intensively studied. The facts that the inverse-gap is bounded for β < β c and exponential for β > β c were established, where β c is the critical spin-glass parameter, and the tree-height h plays the role of the surface area.
In this work, we complete the picture for the inverse-gap of the Ising model on the b-ary tree, by showing that it is indeed polynomial in h at criticality. The degree of our polynomial bound does not depend on b, and furthermore, this result holds under any boundary condition. We also obtain analogous bounds for the mixing-time of the chain. In addition, we study the near critical behavior, and show that for β > β c , the inverse-gap and mixing-time are both exp[Θ((β − β c )h)].
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aldous, D., Fill J.A.: Reversible Markov Chains and Random Walks on Graphs, In preparation, http://www.stat.berkeley.edu/~aldous/RWG/book.html
Baxter, R.J.: Exactly Solved Models in Statistical Mechanics. London: Academic Press Inc. [Harcourt Brace Jovanovich Publishers], 1989. Reprint of the 1982 original
Berger N., Kenyon C., Mossel E., Peres Y.: Glauber dynamics on trees and hyperbolic graphs. Prob. Th. Rel. Fields 131(3), 311–340 (2005)
Bleher P.M., Ruiz J., Zagrebnov V.A.: On the purity of the limiting Gibbs state for the Ising model on the Bethe lattice. J. Stat. Phys. 79(1-2), 473–482 (1995)
Carlson J.M., Chayes J.T., Chayes L., Sethna J.P., Thouless D.J.: Bethe lattice spin glass: the effects of a ferromagnetic bias and external fields. I. Bifurcation analysis. J. Stat. Phys. 61(5-6), 987–1067 (1990)
Carlson J.M., Chayes J.T., Chayes L., Sethna J.P., Thouless D.J.: Critical Behavior of the Bethe Lattice Spin Glass. Europhys. Lett. 106(5), 355–360 (1988)
Carlson J.M., Chayes J.T., Sethna J.P., Thouless D.J.: Bethe lattice spin glass: the effects of a ferromagnetic bias and external fields. II. Magnetized spin-glass phase and the de Almeida-Thouless line. J. Stat. Phys. 61(5-6), 1069–1084 (1990)
Chen, M.-F.: Trilogy of couplings and general formulas for lower bound of spectral gap. Probability towards 2000 (New York, 1995), Lecture Notes in Statist., Vol. 128, New York: Springer, 1998, pp. 123–136
Ding J., Lubetzky E., Peres Y.: The mixing time evolution of Glauber dynamics for the mean-field Ising model. Commun. Math. Phys. 289(2), 725–764 (2009)
Diaconis P., Saloff-Coste L.: Comparison techniques for random walk on finite groups. Ann. Probab. 21(4), 2131–2156 (1993)
Diaconis P., Saloff-Coste L.: Comparison theorems for reversible Markov chains. Ann. Appl. Probab. 3(3), 696–730 (1993)
Diaconis P., Saloff-Coste L.: Logarithmic Sobolev inequalities for finite Markov chains. Ann. Appl. Probab. 6(3), 695–750 (1996)
Diaconis P., Saloff-Coste L.: Nash inequalities for finite Markov chains. J. Theor. Prob. 9(2), 459–510 (1996)
Domb, C., Lebowitz, J.L. (eds.): Phase Transitions and Critical Penomena. Vol. 20, San Diego, CA: Academic Press, 2001
Evans W., Kenyon C., Peres Y., Schulman L.J.: Broadcasting on trees and the Ising model. Ann. Appl. Probab. 10(2), 410–433 (2000)
Hohenberg P.C., Halperin B.I.: Theory of dynamic critical phenomena. Rev. Mod. Phys. 49(3), 435–479 (1977)
Ioffe, D.: Extremality of the disordered state for the Ising model on general trees. Trees (Versailles, 1995), Progr. Probab., Vol. 40, Basel: Birkhäuser, 1996, pp. 3–14 (English, with English and French summaries)
Ioffe D.: On the extremality of the disordered state for the Ising model on the Bethe lattice. Lett. Math. Phys. 37(2), 137–143 (1996)
Jerrum M., Son J.-B., Tetali P., Vigoda E.: Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains. Ann. Appl. Probab. 14(4), 1741–1765 (2004)
Lauritsen K.B., Fogedby H.C.: Critical exponents from power spectra. J. Stat. Phys. 72(1), 189–205 (1993)
Le Cam, L.: Notes on Asymptotic Methods in Statistical Decision Theory. Centre de Recherches Mathématiques, Montreal, Que.: Université de Montréal, 1974
Levin, D.A., Peres, Y., Wilmer, E.: Markov Chains and Mixing Times. Amer. Math. Soc., 2008
Lyons R.: The Ising model and percolation on trees and tree-like graphs. Commun. Math. Phys. 125(2), 337–353 (1989)
Lyons, R., Peres, Y.: Probability on Trees and Networks. Cambridge University Press, 2008, In preparation. Current version is available at http://mypage.iu.edu/~rdlyons/prbtree/book.pdf
Martinelli, F.: Lectures on Glauber dynamics for discrete spin models. In: Lectures on Probability Theory and Statistics (Saint-Flour, 1997), Lecture Notes in Math., Vol. 1717, Berlin: Springer, 1999, 93–191
Martinelli F.: On the two-dimensional dynamical Ising model in the phase coexistence region. J. Stat. Phys. 76(5-6), 1179–1246 (1994)
Martinelli F., Sinclair A., Weitz D.: Glauber dynamics on trees: boundary conditions and mixing time. Commun. Math. Phys. 250(2), 301–334 (2004)
Murakami A., Yamasaki M.: Nonlinear potentials on an infinite network. Mem. Fac. Sci. Shimane Univ. 26, 15–28 (1992)
Nacu Ş.: Glauber Dynamics on the Cycle is Monotone. Prob. Th. Re. Fields 127, 177–185 (2003)
Nash-Williams C.St.J.A.: Random walk and electric currents in networks. Proc. Cambridge Philos. Soc. 55, 181–194 (1959)
Pemantle, R., Peres, Y.: The critical Ising model on trees, concave recursions and nonlinear capacity, Ann. Probab., to appear, http://arxiv.org/abs/math/0503137v2[math.PR], 2006
Peres, Y.: Lectures on “Mixing for Markov Chains and Spin Systems” (University of British Columbia, August 2005). Summary available at http://www.stat.berkeley.edu/~peres/ubc.pdf
Peres, Y., Winkler, P.: Can extra updates delay mixing? In preparation
Preston, C.J.: Gibbs States on Countable Sets. Cambridge Tracts in Mathematics, No. 68, London: Cambridge University Press, 1974
Saloff-Coste, L.: Lectures on finite Markov chains. In: Lectures on Probability Theory and Statistics (Saint-Flour, 1996), Lecture Notes in Math., Vol. 1665, Berlin: Springer, 1997, pp. 301–413
Soardi P.M.: Morphisms and currents in infinite nonlinear resistive networks. Potential Anal. 2(4), 315–347 (1993)
Soardi, P.M.: Potential Theory on Infinite Networks. Lecture Notes in Mathematics, Vol. 1590, Berlin: Springer-Verlag, 1994
Wang F.-G., Hu C.-K.: Universality in dynamic critical phenomena. Phys. Rev. E 56(2), 2310–2313 (1997)
Wilson D.B.: Mixing times of Lozenge tiling and card shuffling Markov chains. Ann. Appl. Probab. 14(1), 274–325 (2004)
Acknowledgements
We thank the anonymous referees for helpful comments.
Open Access
This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by F. Toninelli
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Ding, J., Lubetzky, E. & Peres, Y. Mixing Time of Critical Ising Model on Trees is Polynomial in the Height. Commun. Math. Phys. 295, 161–207 (2010). https://doi.org/10.1007/s00220-009-0978-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00220-009-0978-y