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 π .
Define
Q ( x , y ) = π ( x ) K ( x , y ) and for A , B ⊂ X define
Q ( A × B ) = ∑ x ∈ A , y ∈ B Q ( x , y ) . Define the constant Φ as
Φ = min S ⊂ X , π ( S ) ≤ 1 2 Q ( S × S c ) π ( S ) . The operator K , acting on the space of functions from | X | to | X | , defined by
( K ϕ ) ( x ) = ∑ y K ( x , y ) ϕ ( y ) has eigenvalues λ 1 ≥ λ 2 ≥ ⋯ ≥ λ n . It is known that λ 1 = 1 . The Cheeger bound is a bound on the second largest eigenvalue λ 2 .
Theorem (Cheeger bound):
1 − 2 Φ ≤ λ 2 ≤ 1 − Φ 2 2 . 