Cheeger bound

From Wikipedia, the free encyclopedia

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.

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 A,B \subset X define

Q(A \times B) = \sum_{x \in A, y \in B} Q(x,y).

Define the constant Φ as

\Phi = \min_{S \subset X, \pi(S) \leq \frac{1}{2}} \frac{Q (S \times S^c)}{\pi(S)}.

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 λ1 = 1. The Cheeger bound is a bound on the second largest eigenvalue λ2.


Theorem (Cheeger bound):

1 - 2 \Phi \leq \lambda_2 \leq 1 - \frac{\Phi^2}{2}.

[edit] See also

[edit] 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.
Retrieved from "http://en.wikipedia.org../../../c/h/e/Cheeger_bound.html"