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:
“In the case of a deliberate, palpable, and dangerous exercise of ... powers not granted by the compact, the States ... are in duty bound to interpose for arresting the progress of the evil, and for maintaining within their respective limits the authorities, rights, and liberties appertaining to them.”
—James Madison (1751–1836)