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}.

See also

References


This article is issued from Wikipedia - version of the Monday, December 08, 2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.