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 [math]\displaystyle{ X }[/math] be a finite set and let [math]\displaystyle{ K(x,y) }[/math] be the transition probability for a reversible Markov chain on [math]\displaystyle{ X }[/math]. Assume this chain has stationary distribution [math]\displaystyle{ \pi }[/math].

Define

[math]\displaystyle{ Q(x,y) = \pi(x) K(x,y) }[/math]

and for [math]\displaystyle{ A,B \subset X }[/math] define

[math]\displaystyle{ Q(A \times B) = \sum_{x \in A, y \in B} Q(x,y). }[/math]

Define the constant [math]\displaystyle{ \Phi }[/math] as

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

The operator [math]\displaystyle{ K, }[/math] acting on the space of functions from [math]\displaystyle{ |X| }[/math] to [math]\displaystyle{ \mathbb{R} }[/math], defined by

[math]\displaystyle{ (K \phi)(x) = \sum_y K(x,y) \phi(y) }[/math]

has eigenvalues [math]\displaystyle{ \lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n }[/math]. It is known that [math]\displaystyle{ \lambda_1 = 1 }[/math]. The Cheeger bound is a bound on the second largest eigenvalue [math]\displaystyle{ \lambda_2 }[/math].

Theorem (Cheeger bound):

[math]\displaystyle{ 1 - 2 \Phi \leq \lambda_2 \leq 1 - \frac{\Phi^2}{2}. }[/math]

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.