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 be a finite set and let be the transition probability for a reversible Markov chain on. Assume this chain has stationary distribution.
Define
and for define
Define the constant as
The operator acting on the space of functions from to, defined by
has eigenvalues. It is known that . The Cheeger bound is a bound on the second largest eigenvalue.
Theorem :
