Home | Contents | Submissions, editors, etc. | Login | Search | ECP
 Electronic Journal of Probability > Vol. 13 (2008) > Paper 65 open journal systems 


Glauber dynamics on nonamenable graphs: boundary conditions and mixing time

Alessandra Bianchi, Weierstrass Institute for Applied Analysis and Stochastics (WIAS)


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: PDF

Pages: 1980-2012

Published on: November 11, 2008
Bibliography
  1. 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
  2. T. Bodineau. Translation invariant Gibbs states for the Ising model. Probab. Theory Related Fields 135 (2006), no. 2, 153--168. Math. Review 2007b:82007
  3. 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.
  4. 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
  5. 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
  6. 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
  7. I. Benjamini, O. Schramm. Percolation in the hyperbolic plane. J. Amer. Math. Soc. 14 (2001), no. 2, 487--507. Math. Review 2002h:82049
  8. 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
  9. D. Fisher, D. Huse. Dynamics of droplet fluctuations in pure and random Ising systems. Phys. Rev. B 35 (1987), no.13, 6841--6846.
  10. H.-O. Georgii. Gibbs measures and Phase Transitions. de Gruyter Studies in Mathematics, 9. Walter de Gruyter & Co., Berlin, 1988 . Math. Review 89k:82010
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. H. Kesten. Percolation theory for mathematicians. Progr. Probab. Statist. 2. Birkhäuser, Boston, Mass., 1982. Math. Review 84i:60145
  17. 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.
  18. 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
  19. 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
  20. R. Lyons. Phase transitions on Nonamenable Graphs. J. Math. Phys. 41 (2000), no.3, 1099--1126. Math. Review 2001c:82028
  21. 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
  22. W. Magnus. Noneuclidean tesselations and their groups. Pure and Applied Mathematics, Vol. 61. Academic Press, New York-London, 1974. . Math. Review 50 #4774
  23. 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
  24. 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
  25. 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
  26. 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
  27. R. Rietman, B. Nienhuis, J. Oitmaa. Ising model on hyperlattices. J. Phys. A 25 (1992), no. 24, 6577-6592. Math. Review 94e:82026
  28. 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
  29. 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
  30. 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
  31. 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
  32. D. Weitz. Combinatorial criteria for uniqueness of the Gibbs measure. Random Structures Algorithms 27 (2005), no. 4, 445--475. Math. Review 2006k:82036
  33. C. C. Wu. Ising models on Hyperbolic Graphs. J. Stat. Phys. 85 (1997), no. 1-2, 251--259. Math. Review 98a:82028
  34. C. C. Wu. Ising models on Hyperbolic Graphs II. J. Statist. Phys. 100 (2000), no. 5-6, 893--904. Math. Review 2002h:82027
















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | ECP

Electronic Journal of Probability. ISSN: 1083-6489