Теорема о поглощении — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 5: Строка 5:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Написать про каноническую форму стохастической матрицы(<tex>P = \begin{pmatrix}
+
Квадратные матрицы, для которых выполняются следующие условия:
Q & R \\      
+
:<tex>0 < p_{ij} < 1</tex>
0 & I
+
:<tex>\sum\limits_{j = 1}^{k} p_{ij} = 1 ~~~ (i = 1, 2, ..., k)</tex>
\end{pmatrix}</tex>)
+
называются '''стохастическими'''.
 
}}
 
}}
  

Версия 20:50, 21 февраля 2012

Утверждение:
Состояние является поглощающим(сюда ссылку на определение поглощающего состояния) тогда и только тогда, когда [math] p_{ii} = 1[/math].


Определение:
Квадратные матрицы, для которых выполняются следующие условия:
[math]0 \lt p_{ij} \lt 1[/math]
[math]\sum\limits_{j = 1}^{k} p_{ij} = 1 ~~~ (i = 1, 2, ..., k)[/math]
называются стохастическими.


Теорема (о поглощении):
Если цепь поглощающая, то с вероятностью, равной 1, она перейдет в поглощающее состояние.
Доказательство:
[math]\triangleright[/math]

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


Рассмотрим путь из i-го состояния в поглощающее, равное [math]m_i[/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]