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 $\pi$.

Define

$Q(x,y)=\pi (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 $\mathrm{\Phi }$ as

$\mathrm{\Phi }=\underset{S\subset X,\pi (S)\le \frac{1}{2}}{\min }\frac{Q(S\times S^c)}{\pi (S)}.$

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

$(K\varphi )(x)=\sum _{y}K(x,y)\varphi (y)$

has eigenvalues ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n$. It is known that ${\lambda }_1=1$. The Cheeger bound is a bound on the second largest eigenvalue ${\lambda }_2$.

Theorem (Cheeger bound):

$1-2\mathrm{\Phi }\le {\lambda }_2\le 1-\frac{{\mathrm{\Phi }}^2}{2}.$

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.