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:
“The quickness with which all the “stuff” from childhood can reduce adult siblings to kids again underscores the strong and complex connections between brothers and sisters.... It doesn’t seem to matter how much time has elapsed or how far we’ve traveled. Our brothers and sisters bring us face to face with our former selves and remind us how intricately bound up we are in each other’s lives.”
—Jane Mersky Leder (20th century)