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:
“People named John and Mary never divorce. For better or for worse, in madness and in saneness, they seem bound together for eternity by their rudimentary nomenclature. They may loathe and despise one another, quarrel, weep, and commit mayhem, but they are not free to divorce. Tom, Dick, and Harry can go to Reno on a whim, but nothing short of death can separate John and Mary.”
—John Cheever (1912–1982)