Теорема о поглощении

Материал из Викиконспекты
Перейти к: навигация, поиск

Формулировка теоремы

Формулировка

С вероятностью, равной 1, марковская цепь перейдет в поглощающее состояние, если у нее существует такое состояние.

Доказательство теоремы

Пусть P - матрица переходов, где элемент [math]p_{ij}[/math] равен вероятности перехода из i-го состояния в j-ое. Она будет выглядеть как матрица из 4-х блоков, где Q - несущественные состояния, а R и I - существенные.(т.к. цепь поглощающая, то из любого несущественного можно попасть в существенное) Матрница перехода.GIF

Пусть вектор [math]c^{(t)}[/math] - вектор вероятности нахождения на шаге t. Он вычисляется, как произведение вектора на нулевом шаге на матрицу перехода в степени t. [math] c^{(t)} = c^{(0)} * P^t[/math] Рассмотрим, что представляет из себя возведение матрицы P в степень:

для t=1 : Матрница перехода (перемножение).GIF Отсюда видно, что [math] P^n[/math] имеет такой вид, где X - некоторые значения. Vfnhbwf d n-jq cntgtyb.GIF

Следовательно нам надо доказать, что [math]Q^n \xrightarrow{} 0[/math], при [math] n\xrightarrow{}+\infty[/math]

Рассмотрим путь из i-го состояния в поглощающее, равное [math]m_i[/math]. Пусть [math]p\lt 1[/math] - вероятность того, что через [math]m_i[/math] шагов из шага i не попадет в поглощающее состояние. Пусть [math]m = max(m_i)[/math], а [math]p = max(p_i)\lt 1[/math]

Тогда получаем: [math]\sum_{j} {Q^m_{ij}}\leqslant p[/math] [math]\Rightarrow[/math] [math]\sum_{j} {Q^{mk}_{ij}}\leqslant p^k\xrightarrow{k\xrightarrow{}+\infty}0[/math]

В итоге получаем, что несущественные состояния стремятся к 0, а значит существенные в итоге приходят к 1, т.е. цепь приходит в поглощающее состояние.