Чигер связан

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

Пусть будет конечным множеством и пусть будет вероятностью перехода для обратимой цепи Маркова на . Предположим, что эта цепь имеет стационарное распределение . ${\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)\leq {\frac {1}{2}}}{\frac {Q(S\times S^{c})}{\pi (S)}}.}$

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

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

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

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

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

Смотрите также

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

Ссылки

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