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

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

Пусть $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).$

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

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

Оператор $K,$, действующий на Шаблон:Нп5 из $|X|$ в $|X|$, определённый выражением

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

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

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

$1-2\mathrm{\Phi }⩽{\lambda }_2⩽1-\frac{{\mathrm{\Phi }}^2}{2}.$

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Статья