Границы Чигера

Границы Чигера — это границы второй по величине собственного значения матрицы переходных вероятностей дискретной по времени цепи Маркова с конечным числом состояний и возвратными состояниями. Она может рассматриваться как специальный случай неравенства Чигера в экспандерах.

Пусть будет конечным множеством и пусть будет вероятностями переходов для цепи Маркова на . Предположим, что цепь имеет стационарное распределение .

Определим

и для определим

Определим константу как

Оператор , действующий на пространстве функций[англ.] из в , определённый выражением

имеет собственные значения . Известно, что . Границы Чигера являются границами второго по величине собственного значения .

Теорема (границы Чигера):

См. также

править

Примечания

править

Литература

править
  • J. Cheeger. A lower bound for the smallest eigenvalue of the Laplacian // Problems in Analysis, Papers dedicated to Salomon Bochner. — Princeton: Princeton University Press, 1969.
  • P. Diaconis, D. Stroock. Geometric bounds for eigenvalues of Markov chains // Annals of Applied Probability. — 1991. — Т. 1.