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

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

Define the constant $Φ$ as

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

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

(K ϕ) (x) = \sum_{y} K (x, y) ϕ (y)

has eigenvalues $λ_{1} \geq λ_{2} \geq \dots \geq λ_{n}$ . It is known that $λ_{1} = 1$ . The Cheeger bound is a bound on the second largest eigenvalue $λ_{2}$ .

Theorem (Cheeger bound):

1 - 2 Φ \leq λ_{2} \leq 1 - \frac{Φ^{2}}{2} .

References

Cheeger, Jeff (1971). "A Lower Bound for the Smallest Eigenvalue of the Laplacian". Problems in Analysis: A Symposium in Honor of Salomon Bochner (PMS-31). Princeton University Press. pp. 195–200. doi:10.1515/9781400869312-013. ISBN 978-1-4008-6931-2.
Diaconis, Persi; Stroock, Daniel (1991). "Geometric Bounds for Eigenvalues of Markov Chains". The Annals of Applied Probability. 1 (1). Institute of Mathematical Statistics: 36–61. doi:10.1214/aoap/1177005980. ISSN 1050-5164. JSTOR 2959624. Retrieved 2024-04-14.

This statistics-related article is a stub. You can help Wikipedia by adding missing information.

See also

References