View source for Cheeger bound

In [[Mathematics|mathematics]], the '''Cheeger bound''' is a bound of the second largest eigenvalue of the [[Stochastic matrix|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 graph|expander graph]]s.
Let <math>X</math> be a finite set and let <math>K(x,y)</math> be the transition probability for a reversible Markov chain on <math>X</math>. Assume this chain has [[Stationary distribution|stationary distribution]] <math>\pi</math>.

Define

:<math>Q(x,y) = \pi(x) K(x,y) </math>

and for <math>A,B \subset X </math> define

: <math>Q(A \times B) = \sum_{x \in A, y \in B} Q(x,y). </math>

Define the constant <math>\Phi</math> as

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

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

: <math> (K \phi)(x) = \sum_y K(x,y) \phi(y) </math>

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

''' Theorem (Cheeger bound):'''

:<math> 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.

[[Category:Probabilistic inequalities]]
[[Category:Stochastic processes]]
[[Category:Statistical inequalities]]



{{Sourceattribution|Cheeger bound}}