Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-24T17:34:42.791Z Has data issue: false hasContentIssue false
  • English
  • Français

On spectral gap estimates of a Markov chain via hitting times and coupling

Part of: Limit theorems Markov processes

Published online by Cambridge University Press:  14 July 2016

Christian Meise
Christian Meise*
Affiliation:
Universität Bielefeld
*
∗Postal address: Fakultät für Mathematik, Universität Bielefeld, Postfach 100131, 33501 Bielefeld, Germany. Email address: [email protected].
Get access Rights & Permissions [Opens in a new window]

Abstract

Well-known inequalities for the spectral gap of a discrete-time Markov chain, such as Poincaré's and Cheeger's inequalities, do not perform well if the transition graph of the Markov chain is strongly connected. For example in the case of nearest-neighbour random walk on the n-dimensional cube Poincaré's and Cheeger's inequalities are off by a factor n. Using a coupling technique and a contraction principle lower bounds on the spectral gap can be derived. Finally, we show that using the contraction principle yields a sharp estimate for nearest-neighbour random walk on the n-dimensional cube.

Keywords

Markov chainsspectral gapcouplings

MSC classification

Primary: 60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
Secondary: 60F05: Central limit and other weak theorems
Type
Research Papers
Information
Journal of Applied Probability , Volume 36 , Issue 2 , June 1999 , pp. 310 - 319
Copyright
Copyright © Applied Probability Trust 1999 

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

Aldous, D., and Diaconis, P. (1987). Strong uniform times and finite random walks. Adv. Appl. Math. 8, 69–97.CrossRefGoogle Scholar
Chen, M. F. (1992). From Markov Chains to Non-Equilibrium Particle Systems. World Scientific, Singapore.CrossRefGoogle Scholar
Chen, M. F. (1994). Optimal Markovian couplings and applications. Acta Math. Sinica N.S. 10, 260–275.Google Scholar
Chen, M. F. (1996). Estimation of spectral gap for Markov chains. Acta Math. Sinica N.S. 12, 337–360.Google Scholar
Chen, M. F., and Wang, F. Y. (1994). Applications of coupling method to the first eigenvalue on manifold. Sci. China, Ser. A 37, 1–14.Google Scholar
Diaconis, P., and Stroock, D. (1991). Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Prob. 1, 36–61.Google Scholar
Fiedler, M. (1975). A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czech. Math. J. 25, 619–633.CrossRefGoogle Scholar
Meise, C. (1996). Lower bounds for the spectral gap of Markov chains. Preprint 96-019, SFB 343, Universität Bielefeld.Google Scholar