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

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

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

Определим

$Q(x,y)=\pi (x)K(x,y)$

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

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

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

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

Оператор $K,$, действующий на пространстве функций из $|X|$ в $|X|$, определённый выражением

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

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

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

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

См. также

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