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

Пусть ${\displaystyle X}$ будет конечным множеством и пусть ${\displaystyle K(x,y)}$ будет вероятностями переходов для цепи Маркова на ${\displaystyle X}$ . Предположим, что цепь имеет стационарное распределение ${\displaystyle \pi }$ .

Определим:

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

и для ${\displaystyle A,B\subset X}$ определим

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

Определим константу ${\displaystyle \Phi }$ как

${\displaystyle \Phi =\min _{S\subset X,\pi (S)\leqslant {\frac {1}{2}}}{\frac {Q(S\times S^{c})}{\pi (S)}}.}$

Оператор ${\displaystyle K,}$ , действующий на из ${\displaystyle |X|}$ в ${\displaystyle |X|}$ , определённый выражением

${\displaystyle (K\phi )(x)=\sum _{y}K(x,y)\phi (y)\,}$

имеет собственные значения ${\displaystyle \lambda _{1}\geqslant \lambda _{2}\geqslant \cdots \geqslant \lambda _{n}}$ . Известно, что ${\displaystyle \lambda _{1}=1}$ . Границы Чигера являются границами второго по величине собственного значения ${\displaystyle \lambda _{2}}$ .

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

${\displaystyle 1-2\Phi \leqslant \lambda _{2}\leqslant 1-{\frac {\Phi ^{2}}{2}}.}$

См. также

• Стохастическая матрица
• Константа Чигера

Примечания

Литература