Cheeger bound - Alchetron, The Free Social Encyclopedia

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 .

References

Cheeger bound Wikipedia

(Text) CC BY-SA