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:
“When I received this [coronation] ring I solemnly bound myself in marriage to the realm; and it will be quite sufficient for the memorial of my name and for my glory, if, when I die, an inscription be engraved on a marble tomb, saying, “Here lieth Elizabeth, which reigned a virgin, and died a virgin.””
—Elizabeth I (1533–1603)