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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 7: Строка 7:
 
|proof=
 
|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</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}
 
<tex>P = \begin{pmatrix}
Строка 12: Строка 13:
 
0 & I
 
0 & I
 
\end{pmatrix}</tex>
 
\end{pmatrix}</tex>
 +
  
 
Пусть вектор <tex>c^{(t)}</tex> - вектор вероятности нахождения на шаге <tex>t</tex>.
 
Пусть вектор <tex>c^{(t)}</tex> - вектор вероятности нахождения на шаге <tex>t</tex>.
Строка 18: Строка 20:
 
Рассмотрим, что представляет из себя возведение матрицы <tex>P</tex>  в степень:
 
Рассмотрим, что представляет из себя возведение матрицы <tex>P</tex>  в степень:
  
для <tex>t = 2</tex> :
+
 
 +
Для <tex>t = 2</tex> :
 +
 
 +
<tex>P^{2} =</tex>
 
<tex>\begin{pmatrix}
 
<tex>\begin{pmatrix}
 
Q & R \\         
 
Q & R \\         
Строка 27: Строка 32:
 
Q & R \\         
 
Q & R \\         
 
0 & I
 
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}
 
=
 
=
Строка 33: Строка 43:
 
0 & I
 
0 & I
 
\end{pmatrix}</tex> .
 
\end{pmatrix}</tex> .
 +
 +
<tex>(</tex>Произведение единичной матрицы на саму себя есть единичная матрица <tex>(I \times I = I);</tex> <tex>X</tex> - некоторые значения<tex>).</tex>
  
 
Отсюда видно, что <tex>P^n</tex> имеет такой вид: <tex>\begin{pmatrix}
 
Отсюда видно, что <tex>P^n</tex> имеет такой вид: <tex>\begin{pmatrix}
Строка 40: Строка 52:
  
 
Следовательно нам надо доказать, что <tex>Q^n \xrightarrow{} 0</tex>, при <tex> n\xrightarrow{}+\infty</tex>
 
Следовательно нам надо доказать, что <tex>Q^n \xrightarrow{} 0</tex>, при <tex> n\xrightarrow{}+\infty</tex>
 +
  
 
Рассмотрим путь из i-го состояния в поглощающее, равное <tex>m_i</tex>. Пусть <tex>p<1</tex> - вероятность того, что через <tex>m_i</tex> шагов из шага <tex>i</tex> не попадет в поглощающее состояние.
 
Рассмотрим путь из i-го состояния в поглощающее, равное <tex>m_i</tex>. Пусть <tex>p<1</tex> - вероятность того, что через <tex>m_i</tex> шагов из шага <tex>i</tex> не попадет в поглощающее состояние.

Версия 21:14, 12 января 2012

Теорема (о поглощении):
С вероятностью, равной [math]1[/math], марковская цепь перейдет в поглощающее состояние, если у нее существует такое состояние.
Доказательство:
[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} =[/math] [math]\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]([/math]Произведение единичной матрицы на саму себя есть единичная матрица [math](I \times I = I);[/math] [math]X[/math] - некоторые значения[math]).[/math]

Отсюда видно, что [math]P^n[/math] имеет такой вид: [math]\begin{pmatrix} Q^n & X \\ 0 & I \end{pmatrix}[/math] , где [math]X[/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]