thereaderwiki.com

Cheeger bound

  • ️Sun Apr 14 2024

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 {\displaystyle X} be a finite set and let {\displaystyle K(x,y)} be the transition probability for a reversible Markov chain on {\displaystyle X}. Assume this chain has stationary distribution {\displaystyle \pi }.

Define

{\displaystyle Q(x,y)=\pi (x)K(x,y)}

and for {\displaystyle A,B\subset X} define

{\displaystyle Q(A\times B)=\sum _{x\in A,y\in B}Q(x,y).}

Define the constant {\displaystyle \Phi } as

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

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

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

has eigenvalues {\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}}. It is known that {\displaystyle \lambda _{1}=1}. The Cheeger bound is a bound on the second largest eigenvalue {\displaystyle \lambda _{2}}.

Theorem (Cheeger bound):

{\displaystyle 1-2\Phi \leq \lambda _{2}\leq 1-{\frac {\Phi ^{2}}{2}}.}