Материал из Викиконспекты
| Определение: |
| Матрицу [math]Q[/math] называют непоглощающей, если она не содержит поглощающих состояний. То есть [math]\forall i : q_{ii} \neq 1[/math] |
| Определение: |
| Стохастическую матрицу с [math]r[/math] поглощающими состояниями и [math]t[/math] непоглощающими, можно перевести в каноническую форму:
[math]P = \begin{pmatrix}
Q & R \\
0 & I
\end{pmatrix}[/math] ,
где [math]I[/math] — единичная матрица ([math]r \times r[/math]), [math]0[/math] — нулевая матрица ([math]r \times t[/math]), [math]R[/math] — ненулевая поглощающая матрица ([math]t \times r[/math]) и [math]Q[/math] — непоглощающая ([math]t \times t[/math]). Первые [math]t[/math] состояний переходные и последние [math]r[/math] состояний поглощающие. |
| Теорема (о поглощении): |
|
| Доказательство: |
| [math]\triangleright[/math] |
|
Пусть [math]P[/math] — матрица переходов, где элемент [math]p_{ij}[/math] равен вероятности перехода из [math]i[/math]-го состояния в [math]j[/math]-ое. Приведем ее в каноническую форму:
[math]P = \begin{pmatrix}
Q & R \\
0 & I
\end{pmatrix}[/math]
Пусть вектор [math]c^{(t)}[/math] — вектор вероятности нахождения на шаге [math]t[/math].
Он вычисляется, как произведение вектора на нулевом шаге на матрицу перехода в степени [math]t[/math].
[math] c^{(t)} = c^{(0)} \times P^t[/math]
Рассмотрим, что представляет из себя возведение матрицы [math]P[/math] в степень:
Для [math]t = 2[/math] :
[math]P^{2} =
\begin{pmatrix}
Q & R \\
0 & I
\end{pmatrix}
\times
\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}
=
\begin{pmatrix}
Q^2 & X \\
0 & I
\end{pmatrix}[/math] .
Произведение единичной матрицы на саму себя есть единичная матрица ([math]I \times I = I[/math]); [math]X[/math] — некоторые значения (не важны для доказательства теоремы, т.к. чтобы доказать теорему достаточно доказать, что непоглощающие состояния стремятся к 0).
Продолжив вычисления, получим, что [math]P^n[/math] имеет следующий вид: [math]\begin{pmatrix}
Q^n & X \\
0 & I
\end{pmatrix}[/math] .
Докажем, что [math]Q^n \xrightarrow{} 0[/math], при [math] n\xrightarrow{}+\infty[/math].
Рассмотрим путь из [math]i[/math]-го состояния в поглощающее, равное [math]j[/math]. Пусть [math]p\lt 1[/math] — вероятность того, что через [math]m_i[/math] шагов из шага [math]i[/math] не попадет в поглощающее состояние.
Пусть [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]
В итоге получаем, что непоглощающие состояния стремятся к [math]0[/math], а значит поглощающие в итоге приходят к [math]1[/math], т.е. цепь приходит в поглощающее состояние. |
| [math]\triangleleft[/math] |
Литература
- Дж. Кемени, Дж. Снелл "Конечные цепи Маркова"
