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.

. Assume this chain has stationary distribution.

Define

define

as

acting on the space of functions, defined by

has eigenvalues.

Theorem (Cheeger bound):

See also

• Stochastic matrix

• Cheeger constant

• Conductance

References