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

Define

:$Q(x,y)\; =\; \backslash pi(x)\; K(x,y)$

and for $A,B\; \backslash subset\; X$ define

: $Q(A\; \backslash times\; B)\; =\; \backslash sum\_\{x\; \backslash in\; A,\; y\; \backslash in\; B\}\; Q(x,y).$

Define the constant $\backslash Phi$ as

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

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

: $(K\; \backslash phi)(x)\; =\; \backslash sum\_y\; K(x,y)\; \backslash phi(y)$

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

Theorem (Cheeger bound):

:$1\; -\; 2\; \backslash Phi\; \backslash leq\; \backslash lambda\_2\; \backslash leq\; 1\; -\; \backslash frac\{\backslash Phi^2\}\{2\}.$