Cheeger bound

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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):

See also[edit]

References[edit]

  • J. Cheeger, A lower bound for the smallest eigenvalue of the Laplacian, Problems in Analysis, Papers dedicated to Salomon Bochner, 1969, Princeton University Press, Princeton, 195-199.
  • P. Diaconis, D. Stroock, Geometric bounds for eigenvalues of Markov chains, Annals of Applied Probability, vol. 1, 36-61, 1991, containing the version of the bound presented here.