Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-06T10:36:58.389Z Has data issue: false hasContentIssue false
  • English
  • Français

Geometric inequalities for the eigenvalues of concentrated Markov chains

Part of: Probabilistic methods, simulation and stochastic differential equations Basic linear algebra Markov processes

Published online by Cambridge University Press:  14 July 2016

Olivier François
Olivier François*
Affiliation:
LMC/IMAG
*
∗Postal address: LMC/IMAG, BP 53, 38041 Grenoble cedex 9, France. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

This article describes new estimates for the second largest eigenvalue in absolute value of reversible and ergodic Markov chains on finite state spaces. These estimates apply when the stationary distribution assigns a probability higher than 0.702 to some given state of the chain. Geometric tools are used. The bounds mainly involve the isoperimetric constant of the chain, and hence generalize famous results obtained for the second eigenvalue. Comparison estimates are also established, using the isoperimetric constant of a reference chain. These results apply to the Metropolis-Hastings algorithm in order to solve minimization problems, when the probability of obtaining the solution from the algorithm can be chosen beforehand. For these dynamics, robust bounds are obtained at moderate levels of concentration.

Keywords

Reversible Markov chaineigenvaluesisoperimetric constantMetropolis-Hastings dynamicsminimization

MSC classification

Primary: 60J10: Markov chains (discrete-time Markov processes on discrete state spaces) 65C05: Monte Carlo methods
Secondary: 15A42: Inequalities involving eigenvalues and eigenvectors
Type
Research Papers
Information
Journal of Applied Probability , Volume 37 , Issue 1 , March 2000 , pp. 15 - 28
Copyright
Copyright © 2000 by The Applied Probability Trust 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Azencott, R. (1988). Simulated annealing. Sém. Bourbaki 697, 161–175.Google Scholar
Bertsimas, D., and Tsitsiklis, J. (1993). Simulated annealing. Statist. Sci. 8, 10–15.CrossRefGoogle Scholar
Cheeger, J. (1970). A lower bound for the smallest eigenvalue of the Laplacian. In Problems in Analysis, ed. Gunning, R. C. Princeton University Press, Princeton, NJ, pp. 195–199.Google Scholar
Diaconis, P., and Saloff-Coste, L. (1993). Comparison theorems for reversible Markov chains. Ann. Appl. Prob. 3, 696–730.CrossRefGoogle Scholar
Diaconis, P., and Saloff-Coste, L. (1998). What do we know about the Metropolis algorithm? J. Comp. Sci. Syst. 57, 20–36.CrossRefGoogle Scholar
Diaconis, P., and Stroock, D. (1991). Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Prob. 1, 36–61.CrossRefGoogle Scholar
Francois, O. (1999). On the spectral gap of a time reversible Markov chain. Prob. Eng. Inform. Sci. 13, 95–101.Google Scholar
Freidlin, M. I., and Wentzell, A. D. (1984). Random Perturbations of Dynamical Systems. Springer, New York.CrossRefGoogle Scholar
Frigessi, A., Martinelli, F., and Stander, J. (1997). Computational complexity of Markov chain Monte Carlo methods. Biometrika 84, 1–18.Google Scholar
Frigessi, A., Hwang, C. R., Sheu, S. J., and Di Stefano, P. (1993). Convergence rates of the Gibbs sampler, the Metropolis algorithm, and other single-site updating dynamics. J. Roy. Statist. Soc. B 55, 205–220.Google Scholar
Hajek, B. (1988). Cooling schedules for optimal annealing. Math. Operat. Res. 13, 311–329.Google Scholar
Hastings, W. K. (1970). Monte Carlo sampling using Markov chains and their application. Biometrika 57, 77–109.Google Scholar
Holley, R., and Stroock, D. (1988). Simulated annealing via Sobolev inequalities. Commun. Math. Phys. 115, 553–569.Google Scholar
Ingrassia, S. (1993). Geometric approaches to the estimation of the spectral gap of time reversible Markov chains. Combin. Prob. Comput. 2, 301–323.CrossRefGoogle Scholar
Ingrassia, S. (1994). On the rate of convergence of the Metropolis algorithm and the Gibbs sampler by geometric bounds. Ann. Appl. Prob. 4, 347–389.Google Scholar
Lawler, G. F., and Sokal, A. D. (1988). Bounds on the L2 spectrum for Markov chains and Markov processes: a generalization of Cheeger's inequality. Trans. Amer. Math. Soc. 309, 557–580.Google Scholar
Lezaud, P. (1996). Chernoff bounds for finite Markov chains. Ph.D. Thesis, University of Toulouse.Google Scholar
Metropolis, M., Rosenbluth, A., Rosenbluth, M., Teller, A., and Teller, E. (1953). Equation of state calculation by fast computing machines. J. Chem. Phys. 21, 1087–1092.Google Scholar
Saloff-Coste, L. (1997). Lectures on Finite Markov Chains. Lect. Notes Math. (Saint-Flour) 1665, Springer, Berlin, pp. 301-413.Google Scholar
Sinclair, A. (1991). Improved bounds for mixing rates of Markov chains and multicommodity flows. Combin. Prob. Comput. 1, 351–370.Google Scholar
Sinclair, A., and Jerrum, M. (1989). Approximate counting, uniform generation and rapidly mixing Markov chains. Inform. and Comput. 82, 93–133.Google Scholar