78
правок
Изменения
Нет описания правки
{{Определение
|definition=
}}
{{Определение
|definition=
Стохастическую матрицу с <tex>r</tex> [[Марковская цепь#Поглощающая цепь|поглощающими состояниями]] и <tex>t</tex> непоглощающими, можно перевести в '''каноническую форму'''Канонической формой матрицы цепи Маркова(англ. ''canonical form', является матрица вида'):
<tex>P = \begin{pmatrix}
Q & R \\
0 & I
\end{pmatrix}</tex>, где <tex>I - </tex> — единичная матрица(<tex>r \times r</tex>), <tex>0 –нулевая </tex> — нулевая матрица(<tex>r \times t</tex>), <tex>R – </tex> — ненулевая поглощающая матрица (<tex>t \times r</tex>) и <tex>Q - </tex> — непоглощающая(<tex>t \times t</tex>). Первые <tex>t</tex> состояний переходные и последние <tex>r</tex> состояний поглощающие.
}}
Теорема
|about=о поглощении
|statement=Если цепь поглощающая, то с вероятностью, равной <tex>1</tex>, она перейдет в [[Марковская цепь#Поглощающая цепь№|поглощающее состояние]].
|proof=
Пусть <tex>P</tex> - — [[Марковская цепь|матрица переходов]], где элемент <tex>p_{ij}</tex> равен вероятности перехода из <tex>i</tex>-го состояния в <tex>j</tex>-ое. Она будет выглядеть как матрица из 4-х блоков, где <tex>Q</tex> - непоглощающие состояния, а <tex>R</tex> и <tex>I</tex> - поглощающие (т.к. цепь поглощающая, то из любого непоглощающего можно попасть Приведем ее в поглощающее). <tex>I</tex> - единичная матрица.каноническую форму:
Пусть вектор <tex>c^{(t)}</tex> - — вектор вероятности нахождения на шаге <tex>t</tex>.
Он вычисляется, как произведение вектора на нулевом шаге на матрицу перехода в степени <tex>t</tex>.
<tex> c^{(t)} = c^{(0)} \times P^t</tex>
\end{pmatrix}</tex> .
Произведение единичной матрицы на саму себя есть единичная матрица (<tex>I \times I = I</tex>); <tex>X</tex> - — некоторые значения (не важны для доказательства теоремы, т.к. так как чтобы доказать теорему достаточно доказать, что непоглощающие состояния стремятся к 0).
Продолжив вычисления, получим, что <tex>P^n</tex> имеет такой следующий вид: <tex>\begin{pmatrix}
Q^n & X \\
0 & I
Рассмотрим путь из <tex>i</tex>-го состояния в поглощающее, равное состояние <tex>m_ij</tex>. Пусть мы совершили <tex>m</tex> шагов из состояния <tex>i</tex>p, тогда обозначим <1tex>p_{m}</tex> - — вероятность тогопопасть в поглощающее состояние <tex>j</tex> за такое количество шагов. Заметим, что через <tex>m_ip_{m} < 1</tex> Теперь обобщим в большую сторону для любого количества шагов из шага : пусть <tex>p = \max(p_{m})< 1</tex>. В таком случае <tex>ip</tex> не попадет — наибольшая вероятность попасть в поглощающее состояние<tex>j</tex>, совершив при этом не более чем <tex>m</tex> шагов.Пусть Тогда вероятность перехода в состояние <tex>j</tex> на шаге <tex>m</tex> равна <tex>p_{m } = max(m_i)\sum\limits_{j} {q^{m}_{ij}}</tex>, а где <tex>q_{ij}^{m}</tex>p = max(p_i)— элемент матрицы < 1tex>Q^{m}</tex>.
В итоге получаем, что непоглощающие состояния стремятся к <tex>0</tex>, а значит поглощающие в итоге приходят к <tex>1</tex>, т.е. то есть цепь приходит в поглощающее состояние.
}}
== См.также ==
* [[Марковская цепь]]
* [[Эргодическая марковская цепь]]
* [[Регулярная марковская цепь]]
== Источники информации ==
* ''Дж. Кемени, Дж. Снелл'' — "Конечные цепи Маркова", издание "Наука", 1970г., стр. 62
[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Марковские цепи ]]