Cheeger bound

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 be a finite set and let K(x,y) be the transition probability for a reversible Markov chain on X. Assume this chain has stationary distribution π.

Define

Q(x,y) = π(x)K(x,y)

and for $A,B \subset X$ define

$Q(A \times B) = \sum_{x \in A, y \in B} Q(x,y).$

Define the constant Φ as

$\Phi = \min_{S \subset X, \pi(S) \leq \frac{1}{2}} \frac{Q (S \times S^c)}{\pi(S)}.$

The operator K, acting on the space of functions from | X | to | X | , defined by

$(K \phi)(x) = \sum_y K(x,y) \phi(y) \,$

has eigenvalues $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$. It is known that λ₁ = 1. The Cheeger bound is a bound on the second largest eigenvalue λ₂.

Theorem (Cheeger bound):

$1 - 2 \Phi \leq \lambda_2 \leq 1 - \frac{\Phi^2}{2}.$

See also

• Poincaré bound
• Stochastic matrix
• Cheeger constant

References

• 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.v · Categories: Probabilistic inequalities Stochastic processes Statistical inequalities Statistics stubs Wikimedia Foundation. 2010. Игры ⚽ Поможем сделать НИР Takayuki Yamaguchi KMEG Look at other dictionaries: Cheeger constant — This article discusses the Cheeger isoperimetric constant and Cheeger s inequality in Riemannian geometry. For a different use, see Cheeger constant (graph theory). In Riemannian geometry, the Cheeger isoperimetric constant of a compact… …   Wikipedia Cheeger constant (graph theory) — In mathematics, the Cheeger constant (also Cheeger number or isoperimetric number) of a graph is a numerical measure of whether or not a graph has a bottleneck . The Cheeger constant as a measure of bottleneckedness is of great interest in many… …   Wikipedia Jeff Cheeger — Infobox Scientist name = Jeff Cheeger caption = birth date = birth date|1943|12|1|df=y birth place = Brooklyn, U.S. death date = death place = residence = U.S. nationality = American field = Mathematician work institution = New York University… …   Wikipedia List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   Wikipedia List of statistics topics — Please add any Wikipedia articles related to statistics that are not already on this list.The Related changes link in the margin of this page (below search) leads to a list of the most recent changes to the articles listed below. To see the most… …   Wikipedia Collapsing manifold — For the concept in homotopy, see collapse (topology). In Riemannian geometry, a collapsing or collapsed manifold is an n dimensional manifold M that admits a sequence of Riemannian metrics gn, such that as n goes to infinity the manifold is close …   Wikipedia Expander graph — In combinatorics, an expander graph is a sparse graph which has high connectivity properties, quantified using vertex or edge expansion as described below. Expander constructions have spawned research in pure and applied mathematics, with several …   Wikipedia Ricci curvature — In differential geometry, the Ricci curvature tensor, named after Gregorio Ricci Curbastro, provides one way of measuring the degree to which the geometry determined by a given Riemannian metric might differ from that of ordinary Euclidean n… …   Wikipedia 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”