78
правок
Изменения
Нет описания правки
{{Определение
|definition=
Матрицу <tex>Q</tex> называют '''непоглощающей''' (англ. ''not-absorbing''), если она не содержит поглощающих состояний. То есть <tex>q_{ii} \neq 1, \forall i </tex>
}}
{{Определение
|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>P = \begin{pmatrix}
\end{pmatrix}</tex>
Пусть вектор <tex>c^{(t)}</tex> - — вектор вероятности нахождения на шаге <tex>t</tex>.
Он вычисляется, как произведение вектора на нулевом шаге на матрицу перехода в степени <tex>t</tex>.
<tex> c^{(t)} = c^{(0)} * \times P^t</tex>
Рассмотрим, что представляет из себя возведение матрицы <tex>P</tex> в степень:
Q & R \\
0 & I
\end{pmatrix}
\begin{pmatrix}
Q & R \\
0 & I
\end{pmatrix}
=
\begin{pmatrix}
Q \times Q + R \times 0 & Q \times R + R \times I \\
0 \times Q + I \times 0 & 0 \times R + I \times I
\end{pmatrix}
=
\end{pmatrix}</tex> .
Q^n & X \\
0 & I
\end{pmatrix}</tex> . Докажем, что <tex>Q^n \xrightarrow{} 0</tex> , где при <tex> n\xrightarrow{}+\infty</tex>. Рассмотрим путь из <tex>Xi</tex> - некоторые значенияго состояния в поглощающее состояние <tex>j</tex>.Пусть мы совершили <tex>m</tex> шагов из состояния <tex>i</tex>, тогда обозначим <tex>p_{m}</tex> — вероятность попасть в поглощающее состояние <tex>j</tex> за такое количество шагов. Заметим, что <tex>p_{m} < 1</tex>
В итоге получаем, что несущественные непоглощающие состояния стремятся к <tex>0</tex>, а значит существенные поглощающие в итоге приходят к <tex>1</tex>, т.е. то есть цепь приходит в поглощающее состояние.
}}
== См.также ==
* [[Марковская цепь]]
* [[Эргодическая марковская цепь]]
* [[Регулярная марковская цепь]]
== Источники информации ==
* ''Дж. Кемени, Дж. Снелл'' — "Конечные цепи Маркова", издание "Наука", 1970г., стр. 62
[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Марковские цепи ]]