- Cheeger bound
-
In mathematics, the Cheeger bound is a bound of the second largest eigenvalue of the transition matrix of a finite-state, discrete-time, reversible stationary Markov chain. It can be seen as a special case of Cheeger inequalities in expander graphs.
Let X be a finite set and let K(x,y) be the transition probability for a reversible Markov chain on X. Assume this chain has stationary distribution π.
Define
- Q(x,y) = π(x)K(x,y)
and for define
Define the constant Φ as
The operator K, acting on the space of functions from | X | to | X | , defined by
has eigenvalues . It is known that λ1 = 1. The Cheeger bound is a bound on the second largest eigenvalue λ2.
Theorem (Cheeger bound):
See also
- Poincaré bound
- Stochastic matrix
- Cheeger constant
References
- J. Cheeger, A lower bound for the smallest eigenvalue of the Laplacian, Problems in Analysis, Papers dedicated to Salomon Bochner, 1969, Princeton University Press, Princeton, 195-199.
- P. Diaconis, D. Stroock, Geometric bounds for eigenvalues of Markov chains, Annals of Applied Probability, vol. 1, 36-61, 1991, containing the version of the bound presented here.
This statistics-related article is a stub. You can help Wikipedia by expanding it.