Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-28T10:40:45.017Z Has data issue: false hasContentIssue false
  • English
  • Français

Spectral Theory for Weakly Reversible Markov Chains

Part of: Markov processes Ergodic theory

Published online by Cambridge University Press:  04 February 2016

Achim Wübker
Achim Wübker*
Affiliation:
Universität Osnabrück
*
∗ Postal address: Fachbereich Mathematik, Universität Osnabrück, Albrechtstrasse 28a, 49076 Osnabrück, Germany. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The theory of L2-spectral gaps for reversible Markov chains has been studied by many authors. In this paper we consider positive recurrent general state space Markov chains with stationary transition probabilities. Replacing the assumption of reversibility with a weaker assumption, we still obtain a simple necessary and sufficient condition for the spectral gap property of the associated Markov operator in terms of the isoperimetric constant. We show that this result can be applied to a large class of Markov chains, including those that are related to positive recurrent finite-range random walks on Z.

Keywords

Markov chaingeneral state spacespectral gap propertyisoperimetric constantreversibility

MSC classification

Primary: 37A30: Ergodic theorems, spectral theory, Markov operators 60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
Type
Research Article
Information
Journal of Applied Probability , Volume 49 , Issue 1 , March 2012 , pp. 245 - 265
Copyright
© Applied Probability Trust 

References

Chen, M. (1996). Estimation of spectral gap for Markov chains. Acta Math. Sinica (N.S.) 12, 337–360.Google Scholar
Chen, M.-F. (2005). Eigenvalues, Inequalities, and Ergodic Theory. Springer, London.Google Scholar
Chen, M.-F. and Wang, F. Y. (2000). Cheeger's inequalities for general symmetric forms and existence criteria for spectral gap. Ann. Prob. 28, 235–257.CrossRefGoogle 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. (1996). Logarithmic Sobolev inequalities for finite Markov chains. Ann. Appl. Prob. 6, 695–750.CrossRefGoogle Scholar
Diaconis, P. and Saloff-Coste, L. (1996). Nash inequalities for finite Markov chains. J. Theoret. Prob. 9, 459–510.CrossRefGoogle Scholar
Diaconis, P. and Stroock, D. (1991). Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Prob. 1, 36–61.CrossRefGoogle Scholar
Dodziuk, J. (1984). Difference equations, isoperimetric inequality and transience of certain random walks. Trans. Amer. Math. Soc. 284, 787–794.CrossRefGoogle Scholar
Elaydi, S. N. (1996). An Introduction to Difference Equations. Springer, New York.CrossRefGoogle Scholar
Fill, J. (1991). Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process. Ann. Appl. Prob. 1, 62–87.CrossRefGoogle Scholar
Fukushima, M. (1980). Dirichlet Forms and Markov Processes. North-Holland, Amsterdam.Google Scholar
Hennion, H. and Hervé, L. (2001). Limit Theorems for Markov Chains and Stochastic Properties of Dynamical Systems by Quasi-Compactness (Lecture Notes Math. 1766). Springer, Berlin.CrossRefGoogle Scholar
Jones, G. L. (2004). On the Markov chain central limit theorem. Prob. Surveys 1, 299–320.CrossRefGoogle Scholar
Kontoyiannis, I. and Meyn, S. P. (2009). Geometric ergodicity and the spectral gap of non-reversible Markov chains. Preprint. Available at http://arxiv.org/abs/0906.5322v1.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
Levin, D. A., Peres, Y. and Wilmer, E. L. (2008). Markov Chains and Mixing Times. American Mathematical Society.CrossRefGoogle Scholar
Meyn, S. P. and Tweedie, R. L. (1993). Markov Chains and Stochastic Stability. Springer, London.CrossRefGoogle Scholar
Mitrophanov, A. Y. (2003). Stability and exponential convergence of continuous-time Markov chains. J. Appl. Prob. 40, 970–979.CrossRefGoogle Scholar
Mitrophanov, A. Y. (2004). The spectral gap and perturbation bounds for reversible continuous-time Markov chains. J. Appl. Prob. 41, 1219–1222.CrossRefGoogle Scholar
Mitrophanov, A. Y. (2005). Sensitivity and convergence of uniformly ergodic Markov chains. J. Appl. Prob. 42, 1003–1014.CrossRefGoogle Scholar
Montenegro, R. and Tetali, P. (2005). Mathematical Aspects of Mixing Times in Markov Chains. (Foundation Trends Theoret. Comput. Sci. 1). Now, Boston.CrossRefGoogle Scholar
Roberts, G. O. and Tweedie, R. L. (2001). Geometric L{2} and L{1} convergence are equivalent for reversible Markov chains. In Probability, Statistics and Seismology (J. Appl. Prob. Spec. Vol. 38A), ed. Daley, D. J., Applied Probability Trust, Sheffield, pp. 37–41 Google Scholar
Wübker, A. (2011). Asymptotic optimality of isoperimetric constants. J. Theoret. Prob. 24 pp.Google Scholar
Wübker, A. (2012). L{2}-spectral gaps for time discrete reversible Markov chains. To appear in Markov Process. Relat. Fields.Google Scholar