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.
This statistics-related article is a stub. You can help Wikipedia by expanding it.
cheeger, bound, mathematics, bound, second, largest, eigenvalue, transition, matrix, finite, state, discrete, time, reversible, stationary, markov, chain, seen, special, case, cheeger, inequalities, expander, graphs, displaystyle, finite, displaystyle, transit. 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 X displaystyle X be a finite set and let K x y displaystyle K x y be the transition probability for a reversible Markov chain on X displaystyle X Assume this chain has stationary distribution p displaystyle pi Define Q x y p x K x y displaystyle Q x y pi x K x y and for A B X displaystyle A B subset X define Q A B x A y BQ x y displaystyle Q A times B sum x in A y in B Q x y Define the constant F displaystyle Phi as F minS X p S 12Q S Sc p S displaystyle Phi min S subset X pi S leq frac 1 2 frac Q S times S c pi S The operator K displaystyle K acting on the space of functions from X displaystyle X to R displaystyle mathbb R defined by Kϕ x yK x y ϕ y displaystyle K phi x sum y K x y phi y has eigenvalues l1 l2 ln displaystyle lambda 1 geq lambda 2 geq cdots geq lambda n It is known that l1 1 displaystyle lambda 1 1 The Cheeger bound is a bound on the second largest eigenvalue l2 displaystyle lambda 2 Theorem Cheeger bound 1 2F l2 1 F22 displaystyle 1 2 Phi leq lambda 2 leq 1 frac Phi 2 2 See also editStochastic matrix Cheeger constantReferences editJ 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 nbsp This statistics related article is a stub You can help Wikipedia by expanding it vte Retrieved from https en wikipedia org w index php title Cheeger bound amp oldid 1181588511, wikipedia, wiki, book, books, library,