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 $\Phi$ as

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

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

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

has eigenvalues $\lambda _{1}\geq \lambda _{2}\geq \cdots \geq \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\Phi \leq \lambda _{2}\leq 1-{\frac {\Phi ^{2}}{2}}.$

See also

• Stochastic matrix
• Cheeger constant
• Conductance

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.