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 $\pi$.

Define

:$Q(x,y) = \pi(x) K(x,y)$

and for $A,B \subset X$ define

: $Q(A \times B) = \sum_ Q(x,y).$

Define the constant $\Phi$ as

: $\Phi = \min_ \frac.$

The operator $K,$ acting on the space of functions from $, X,$ to $, X,$, defined by

: $(K \phi)(x) = \sum_y K(x,y) \phi(y)$

has eigenvalues $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$. It is known that $\lambda_1 = 1$. The Cheeger bound is a bound on the second largest eigenvalue $\lambda_2$.

Theorem (Cheeger bound):

:$1 - 2 \Phi \leq \lambda_2 \leq 1 - \frac.$

See also

* 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.

Probabilistic inequalities
Stochastic processes
Statistical inequalities

{{statistics-stub