Some universal estimates for reversible Markov chains

Mykhaylo Shkolnikov (University of California, Berkeley)


We obtain universal estimates on the convergence to equilibrium and the times of coupling for continuous time irreducible reversible finite-state Markov chains, both in the total variation and in the $L^2$ norms. The estimates in total variation norm are obtained using a novel identity relating the convergence to equilibrium of a reversible Markov chain to the increase in the entropy of its one-dimensional distributions. In addition, we propose a universal way of defining the ultrametric partition structure on the state space of such Markov chains. Finally, for chains reversible with respect to the uniform measure, we show how the global convergence to equilibrium can be controlled using the entropy accumulated by the chain.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-17

Publication Date: January 17, 2013

DOI: 10.1214/EJP.v18-1749


  • Aldous, D. J. and Fill, J. A. (2002). Reversible Markov Chains and Random Walks on Graphs. Available at
  • Ben Arous, Gérard; Cerf, Raphaël. Metastability of the three-dimensional Ising model on a torus at very low temperatures. Electron. J. Probab. 1 (1996), no. 10, approx. 55 pp. (electronic). MR1423463
  • Bianchi, Alessandra; Bovier, Anton; Ioffe, Dmitry. Sharp asymptotics for metastability in the random field Curie-Weiss model. Electron. J. Probab. 14 (2009), no. 53, 1541--1603. MR2525104
  • Bianchi, Alessandra; Bovier, Anton; Ioffe, Dmitry. Pointwise estimates and exponential laws in metastable systems via coupling methods. Ann. Probab. 40 (2012), no. 1, 339--371. MR2917775
  • Bobkov, Sergey G.; Tetali, Prasad. Modified logarithmic Sobolev inequalities in discrete settings. J. Theoret. Probab. 19 (2006), no. 2, 289--336. MR2283379
  • Borgs, Christian; Chayes, Jennifer T.; Tetali, Prasad. Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point. Probab. Theory Related Fields 152 (2012), no. 3-4, 509--557. MR2892955
  • Bovier, Anton. Metastability and ageing in stochastic dynamics. Dynamics and randomness II, 17--79, Nonlinear Phenom. Complex Systems, 10, Kluwer Acad. Publ., Dordrecht, 2004. MR2153326
  • Bovier, Anton. Metastability: a potential theoretic approach. International Congress of Mathematicians. Vol. III, 499--518, Eur. Math. Soc., Zürich, 2006. MR2275693
  • Bovier, Anton; Eckhoff, Michael; Gayrard, Véronique; Klein, Markus. Metastability and small eigenvalues in Markov chains. J. Phys. A 33 (2000), no. 46, L447--L451. MR1804034
  • Bovier, Anton; Eckhoff, Michael; Gayrard, Véronique; Klein, Markus. Metastability in stochastic dynamics of disordered mean-field models. Probab. Theory Related Fields 119 (2001), no. 1, 99--161. MR1813041
  • Bovier, Anton; Eckhoff, Michael; Gayrard, Véronique; Klein, Markus. Metastability and low lying spectra in reversible Markov chains. Comm. Math. Phys. 228 (2002), no. 2, 219--255. MR1911735
  • Bovier, Anton; Manzo, Francesco. Metastability in Glauber dynamics in the low-temperature limit: beyond exponential asymptotics. J. Statist. Phys. 107 (2002), no. 3-4, 757--779. MR1898856
  • Cassandro, Marzio; Galves, Antonio; Olivieri, Enzo; Vares, Maria Eulália. Metastable behavior of stochastic dynamics: a pathwise approach. J. Statist. Phys. 35 (1984), no. 5-6, 603--634. MR0749840
  • Cover, Thomas M.; Thomas, Joy A. Elements of information theory. Second edition. Wiley-Interscience [John Wiley & Sons], Hoboken, NJ, 2006. xxiv+748 pp. ISBN: 978-0-471-24195-9; 0-471-24195-4 MR2239987
  • Diaconis, P.; Saloff-Coste, L. Logarithmic Sobolev inequalities for finite Markov chains. Ann. Appl. Probab. 6 (1996), no. 3, 695--750. MR1410112
  • Dembo, Amir; Zeitouni, Ofer. Large deviations techniques and applications. Second edition. Applications of Mathematics (New York), 38. Springer-Verlag, New York, 1998. xvi+396 pp. ISBN: 0-387-98406-2 MR1619036
  • Hwang, Suk-Geun; Pyo, Sung-Soo. The inverse eigenvalue problem for symmetric doubly stochastic matrices. Tenth Conference of the International Linear Algebra Society. Linear Algebra Appl. 379 (2004), 77--83. MR2039298
  • Kramers, H. A. Brownian motion in a field of force and the diffusion model of chemical reactions. Physica 7, (1940). 284--304. MR0002962
  • Levin, David A.; Luczak, Malwina J.; Peres, Yuval. Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability. Probab. Theory Related Fields 146 (2010), no. 1-2, 223--265. MR2550363
  • Neves, E. Jordão; Schonmann, Roberto H. Critical droplets and metastability for a Glauber dynamics at very low temperatures. Comm. Math. Phys. 137 (1991), no. 2, 209--230. MR1101685
  • Neves, E. Jordão; Schonmann, Roberto H. Behavior of droplets for a class of Glauber dynamics at very low temperature. Probab. Theory Related Fields 91 (1992), no. 3-4, 331--354. MR1151800
  • Olivieri, E.; Scoppola, E. Markov chains with exponentially small transition probabilities: first exit problem from a general domain. I. The reversible case. J. Statist. Phys. 79 (1995), no. 3-4, 613--647. MR1327899
  • Thomas, Lawrence E. Bound on the mass gap for finite volume stochastic Ising models at low temperature. Comm. Math. Phys. 126 (1989), no. 1, 1--11. MR1027910

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.