Skip to main content
SpringerLink
Log in

Relaxation Times of Markov Chains in Statistical Mechanics and Combinatorial Structures

  • Chapter
Probability on Discrete Structures

Part of the book series: Encyclopaedia of Mathematical Sciences ((EMS,volume 110))

Abstract

In Markov chain Monte Carlo theory a particular Markov chain is run for a very long time until its distribution is close enough to the equilibrium measure. In recent years, for models of statistical mechanics and of theoretical computer science, there has been a flourishing of new mathematical ideas and techniques to rigorously control the time it takes for the chain to equilibrate. This has provided a fruitful interaction between the two fields and the purpose of this paper is to provide a comprehensive review of the state of the art.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD 109.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. M. Aizenman and R. Holley. Rapid convergence to equilibrium of stochastic Ising models in the Dobrushin Shlosman regime. In Percolation theory and ergodic theory of infinite particle systems (Minneapolis, Minn., 1984–1985), pages 1–11. Springer, New York, 1987.

    Google Scholar 

  2. F. C. Alcaraz, S. R. Salinas, and W. F. Wreszinski. Quantum domains in ferromagnetic anisotropic Heisenberg chains. In Statistical models, Yang-Baxter equation and related topics, and Symmetry, statistical mechanical models and applications (Tianjin, 1995), pages 13–19. World Sci. Publishing, River Edge, NJ, 1996.

    Google Scholar 

  3. F. C. Alcaraz. Exact steady states of asymmetric diffusion and two-species annihilation with back reaction from the ground state of quantum spin models. Internat. J. Modern Phys. B, 8(25–26):3449–3461, 1994. Perspectives on solvable models.

    Google Scholar 

  4. A. Aldous and J. Fill. Reversible Markov chains and random walks on graphs. available at http://stat-www.berkeley.edu/users/adous/book.html.

  5. D. Aldous. Random walks on finite groups and rapidly mixing Markov chains. In Seminar on probability, XVII, pages 243–297. Springer, Berlin, 1983.

    Google Scholar 

  6. D. Aldous, L. Lovész, and P. Winkler. Mixing times for uniformly ergodic Markov chains. Stochastic Process. Appl., 71 (2): 165–185, 1997.

    MathSciNet  MATH  Google Scholar 

  7. K. S. Alexander. On weak mixing in lattice models. Probab. Theory Related Fields, 110 (4): 441–471, 1998.

    MathSciNet  MATH  Google Scholar 

  8. K. S. Alexander. Mixing properties and exponential decay for lattice systems in finite volumes. Preprint, 2001.

    Google Scholar 

  9. K. S. Alexander. The spectral gap of the 2-D stochastic Ising model with nearly single-spin boundary conditions. J. Statist. Phys., 104 (1–2): 59–87, 2001.

    MathSciNet  MATH  Google Scholar 

  10. K. S. Alexander and N. Yoshida. The spectral gap of the 2-D stochastic Ising model with mixed boundary conditions. J. Statist. Phys., 104 (1–2): 89–109, 2001.

    MathSciNet  MATH  Google Scholar 

  11. N. Alon. Eigenvalues and expanders. Combinatorica, 6(2):83–96, 1986. Theory of computing ( Singer Island, Fla., 1984 ).

    Google Scholar 

  12. N. Alon and V. D. Milman Ai, isoperimetric inequalities for graphs, and superconcentrators. J. Combin. Theory Ser. B, 38 (1): 73–88, 1985.

    MathSciNet  MATH  Google Scholar 

  13. C. Ané, S. Blachère, D. Chafaï, P. Fougères, I. Gentil, F. Malrieu, C. Roberto, and G. Scheffer. Sur les inégalités de Sobolev logarithmiques. Société Mathématique de France, Paris, 2000. With a preface by Dominique Bakry and Michel Ledoux.

    Google Scholar 

  14. I. Benjamini, N. Berger, C. Hoffman, and E. Mossel. Mixing time for biased shuffling. Preprint, 2002.

    Google Scholar 

  15. I. Benjamini and E. Mossel. On the mixing time of a simple random walk on the super critical percolation cluster. Preprint, 2002.

    Google Scholar 

  16. L. Bertini, N. Cancrini, and F. Cesi. The spectral gap for a Glauber-type dynamics in a continuous gas. Ann. Inst. H. Poincaré Probab. Statist., 38 (1): 91–108, 2002.

    MathSciNet  MATH  Google Scholar 

  17. L. Bertini and B. Zegarlinski. Coercive inequalities for Kawasaki dynamics. The product case. Markov Process. Related Fields, 5 (2): 125–162, 1999.

    MathSciNet  MATH  Google Scholar 

  18. L. Bertini, E. N. M. Cirillo, and E. Olivieri. Renormalization-group transformations under strong mixing conditions: Gibbsianness and convergence of renormalized interactions. J. Statist. Phys., 97 (5–6): 831–915, 1999.

    MathSciNet  Google Scholar 

  19. T. Bodineau and B. Helfer. The log-Sobolev inequality for unbounded spin systems. J. Funct. Anal., 166 (1): 168–178, 1999.

    MathSciNet  MATH  Google Scholar 

  20. T. Bodineau, D. Ioffe, and Y. Velenik. Rigorous probabilistic analysis of equilibrium crystal shapes. J. Math. Phys., 41 (3): 1033–1098, 2000.

    MathSciNet  MATH  Google Scholar 

  21. T. Bodineau and F. Martinelli. Some new results on the kinetic ising model in a pure phase. Journal of Stat. Phys., 109 (1), 2002.

    Google Scholar 

  22. O. Bolina, P. Contucci, and B. Nachtergaele. Path integral representation for interface states of the anisotropic Heisenberg model. Rev. Math. Phys., 12 (10): 1325–1344, 2000.

    MathSciNet  MATH  Google Scholar 

  23. O. Bolina, P. Contucci, B. Nachtergaele, and S. Starr. Finite-volume excitations of the 111 interface in the quantum XXZ model. Comm. Math. Phys., 212 (1): 63–91, 2000.

    MathSciNet  MATH  Google Scholar 

  24. C. Borgs, J. T. Chayes, A. Frieze, J. H. Kim, P. Tetali, E. Vigoda, and V. H. Vu. Torpid mixing of some Monte Carlo Markov chains algorithms in statistical mechanics. 40th Annual Symposium on Foundations of Computer Science, IEEE, Los Alimitos, 1999.

    Google Scholar 

  25. A. Bovier and P. Picco, editors. Mathematical aspects of spin glasses and neural networks. Birkhäuser Boston Inc., Boston, MA, 1998.

    Google Scholar 

  26. R. Bubley and M. Dyer. Path coupling: A technique for proving rapid mixing in Markov chains. 38th Symposium on Foundations of Computer Science, 1997.

    Google Scholar 

  27. N. Cancrini, F. Cesi, and F. Martinelli. The spectral gap for the Kawasaki dynamics at low temperature. J. Statist. Phys., 95 (1–2): 215–271, 1999.

    MathSciNet  MATH  Google Scholar 

  28. N. Cancrini, F. Cesi, and C. Roberto. Private communication.

    Google Scholar 

  29. N. Cancrini and F. Martinelli. Comparison of finite volume canonical and grand canonical Gibbs measures under a mixing condition. Markov Process. Related Fields, 6 (1): 23–72, 2000.

    MathSciNet  MATH  Google Scholar 

  30. N. Cancrini and F. Martinelli. On the spectral gap of Kawasaki dynamics under a mixing condition revisited. J. Math. Phys., 41(3):1391–1423, 2000. Probabilistic techniques in equilibrium and nonequilibrium statistical physics.

    Google Scholar 

  31. N. Cancrini and F. Martinelli. Diffusive scaling of the spectral gap for the dilute Ising lattice-gas dynamics below the percolation threshold. Probab. Theory Related Fields, 120 (4): 497–534, 2001.

    MathSciNet  MATH  Google Scholar 

  32. N. Cancrini, F. Martinelli, and C. Roberto. The logarithmic Sobolev constant of Kawasaki dynamics under a mixing condition revisited. Ann. Inst. H. Poincaré Probab. Statist., 38 (4): 385–436, 2002.

    MathSciNet  MATH  Google Scholar 

  33. P. Caputo. Uniform Poincaré inequalities for unbounded conservative spin systems: the non interacting case. Preprint, 2002.

    Google Scholar 

  34. P. Caputo and F. Martinelli. Relaxation time of anisotropic simple exclusion processes and quantum Heisenberg models. Ann. Appl. Prob., vol. 13, No 2, 2003.

    Google Scholar 

  35. P. Caputo and F. Martinelli. Asymmetric diffusion and the energy gap above the 111 ground state of the quantum XXZ model. Comm. Math. Phys., 226 (2): 323–375, 2002.

    MathSciNet  MATH  Google Scholar 

  36. E. Carlen, M. C. Caravalho, and M. Loss. Determination of the spectral gap for Kac’s master equation and related stochastic evolutions. Preprint, 2002.

    Google Scholar 

  37. F. Cesi, G. Guadagni, F. Martinelli, and R. H. Schonmann On the two-dimensional stochastic Ising model in the phase coexistence region near the critical point. J. Statist. Phys., 85 (1–2): 55–102, 1996.

    MathSciNet  MATH  Google Scholar 

  38. F. Cesi, C. Maes, and F. Martinelli. Relaxation of disordered magnets in the Griffiths’ regime. Comm. Math. Phys., 188 (1): 135–173, 1997.

    MathSciNet  MATH  Google Scholar 

  39. F. Cesi, C. Maes, and F. Martinelli. Relaxation to equilibrium for two-dimensional disordered Ising systems in the Griffiths phase. Comm. Math. Phys., 189 (2): 323–335, 1997.

    MathSciNet  MATH  Google Scholar 

  40. F. Cesi. Quasi-factorization of the entropy and logarithmic Sobolev inequalities for Gibbs random fields. Probab. Theory Related Fields, 120 (4): 569–584, 2001.

    MathSciNet  MATH  Google Scholar 

  41. F. Cesi and F. Martinelli. On the layering transition of an SOS surface interacting with a wall. I. Equilibrium results. J. Statist. Phys., 82 (3–4): 823–913, 1996.

    MathSciNet  MATH  Google Scholar 

  42. F. Cesi and F. Martinelli. On the layering transition of an SOS surface interacting with a wall. II. The Glauber dynamics. Comm. Math. Phys.,177(1):173201, 1996.

    Google Scholar 

  43. L. Chayes, R. H. Schonmann, and G. Swindle. Lifshitz’ law for the volume of a two-dimensional droplet at zero temperature. J. Statist. Phys., 79 (5–6): 821–831, 1995.

    MathSciNet  MATH  Google Scholar 

  44. J. Cheeger. A lower bound for the smallest eigenvalue of the Laplacian. In Problems in analysis (Papers dedicated to Salomon Bochner, 1969), pages 195–199. Princeton Univ. Press, Princeton, NJ, 1970.

    Google Scholar 

  45. C. Cooper and A. M. Frieze. Mixing properties of the Swendsen-Wang process on classes of graphs. Random Structures Algorithms, 15(3–4):242–261, 1999. Statistical physics methods in discrete probability, combinatorics, and theoretical computer science ( Princeton, NJ, 1997 ).

    Google Scholar 

  46. B. Derrida. Random energy model: Limit of a family of disordered models. Phys. Rev. Lett., 45: 79–82, 1980.

    MathSciNet  Google Scholar 

  47. P. Diaconis and L. Saloff-Coste. Logarithmic Sobolev inequalities for finite Markov chains. Ann. Appl. Probab., 6 (3): 695–750, 1996.

    MathSciNet  MATH  Google Scholar 

  48. P. Diaconis and L. Saloff-Coste. Comparison theorems for reversible Markov chains. Ann. Appl. Probab., 3 (3): 696–730, 1993.

    MathSciNet  MATH  Google Scholar 

  49. P. Diaconis and L. Saloff-Coste. Bounds for Kac’s master equation. Comm. Math. Phys., 209 (3): 729–755, 2000.

    MathSciNet  MATH  Google Scholar 

  50. P. Diaconis and M. Shahshahani. Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Gebiete, 57 (2): 159–179, 1981.

    MathSciNet  MATH  Google Scholar 

  51. P. Diaconis and M. Shahshahani. Time to reach stationarity in the Bernoulli-Laplace diffusion model. SIAM J. Math. Anal., 18 (1): 208–218, 1987.

    MathSciNet  MATH  Google Scholar 

  52. P. Diaconis and D. Stroock. Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Probab., 1 (1): 36–61, 1991.

    MathSciNet  MATH  Google Scholar 

  53. R. L. Dobrushin. The problem of uniqueness of a Gibbsian random field and the problem of phase transitions. Funkcional. Anal. i Prilozen., 2 (4): 44–57, 1968.

    MathSciNet  Google Scholar 

  54. R. L. Dobrushin. Prescribing a system of random variables by conditional distributions. Theory of Prob. Appl., 15: 453–486, 1970.

    Google Scholar 

  55. R. L. Dobrushin and S. B. Shlosman. Constructive criterion for the uniqueness of Gibbs field. In Statistical physics and dynamical systems (Köszeg, 1984), pages 347–370. Birkhäuser Boston, Boston, MA, 1985.

    Google Scholar 

  56. R. L. Dobrushin and S. B. Shlosman. Completely analytical Gibbs fields. Stat. Phys. and Dyn. Systems, 46 (5–6): 983–1014, 1987.

    MathSciNet  MATH  Google Scholar 

  57. R. L. Dobrushin and S. B. Shlosman. Completely analytical interactions: constructive description. J. Statist. Phys., 46 (5–6): 983–1014, 1987.

    MathSciNet  MATH  Google Scholar 

  58. M. Dyer, A. Sinclair, E. Vigoda, and D. Weitz. Mixing in time and space for lattice spin systems: a combinatorial view. Preprint, 2002.

    Google Scholar 

  59. M. Dyer and C. Greenhill. On Markov chains for independent sets. J. Algorithms, 35 (1): 17–49, 2000.

    MathSciNet  MATH  Google Scholar 

  60. M. E. Dyer, A. M. Frieze, and M. R. Jerrum. On counting independent sets in sparse graphs. 40th Annual Symposium on Foundations of Computer Science, IEEE, Los Alimitos, pages 210–217, 1999.

    Google Scholar 

  61. R. G. Edwards and A. D. Sokal. Generalization of the Fortuin-KasteleynSwendsen-Wang representation and Monte Carlo algorithm. Phys. Rev. D (3), 38 (6): 2009–2012, 1988.

    MathSciNet  Google Scholar 

  62. D. Fisher and D. Huse. Dynamics of droplet fluctuation in pure and random Ising systems. Phys. Rev. B, 35 (13), 1987.

    Google Scholar 

  63. L. R. G. Fontes, M. Isopi, Y. Kohayakawa, and P. Picco. The spectral gap of the REM under Metropolis dynamics. Ann. Appl. Probab., 8 (3): 917–943, 1998.

    MathSciNet  MATH  Google Scholar 

  64. R. Fontes, R. H. Schonmann, and V. Sidoravicius. Stretched exponential fixation in stochastic ising models at zero temperature. Preprint, 2001.

    Google Scholar 

  65. C. M. Fortuin and P. W. Kasteleyn. On the random-cluster model. I. Introduction and relation to other models. Physica, 57: 536–564, 1972.

    MathSciNet  Google Scholar 

  66. J. Fröhlich. Mathematical aspects of the physics of disordered systems. In Phénomènes critiques, systèmes aléatoires, théories de jauge, Part I, II (Les Houches, 1984), pages 725–893. North-Holland, Amsterdam, 1986. With the collaboration of A. Bovier and U. Glans.

    Google Scholar 

  67. D. Galvin and J. Kahn. On phase transition in the hard-core model on Z d. Preprint, 2002.

    Google Scholar 

  68. F. Gao and J. Quastel. Exponential decay of entropy in the random transposition and Bernoulli-Laplace models. Preprint, 2002.

    Google Scholar 

  69. H.-O. Georgii. Gibbs measures and phase transitions. Walter de Gruyter & Co., Berlin, 1988.

    MATH  Google Scholar 

  70. V. K. Gore and M. R. Jerrum. The Swendsen-Wang process does not always mix rapidly. J. Statist. Phys., 97 (1–2): 67–86, 1999.

    MathSciNet  MATH  Google Scholar 

  71. R. Griffiths. Non-analytic behaviour above the critical point in a random Ising ferromagnet. Phys. Rev. Lett., 23: 17, 1969.

    Google Scholar 

  72. G. Grimmett. Percolation and disordered systems. In Lectures on probability theory and statistics (Saint-Flour, 1996), pages 153–300. Springer, Berlin, 1997.

    Google Scholar 

  73. L. Gross. Logarithmic Sobolev inequalities. Amer. J. Math., 97 (4): 1061–1083, 1975.

    MathSciNet  Google Scholar 

  74. A. Guionnet and B. Zegarlinski. Lectures on logarithmic Sobolev inequalities. Volume XXXVI of the Seminaire de Probabilité, Springer Lecture Notes in Mathematics, pages 1–134, 2000.

    Google Scholar 

  75. A. Guionnet and B. Zegarlinski. Decay to equilibrium in random spin systems on a lattice. Comm. Math. Phys., 181 (3): 703–732, 1996.

    MathSciNet  MATH  Google Scholar 

  76. A. Guionnet and B. Zegarlinski. Decay to equilibrium in random spin systems on a lattice. II. J. Statist. Phys., 86 (3–4): 899–904, 1997.

    MathSciNet  MATH  Google Scholar 

  77. Y. Higuchi and J. Wang. Spectral gap of Ising model for Dobrushin’s boundary condition in two dimension. Preprint, 1999.

    Google Scholar 

  78. Y. Higuchi and N. Yoshida. Slow relaxation of 2-D stochastic Ising models with random and non-random boundary conditions. In New trends in stochastic analysis (Charingworth, 1994), pages 153–167. World Sci. Publishing, River Edge, NJ, 1997.

    Google Scholar 

  79. R. A. Holley and D. W. Stroock. In one and two dimensions, every stationary measure for a stochastic Ising model is a Gibbs state. Comm. Math. Phys., 55(1):37–45, 1977.

    MathSciNet  Google Scholar 

  80. R. Holley. Possible rates of convergence in finite range, attractive spin systems. In Particle systems, random media and large deviations (Brunswick, Maine, 1984), pages 215–234. Amer. Math. Soc., Providence, RI, 1985.

    Google Scholar 

  81. R. Holley. On the asymptotics of the spin-spin autocorrelation function in stochastic Ising models near the critical temperature. In Spatial stochastic processes, pages 89–104. Birkhäuser Boston, Boston, MA, 1991.

    Google Scholar 

  82. R. Holley. The one-dimensional stochastic X-Y model. In Random walks, Brownian motion, and interacting particle systems, pages 295–307. Birkhauser Boston, Boston, MA, 1991.

    Google Scholar 

  83. R. Holley. Rapid convergence to equilibrium in ferromagnetic stochastic Ising models. Resenhas, 1(2–3):131–149, 1994. Fifth Latin American Congress of Probability and Mathematical Statistics (Portuguese) (Sao Paulo, 1993).

    Google Scholar 

  84. R. Holley and D. Stroock. Logarithmic Sobolev inequalities and stochastic Ising models. J. Statist. Phys., 46 (5–6): 1159–1194, 1987.

    MathSciNet  MATH  Google Scholar 

  85. R. A. Holley and D. W. Stroock. Uniform and L2 convergence in one-dimensional stochastic Ising models. Comm. Math. Phys., 123 (1): 85–93, 1989.

    MathSciNet  MATH  Google Scholar 

  86. M. Huber. Efficient exact sampling from the Ising model using SwendsenWang. Preprint, 2000.

    Google Scholar 

  87. E. J. Janse van Rensburg. Collapsing and adsorbing polygons. J. Phys. A, 31 (41): 8295–8306, 1998.

    MathSciNet  MATH  Google Scholar 

  88. E. Janvresse, C. Landim, J. Quastel, and H. T. Yau. Relaxation to equilibrium of conservative dynamics. I. Zero-range processes. Ann. Probab., 27 (1): 325–360, 1999.

    MathSciNet  MATH  Google Scholar 

  89. E. Janvresse. Spectral gap for Kac’s model of Boltzmann equation. Ann. Probab., 29 (1): 288–304, 2001.

    MathSciNet  MATH  Google Scholar 

  90. M. Jerrum. Mathematical foundations of the Markov chain Monte Carlo method. In Probabilistic methods for algorithmic discrete mathematics, pages 116–165. Springer, Berlin, 1998.

    Google Scholar 

  91. M. Jerrum and A. Sinclair. Approximating the permanent. SIAM J. Comput., 18 (6): 1149–1178, 1989.

    MathSciNet  MATH  Google Scholar 

  92. M. Jerrum and A. Sinclair. Polynomial-time approximation algorithms for the Ising model. SIAM J. Comput., 22 (5): 1087–1116, 1993.

    MathSciNet  MATH  Google Scholar 

  93. M. Kac. Foundations of kinetic theory. In Proceedings of the Third Berkeley Symposium on Mathematical Statistics and Probability, 1954–1955, vol. III, pages 171–197, Berkeley and Los Angeles, 1956.. University of California Press.

    Google Scholar 

  94. C. Kenyon, E. Mossel, and Y. Peres. Glauber dynamics on trees and hyperbolic graphs. In IEEE Symposium on Foundations of Computer Science, pages 568–578, 2001.

    Google Scholar 

  95. C. Kipnis and C. Landim. Scaling limits of interacting particle systems. Springer-Verlag, Berlin, 1999.

    MATH  Google Scholar 

  96. T. Koma, B. Nachtergaele, and S. Starr. The spectral gap of the ferromagnetic spin-j XXZ chain. Preprint, 2001.

    Google Scholar 

  97. T. Koma and B. Nachtergaele. The spectral gap of the ferromagnetic XXZ chain. Lett. Math. Phys., 40 (1): 1–16, 1997.

    MathSciNet  MATH  Google Scholar 

  98. R. Koteckÿ. unpublished. Cited in [69]. pp. 148–149, 457.

    Google Scholar 

  99. R. Koteckÿ and S. B. Shlosman. First-order phase transitions in large entropy lattice models. Comm. Math. Phys., 83 (4): 493–515, 1982.

    MathSciNet  Google Scholar 

  100. C. Landim, G. Panizo, and H. T. Yau. Spectral gap and logarithmic Sobolev inequality for unbounded conservative spin systems. To appear in Annales de l’Institut Henri Poincaré. Probabilités et Statistiques, 38 (5): 739–777, 2002.

    MathSciNet  MATH  Google Scholar 

  101. C. Landim, S. Sethuraman, and S. Varadhan Spectral gap for zero-range dynamics. Ann. Probab., 24 (4): 1871–1902, 1996.

    MathSciNet  MATH  Google Scholar 

  102. G. F. Lawler and A. D. Sokal. Bounds on the L2 spectrum for Markov chains and Markov processes: a generalization of Cheeger’s inequality. Trans. Amer. Math. Soc., 309 (2): 557–580, 1988.

    MathSciNet  MATH  Google Scholar 

  103. M. Ledoux. Logarithmic Sobolev inequalities for unbounded spin systems revisited. In Séminaire de Probabilités, XXXV, pages 167–194. Springer, Berlin, 2001.

    Google Scholar 

  104. T.-Y. Lee and H.-T. Yau. Logarithmic Sobolev inequality for some models of random walks. Ann. Probab., 26(4): 1855–1873, 1998.

    Google Scholar 

  105. T. M. Liggett. Interacting particle systems. Springer-Verlag, New York, 1985.

    MATH  Google Scholar 

  106. L. Lova,sz and R. Kannan. Faster mixing via average conductance. In Annual ACM Symposium on Theory of Computing (Atlanta, GA, 1999), pages 282–287 (electronic). ACM, New York, 1999.

    Google Scholar 

  107. L. Lovasz and P. Winkler. Mixing times. In Microsurveys in discrete probability (Princeton, NJ, 1997), pages 85–133. Amer. Math. Soc., Providence, RI, 1998.

    Google Scholar 

  108. S. L. Lu and H.-T. Yau. Spectral gap and logarithmic Sobolev inequality for Kawasaki and Glauber dynamics. Comm. Math. Phys., 156 (2): 399–433, 1993.

    MathSciNet  MATH  Google Scholar 

  109. M. Luby, D. Randall, and A. Sinclair. Markov chain algorithms for planar lattice structures. SIAM J. Comput., 31(1): 167–192 (electronic), 2001.

    Google Scholar 

  110. M. Luby and E. Vigoda. Fast convergence of the Glauber dynamics for sampling independent sets. Random Structures Algorithms, 15(3–4):229–241, 1999. Statistical physics methods in discrete probability, combinatorics, and theoretical computer science ( Princeton, NJ, 1997 ).

    Google Scholar 

  111. N. Madras and D. Randall. Markov chain decomposition for convergence rate analysis. Ann. Appl. Probability, 12: 581–606, 2002.

    MathSciNet  MATH  Google Scholar 

  112. E. Marcelli and F. Martinelli. Some new results on the two-dimensional kinetic Ising model in the phase coexistence region. J. Statist. Phys., 84 (3–4): 655–696, 1996.

    MathSciNet  MATH  Google Scholar 

  113. F. Martinelli. On the two-dimensional dynamical Ising model in the phase coexistence region. J. Statist. Phys., 76 (5–6): 1179–1246, 1994.

    MathSciNet  MATH  Google Scholar 

  114. F. Martinelli. An elementary approach to finite size conditions for the exponential decay of covariances in lattice spin models. In On Dobrushin’s way. From probability theory to statistical physics, pages 169–181. Amer. Math. Soc., Providence, RI, 2000.

    Google Scholar 

  115. F. Martinelli and E. Olivieri. Some remarks on pathologies of renormalizationgroup transformations for the Ising model. J. Statist. Phys., 72 (5–6): 1169–1177, 1993.

    MathSciNet  MATH  Google Scholar 

  116. F. Martinelli and E. Olivieri. Approach to equilibrium of Glauber dynamics in the one phase region. I. The attractive case. Comm. Math. Phys.,161(3):447486, 1994.

    Google Scholar 

  117. F. Martinelli and E. Olivieri. Approach to equilibrium of Glauber dynamics in the one phase region. II. The general case. Comm. Math. Phys.,161(3):487514, 1994.

    Google Scholar 

  118. F. Martinelli and E. Olivieri. Instability of renormalization-group pathologies under decimation. J. Statist. Phys., 79 (1–2): 25–42, 1995.

    MathSciNet  MATH  Google Scholar 

  119. F. Martinelli, E. Olivieri, and R. H. Schonmann For 2-D lattice spin systems weak mixing implies strong mixing. Comm. Math. Phys., 165 (1): 33–47, 1994.

    MathSciNet  MATH  Google Scholar 

  120. F. Martinelli. Dynamical analysis of low-temperature Monte Carlo cluster algorithms J. Statist. Phys., 66 (5–6): 1245–1276, 1992.

    MathSciNet  MATH  Google Scholar 

  121. F. Martinelli. Lectures on Glauber dynamics for discrete spin models. In Lectures on probability theory and statistics (Saint-Flour, 1997), pages 93–191. Springer, Berlin, 1999.

    Google Scholar 

  122. F. Martinelli, E. Olivieri, and E. Scoppola. On the Swendsen-Wang dynamics. I. Exponential convergence to equilibrium. J. Statist. Phys., 62 (1–2): 117–133, 1991.

    MathSciNet  MATH  Google Scholar 

  123. F. Martinelli, E. Olivieri, and E. Scoppola. On the Swendsen-Wang dynamics. II. Critical droplets and homogeneous nucleation at low temperature for the two-dimensional Ising model. J. Statist. Phys., 62 (1–2): 135–159, 1991.

    MathSciNet  MATH  Google Scholar 

  124. P. Mathieu. Hitting times and spectral gap inequalities. Ann. Inst. H. Poincaré Probab. Statist., 33 (4): 437–465, 1997.

    MathSciNet  MATH  Google Scholar 

  125. P. Mathieu. Convergence to equilibrium for spin glasses. Comm. Math. Phys., 215 (1): 57–68, 2000.

    MathSciNet  MATH  Google Scholar 

  126. B. Morris and Y. Peres. Evolving sets and mixing. Preprint, 2002.

    Google Scholar 

  127. B. Nachtergaele. Interfaces and droplets in quantum lattice models. In XIIIth International Congress on Mathematical Physics (London, 2000), pages 243249. Int. Press, Boston, MA, 2001.

    Google Scholar 

  128. Charles M. Newman. Disordered Ising systems and random cluster representations. In Probability and phase transition (Cambridge, 1993), pages 247–260. Kluwer Acad. Publ., Dordrecht, 1994.

    Google Scholar 

  129. E. Olivieri. On a cluster expansion for lattice spin systems: a finite-size condition for the convergence. J. Statist. Phys., 50 (5–6): 1179–1200, 1988.

    MathSciNet  MATH  Google Scholar 

  130. E. Olivieri and P. Picco. Cluster expansion for d-dimensional lattice systems and finite-volume factorization properties. J. Statist. Phys., 59 (1–2): 221–256, 1990.

    MathSciNet  MATH  Google Scholar 

  131. Y. Peres and P. Winkler. private communication.

    Google Scholar 

  132. G. Posta. Spectral gap for an unrestricted Kawasaki type dynamics. ESAIM Probab. Statist.,1:145–181 (electronic), 1995/97.

    Google Scholar 

  133. R. B. Potts. Some generalized order-disorder transformations. Proceedings of the Cambridge Phisolophical Society, 48, 1952.

    Google Scholar 

  134. D. Randall and R. A. Martin. Sampling adsorbing staircase walks using a new Markov chain decomposition method. Symposium on Foundations of Computer Science (FOCS), pages 492–502, 2000.

    Google Scholar 

  135. D. Randall and P. Tetali. Analyzing Glauber dynamics by comparison of Markov chains. J. Math. Phys., 41(3):1598–1615, 2000. Probabilistic techniques in equilibrium and nonequilibrium statistical physics.

    Google Scholar 

  136. D. Ruelle. Statistical mechanics: Rigorous results. W. A. Benjamin, Inc., New York-Amsterdam, 1969.

    Google Scholar 

  137. J. Salas and A. D. Sokal. Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem. J. Statist. Phys., 86 (3–4): 551–579, 1997.

    MathSciNet  MATH  Google Scholar 

  138. J. Salas and A. D. Sokal. The three-state square-lattice Potts antiferromagnet at zero temperature. J. Statist. Phys., 92 (5–6): 729–753, 1998.

    MathSciNet  MATH  Google Scholar 

  139. L. Saloff-Coste. Lectures on finite Markov chains. In Lectures on probability theory and statistics (Saint-Flour, 1996), pages 301–413. Springer, Berlin, 1997.

    Google Scholar 

  140. R. H. Schonmann. Slow droplet-driven relaxation of stochastic Ising models in the vicinity of the phase coexistence region. Comm. Math. Phys., 161 (1): 1–49, 1994.

    MathSciNet  MATH  Google Scholar 

  141. R. H. Schonmann and N. Yoshida. Exponential relaxation of Glauber dynamics with some special boundary conditions. Comm. Math. Phys., 189 (2): 299–309, 1997.

    MathSciNet  MATH  Google Scholar 

  142. D. Sherrington and S. Kirkpatrick. Solvable model of a spin glass. Phys. Rev. Lett., 35: 1792–1796, 1972.

    Google Scholar 

  143. S. B. Shlosman. The droplet in the tube: a case of phase transition in the canonical ensemble. Comm. Math. Phys., 125 (1): 81–90, 1989.

    MathSciNet  MATH  Google Scholar 

  144. B. Simon. The statistical mechanics of lattice gases. Vol. I. Princeton University Press, Princeton, NJ, 1993.

    MATH  Google Scholar 

  145. A. Sinclair. Improved bounds for mixing rates of Markov chains and multi-commodity flow. Combin. Probab. Comput., 1 (4): 351–370, 1992.

    MathSciNet  MATH  Google Scholar 

  146. A. Sinclair Algorithms for random generation and counting. Birkhäuser Boston Inc., Boston, MA, 1993. A Markov cha in approach.

    Google Scholar 

  147. A. Sinclair and M. Jerrum. Approximate counting, uniform generation and rapidly mixing Markov chains. Inform. and Comput., 82 (1): 93–133, 1989.

    MathSciNet  MATH  Google Scholar 

  148. A. Sokal. Monte Carlo methods in statistical mechanics: foundations and new algorithms. In Functional integration (Cargese, 1996), pages 131–192. Plenum, New York, 1997.

    Google Scholar 

  149. A. Sokal. A personal list of unsolved problems concerning lattice gases and antiferromagnetic potts models. Preprint, 2000.

    Google Scholar 

  150. H. Spohn. Interface motion in models with stochastic dynamics. J. Statist. Phys., 71 (2): 389–462, 1998.

    Google Scholar 

  151. S. Starr. Some properties of the low lying spectrum of the ferromagnetic quantum xxz Heisenberg model. http://front.math.ucdavis.edu/math-ph/0106024, pages 106–109, Ph.D thesis 2001.

    Google Scholar 

  152. D. Stroock and B. Zegarlinski. On the ergodic properties of Glauber dynamics. J. Statist. Phys., 81 (5–6): 1007–1019, 1995.

    MathSciNet  MATH  Google Scholar 

  153. D. W. Stroock. Logarithmic Sobolev inequalities for Gibbs states. In Dirichlet forms (Varenna, 1992), pages 194–228. Springer, Berlin, 1993.

    Google Scholar 

  154. D. W. Stroock and B. Zegarlinski. The equivalence of the logarithmic Sobolev inequality and the Dobrushin-Shlosman mixing condition. Comm. Math. Phys., 144 (2): 303–323, 1992.

    MathSciNet  MATH  Google Scholar 

  155. D. W. Stroock and B. Zegarlinski. The logarithmic Sobolev inequality for continuous spin systems on a lattice. J. Funct. Anal., 104 (2): 299–326, 1992.

    MathSciNet  MATH  Google Scholar 

  156. D. W. Stroock and B. Zegarlinski. The logarithmic Sobolev inequality for discrete spin systems on a lattice. Comm. Math. Phys., 149 (1): 175–193, 1992.

    MathSciNet  MATH  Google Scholar 

  157. N. Sugimine. A lower bound on the spectral gap of the 3-dimensional stochastic Ising models. Preprint, 2002.

    Google Scholar 

  158. L. E. Thomas. Bound on the mass gap for a stochastic contour model at low temperature. J. Math. Phys., 30 (9): 2028–2034, 1989.

    MathSciNet  MATH  Google Scholar 

  159. J. van den Berg and C. Maes. Disagreement percolation in the study of Markov fields. Ann. Probab., 22(2): 749–763, 1994.

    Google Scholar 

  160. A. C. D. van Enter, R. Fernandez, and A. D. Sokal. Regularity properties and pathologies of position-space renormalization-group transformations: scope and limitations of Gibbsian theory. J. Statist. Phys., 72 (5–6): 879–1167, 1993.

    MathSciNet  MATH  Google Scholar 

  161. B. van Rensburg. Adsorbing staircase walks and staircase polygons. Ann. Comb., 3(2–4):451–473, 1999. On combinatorics and statistical mechanics.

    Google Scholar 

  162. S. R. S. Varadhan and H.-T. Yau. Diffusive limit of lattice gas with mixing conditions. Asian J. Math., 1 (4): 623–678, 1997.

    MathSciNet  MATH  Google Scholar 

  163. E. Vigoda. Improved bounds for sampling colorings. J. Math. Phys., 41(3):1555–1569, 2000. Probabilistic techniques in equilibrium and nonequilibrium statistical physics.

    Google Scholar 

  164. E. Vigoda. A note on the Glauber dynamics for sampling independent sets. Electron. J. Cornbin., 8(1):Research Paper 8, 8 pp. (electronic), 2001.

    Google Scholar 

  165. J.-S. Wang and R. H. Swendsen. Non universal critical dynamics in Monte Carlo simulations. Phys. Rev. Lett., 58: 86–88, 1987.

    Google Scholar 

  166. D. Weitz. Combinatorial conditions for uniqueness of the Gibbs measure. Preprint, 2002.

    Google Scholar 

  167. D. B. Wilson. Mixing times of lozenge tilings and card shuffling Markov chains. Preprint, 1997.

    Google Scholar 

  168. H.-T. Yau. Logarithmic Sobolev inequality for lattice gases with mixing conditions. Comm. Math. Phys., 181 (2): 367–408, 1996.

    MathSciNet  MATH  Google Scholar 

  169. H.-T. Yau. Logarithmic Sobolev inequality for generalized simple exclusion processes. Probab. Theory Related Fields, 109 (4): 507–538, 1997.

    MathSciNet  MATH  Google Scholar 

  170. N. Yoshida. The log-Sobolev inequality for weakly coupled lattice fields. Probab. Theory Related Fields, 115 (1): 1–40, 1999.

    MathSciNet  MATH  Google Scholar 

  171. N. Yoshida. Application of log-Sobolev inequality to the stochastic dynamics of unbounded spin systems on the lattice. J. Fund. Anal., 173 (1): 74–102, 2000.

    MATH  Google Scholar 

  172. N. Yoshida. The equivalence of the log-Sobolev inequality and a mixing condition for unbounded spin systems on the lattice. Ann. Inst. H. Poincaré Probab. Statist., 37 (2): 223–243, 2001.

    MATH  Google Scholar 

  173. B. Zegarlinski. On log-Sobolev inequalities for infinite lattice systems. Lett. Math. Phys., 20 (3): 173–182, 1990.

    MathSciNet  MATH  Google Scholar 

  174. B. Zegarlinski. The strong decay to equilibrium for the stochastic dynamics of unbounded spin systems on a lattice. Comm. Math. Phys., 175 (2): 401–432, 1996.

    MathSciNet  MATH  Google Scholar 

Download references

Authors
  1. Fabio Martinelli
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Cornell University Department of Mathematics, Malott Hall 310, 14853-4201, Ithaca, NY, USA

    Harry Kesten

Rights and permissions

Reprints and permissions

Copyright information

© 2004 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Martinelli, F. (2004). Relaxation Times of Markov Chains in Statistical Mechanics and Combinatorial Structures. In: Kesten, H. (eds) Probability on Discrete Structures. Encyclopaedia of Mathematical Sciences, vol 110. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-09444-0_4

Download citation

  • DOI: https://doi.org/10.1007/978-3-662-09444-0_4

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-05647-5

  • Online ISBN: 978-3-662-09444-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation