Związany z Cheegerem

W matematyce granica Cheegera jest granicą drugiej co do wielkości wartości własnej macierzy przejścia odwracalnego stacjonarnego łańcucha Markowa o skończonym stanie, w czasie dyskretnym . Można to postrzegać jako szczególny przypadek nierówności Cheegera w grafach ekspandera .

Niech ${$ $zbiorem$ skończonym i niech dla odwracalnego łańcucha Markowa na $}$ . Załóżmy, że ten łańcuch ma rozkład stacjonarny ${\ displaystyle \ pi}$ .

Definiować

{\ Displaystyle Q (x, y) = \ pi (x) K (x, y)}

i dla zdefiniować. ${\ Displaystyle A, B \ podzbiór X}$

{\ Displaystyle Q (A \ razy B) = \ suma _ {x \ w A, y \ w B} Q (x, y).}

Zdefiniuj stałą jako . ${\ displaystyle \ Phi}$

{\ Displaystyle \ Phi = \ min _ {S \ podzbiór X, \ pi (S) \ leq {\ Frac {1} {2}}}} {\ Frac {Q (S \ razy S ^ {c})} \pi (S)}}.}

Operator ${\ Displaystyle | X |}$ na przestrzeni $_$ z do ${\ displaystyle | X|}$ , zdefiniowany przez

{\ Displaystyle (K \ phi) (x) = \ suma _ {y} K (x, y) \ phi (y)}

ma wartości własne ${\ Displaystyle \ lambda _ {1} \ geq \ lambda _ {2} \ geq \ cdots \ geq \ lambda _ {n}}$ . Wiadomo, że ${\ Displaystyle \ lambda _ {1} = 1}$ . Granica Cheegera jest granicą drugiej co do wielkości wartości własnej ${\ displaystyle \ lambda _ {2}}$ .

Twierdzenie (związane z Cheegerem):

{\ Displaystyle 1-2 \ Phi \ równoważnik \ lambda _ {2} \ równoważnik 1- {\ Frac {\ Phi ^ {2}} {2}}.}

Zobacz też

J. Cheeger, Dolna granica najmniejszej wartości własnej Laplace'a, Problems in Analysis, Papers dedykowane Salomonowi Bochnerowi, 1969, Princeton University Press, Princeton, 195-199.
P. Diaconis, D. Stroock, Geometryczne granice wartości własnych łańcuchów Markowa, Annals of Applied Probability, tom. 1, 36-61, 1991, zawierający prezentowaną tu wersję oprawy.