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 (Cheeger bound):
Famous quotes containing the word bound:
“Nature in darkness groans
And men are bound to sullen contemplation in the night:
Restless they turn on beds of sorrow; in their inmost brain
Feeling the crushing wheels, they rise, they write the bitter words
Of stern philosophy & knead the bread of knowledge with tears & groans.”
—William Blake (1757–1827)