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 $|X|$ , 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}}.

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.

This article is issued from Wikipedia - version of the 10/31/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Cheeger bound

See also

References