Glauber dynamics on nonamenable graphs: boundary conditions and mixing time
Abstract
We study the stochastic Ising model on finite graphs with n vertices and bounded degree and analyze the effect of boundary conditions on the mixing time. We show that for all low enough temperatures, the spectral gap of the dynamics with (+)-boundary condition on a class of nonamenable graphs, is strictly positive uniformly in n. This implies that the mixing time grows at most linearly in n. The class of graphs we consider includes hyperbolic graphs with sufficiently high degree, where the best upper bound on the mixing time of the free boundary dynamics is polynomial in n, with exponent growing with the inverse temperature. In addition, we construct a graph in this class, for which the mixing time in the free boundary case is exponentially large in n. This provides a first example where the mixing time jumps from exponential to linear in n while passing from free to (+)-boundary condition. These results extend the analysis of Martinelli, Sinclair and Weitz to a wider class of nonamenable graphs.
Full Text: Download PDF | View PDF online (requires PDF plugin)
Pages: 1980-2012
Publication Date: November 11, 2008
DOI: 10.1214/EJP.v13-574
References
- D. Aldous. Random walks on finite groups and rapidly mixing Markov chains. Seminar on probability, XVII, 243--297, Lecture Notes in Math., 986, Springer, Berlin, 1983 . Math. Review 86j:60156
- T. Bodineau. Translation invariant Gibbs states for the Ising model. Probab. Theory Related Fields 135 (2006), no. 2, 153--168. Math. Review 2007b:82007
- R. Bubley, M. Dyer. Path Coupling: a technique for proving rapid mixing in Markov Chains. Proc. of the 38th Annual IEEE Symposium on Foundations of Computer Science, 1997 , 223--231.
- N. Berger, C. Kenyon, E. Mossel, Y. Peres. Glauber dynamics on trees and hyperbolic graphs. Probab. Theory Relat. Fields 131 (2005), no. 3, 311--340. Math. Review 2005k:82066
- T. Bodineau, F. Martinelli. Some new results on the kinetic Ising model in a pure phase. J. Statist. Phys. 109 (2002), no. 1-2, 207--235. Math. Review 2003i:82057
- I. Benjamini, O. Schramm. Percolation beyond $\mathbb{Z}^d$, many questions and a few answers. Electron Comm. Probab. 1 (1996), no.8, 71--82. Math. Review 97j:60179
- I. Benjamini, O. Schramm. Percolation in the hyperbolic plane. J. Amer. Math. Soc. 14 (2001), no. 2, 487--507. Math. Review 2002h:82049
- J.T. Chayes, L. Chayes, J.P. Sethna, D.J. Thouless. A mean field spin glass with short-range interactions. Commun. Math. Phys. 106 (1986),no. 1, 41--89. Math. Review 88i:82054
- D. Fisher, D. Huse. Dynamics of droplet fluctuations in pure and random Ising systems. Phys. Rev. B 35 (1987), no.13, 6841--6846.
- H.-O. Georgii. Gibbs measures and Phase Transitions. de Gruyter Studies in Mathematics, 9. Walter de Gruyter & Co., Berlin, 1988 . Math. Review 89k:82010
- O. Hâ°ggstrËm, J. Jonasson, R. Lyons. Explicit isoperimetric constants and phase transitions in the random-cluster model. Ann. Probab. 30 (2002), no. 1, 443--473. Math. Review 2003e:60220
- S. Hoory, N. Linial, A. Wigderson. Expander graphs and their applications. Bull. Amer. Math. Soc. (N.S.) 43 (2006), no. 4, 439--561. Math. Review 2007h:68055
- D. Ioffe. Extremality of the disordered state for the Ising model on general trees. Trees (Versailles, 1995) , 3--14, Progr. Probab., 40, Birkhâ°user, Basel, 1996. Math. Review 98j:82013
- J. Jonasson. The random cluster model on a general graph and a phase transition characterization of nonamenability. Stochastic Process. Appl. 79 (1999), no. 2, 335--354. Math. Review 99k:60249
- J. Jonasson, J.E. Steif. Amenability and phase transition in the Ising model. J. Theoret. Probab. 12 (1999), no. 2, 549--559. Math. Review 2000b:60238
- H. Kesten. Percolation theory for mathematicians. Progr. Probab. Statist. 2. Birkhâ°user, Boston, Mass., 1982. Math. Review 84i:60145
- C. Kenyon, E. Mossel, Y. Peres. Glauber dynamics on trees and hyperbolic graphs. In 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001), IEEE Computer Soc., Los Alamitos, CA, 2001 , 568--578.
- T. Lindvall. Lectures on the coupling method. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1992. Math. Review 94c:60002
- R. Lyons. The Ising model and percolation on trees and tree-like graphs. Comm. Math. Phys. 125 (1989), no. 2, 337--353. Math. Review 90h:82046
- R. Lyons. Phase transitions on Nonamenable Graphs. J. Math. Phys. 41 (2000), no.3, 1099--1126. Math. Review 2001c:82028
- M. Luby, D. Randall, A. Sinclair. Markov chain algorithms for planar lattice structures. SIAM J. Comput. 31 (2001), no. 1, 167--192. Math. Review 2002h:82046
- W. Magnus. Noneuclidean tesselations and their groups. Pure and Applied Mathematics, Vol. 61. Academic Press, New York-London, 1974. . Math. Review 50 #4774
- F. Martinelli. Lectures on Glauber dynamics for discrete spin models. Lectures on probability and statistics (Saint-Flour, 1997), 93--191, Lecture Notes in Math., 1717, Springer, Berlin, 1999 . Math. Review 2002a:60163
- F. Martinelli, E. Olivieri. Approach to equilibrium of Glauber dynamics in the one phase region I: The attractive case. Comm. Math. Phys. 161 (1994), no. 3, 447--486. Math. Review 96c:82040
- F. Martinelli, E. Olivieri. Approach to equilibrium of Glauber dynamics in the one phase region II: The general case. Comm. Math. Phys. 161 (1994), no. 3, 487--514. Math. Review 96c:82041
- F. Martinelli, A. Sinclair, D. Weitz. Glauber dynamics on trees: boundary conditions and mixing time. Comm. Math. Phys. 250 (2004), no. 2, 301--334. Math. Review 2005j:82052
- R. Rietman, B. Nienhuis, J. Oitmaa. Ising model on hyperlattices. J. Phys. A 25 (1992), no. 24, 6577-6592. Math. Review 94e:82026
- L. Saloff-Coste. Lectures on finite Markov chains. Lectures on probability theory and statistics (Saint-Flour, 1996) , 301-413, Lecture Notes in Math., 1665 , Springer, Berlin, 1997 . Math. Review 99b:60119
- R. H. Schonmann. Multiplicity of Phase Transitions and mean-field criticality on highly non-amenable graphs. Comm. Math. Phys. 219 (2001), no. 2, 271--322. Math. Review 2002h:82036
- C. M. Series, Ya. G. Sinai. Ising models on the Lobachevsky plane. Comm. Math. Phys. 128 (1990), no. 1, 63--76. Math. Review 91b:82006
- D.W. Stroock, B. Zegarlinski. The logarithmic Sobolev inequality for discrete spin systems on a lattice. Comm. Math. Phys. 149 (1992), no. 1, 175--194. Math. Review 93j:82013
- D. Weitz. Combinatorial criteria for uniqueness of the Gibbs measure. Random Structures Algorithms 27 (2005), no. 4, 445--475. Math. Review 2006k:82036
- C. C. Wu. Ising models on Hyperbolic Graphs. J. Stat. Phys. 85 (1997), no. 1-2, 251--259. Math. Review 98a:82028
- C. C. Wu. Ising models on Hyperbolic Graphs II. J. Statist. Phys. 100 (2000), no. 5-6, 893--904. Math. Review 2002h:82027
This work is licensed under a Creative Commons Attribution 3.0 License.