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 {\displaystyle X} be a finite set and let K ( x , y ) {\displaystyle K(x,y)} be the transition probability for a reversible Markov chain on X {\displaystyle X} . Assume this chain has stationary distribution π {\displaystyle \pi } . Define
Q ( x , y ) = π ( x ) K ( x , y ) {\displaystyle Q(x,y)=\pi (x)K(x,y)}
and for A , B ⊂ X {\displaystyle A,B\subset X} define
Q ( A × B ) = ∑ x ∈ A , y ∈ B Q ( x , y ) . {\displaystyle Q(A\times B)=\sum _{x\in A,y\in B}Q(x,y).}
Define the constant Φ {\displaystyle \Phi } as
Φ = min S ⊂ X , π ( S ) ≤ 1 2 Q ( S × S c ) π ( S ) . {\displaystyle \Phi =\min _{S\subset X,\pi (S)\leq {\frac {1}{2}}}{\frac {Q(S\times S^{c})}{\pi (S)}}.}
The operator K , {\displaystyle K,} acting on the space of functions from | X | {\displaystyle |X|} to R {\displaystyle \mathbb {R} } , defined by
( K ϕ ) ( x ) = ∑ y K ( x , y ) ϕ ( y ) {\displaystyle (K\phi )(x)=\sum _{y}K(x,y)\phi (y)}
has eigenvalues λ 1 ≥ λ 2 ≥ ⋯ ≥ λ n {\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}} . It is known that λ 1 = 1 {\displaystyle \lambda _{1}=1} . The Cheeger bound is a bound on the second largest eigenvalue λ 2 {\displaystyle \lambda _{2}} . Theorem (Cheeger bound):
1 − 2 Φ ≤ λ 2 ≤ 1 − Φ 2 2 . {\displaystyle 1-2\Phi \leq \lambda _{2}\leq 1-{\frac {\Phi ^{2}}{2}}.}
See also Stochastic matrix Cheeger constant Conductance
References