Чигер связан

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

Позволять $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)\leq {\frac {1}{2}}}{\frac {Q(S\times S^{c})}{\pi (S)}}.$

Оператор $K,$ действуя на пространство функций из $|X|$ к $\mathbb {R}$, определяемый

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

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

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

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

См. также

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

Ссылки

• Чигер, Джефф (1971). «Нижняя граница наименьшего собственного значения лапласиана». Проблемы анализа: симпозиум в честь Саломона Бохнера (PMS-31) . Издательство Принстонского университета. стр. 195–200. дои : 10.1515/9781400869312-013 . ISBN  978-1-4008-6931-2 .
• Диаконис, Перси; Строк, Дэниел (1991). «Геометрические границы собственных значений цепей Маркова» . Анналы прикладной теории вероятности . 1 (1). Институт математической статистики: 36–61. ISSN   1050-5164 . JSTOR   2959624 . Проверено 14 апреля 2024 г.