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

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

Пусть ${\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}}.}$

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