Cheeger bound explained

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 defineQ(A x B) = \sum _{x} Q(x,y).

Define the constant

\Phi as\Phi = min _{S \subset X, \pi(S) \leq (1)/(2)} (Q (S x S ^{c)})/(\pi(S)) .

The operator

K, acting on the space of functions from |X| to R , defined by(K \phi)(x) = \sum _{y} K(x,y) \phi(y)

has eigenvalues

λ _{1} \geq λ _{2} \geq … \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 \Phi \leq λ _{2} \leq 1 - (\Phi ^{2})/(2) .

See also

• Stochastic matrix
• Cheeger constant
• Conductance

References

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