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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство теоремы)
м (rollbackEdits.php mass rollback)
 
(не показано 47 промежуточных версий 9 участников)
Строка 1: Строка 1:
== Формулировка теоремы ==
+
{{Определение
 +
|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> ,
  
С вероятностью, равной 1, марковская цепь перейдет в поглощающее состояние.
+
где <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>, она перейдет в [[Марковская цепь#Поглощающая цепь№|поглощающее состояние]].
  
Пусть '''''P''''' - матрица переходов, где элемент <tex>p_{ij}</tex> равен вероятности перехода из i-го состояния в j-ое, а  <tex>p^{(t)}</tex> вектор вероятностей нахождения в определенном состоянии на шаге ''t'', тогда, если все элементы матрицы переходных состояний '''''P''''' положительны, то при ''t'' , стремящимся к бесконечности, вектор <tex>p^{(t)}</tex> стремится к вектору <tex>\bar p</tex>, являющемуся единственному решению системы <tex>p \times P=p </tex>
+
|proof=
 +
Пусть <tex>P</tex> — [[Марковская цепь|матрица переходов]], где элемент <tex>p_{ij}</tex> равен вероятности перехода из <tex>i</tex>-го состояния в <tex>j</tex>-ое. Приведем ее в каноническую форму:
  
  
== Доказательство теоремы ==
+
<tex>P = \begin{pmatrix}
 +
Q & R \\       
 +
0 & I
 +
\end{pmatrix}</tex>
  
Обозначим через ''d'' минимальный элемент матрицы '''''P''''' (''d''>0). Введем функцию ''f'', переводящую вероятностный вектор в другой: <tex>f=p \times P</tex>. Отображение ''f'' сжимающиеся, т.е. отношение "расстояния" между ''f(p)'' и ''f(q)'' к расстоянию между векторами p и q не превосходит, некоторого ''R'' (''R''<1).
 
  
Пусть расстояние между ''p'' и ''q'' равно: <tex>r(p,r) = \sum_{i} {|p_i - q_i|}</tex>
+
Пусть вектор <tex>c^{(t)}</tex> — вектор вероятности нахождения на шаге <tex>t</tex>.
 +
Он вычисляется, как произведение вектора на нулевом шаге на матрицу перехода в степени <tex>t</tex>.
 +
<tex> c^{(t)} = c^{(0)} \times P^t</tex>
 +
Рассмотрим, что представляет из себя возведение матрицы <tex>P</tex> в степень:
  
Введем матрицу '''''D''''', элементы которой на ''d'' меньше, чем у '''''P'''''. Тогда <tex>f(p) = p \times 1 + p \times D</tex>. Таким образом  <tex>f(p) - f(q) = {(p- q)} \times D</tex>.
 
  
Подставляем это выражение в определение расстояния и получаем выражение:
+
Для <tex>t = 2</tex> :
  
<tex>r(f(p), f(q)) = \sum_{i} {|\sum_{j}{p_j D_{ji}} - \sum_{j}{q_i D_{ji}}|} <= \sum_{i}{\sum_{j}{D_{ij}|p_j - q_j|}} =  r(p,q)*(1- md)</tex>
+
<tex>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}</tex> .
  
Где <tex>(1-md)< 1</tex>, следовательно оно равно ''R''.
+
Произведение единичной матрицы на саму себя есть единичная матрица (<tex>I \times I = I</tex>); <tex>X</tex> — некоторые значения (не важны для доказательства теоремы, так как чтобы доказать теорему достаточно доказать, что непоглощающие состояния стремятся к 0).
  
В итоге получаем  <tex>r(pP,qP)\leqslant R \times r(p,q)</tex>, из которого следует для любого ''n''  <tex>r(pP^n,qP^n)\leqslant R^n \times r(p,q)</tex>. Отсюда получаем сходимость <tex>p^{(0)}P^n</tex>. И переходя в исходном уравнении к пределу в итоге получаем уравнение для предельного вектора <tex>\bar p</tex> : <tex>\bar p = \bar p P</tex>.
+
Продолжив вычисления, получим, что <tex>P^n</tex> имеет следующий вид: <tex>\begin{pmatrix}
 +
Q^n & X \\      
 +
0 & I
 +
\end{pmatrix}</tex> .
  
Единственность решения для уравнения следует из этого же неравенства. Если <tex>p_1</tex> и <tex>p_2</tex> решения системы, то получаем <tex>r(p_1,p_2)=(r(p_1P,p_2P)\leqslant R \times r(p_1,p_2)</tex>, что возможно только при совпадении этих решений.
+
Докажем, что <tex>Q^n \xrightarrow{} 0</tex>, при <tex> n\xrightarrow{}+\infty</tex>.
  
== Используемая литература ==
+
 
И.В. Романовский "Дискретный анализ", 2003
+
Рассмотрим путь из <tex>i</tex>-го состояния в поглощающее состояние <tex>j</tex>. Пусть мы совершили <tex>m</tex> шагов из состояния <tex>i</tex>, тогда обозначим <tex>p_{m}</tex> — вероятность попасть в поглощающее состояние <tex>j</tex> за такое количество шагов. Заметим, что <tex>p_{m} < 1</tex>
 +
 
 +
Теперь обобщим в большую сторону для любого количества шагов: пусть <tex>p = \max(p_{m})< 1</tex>. В таком случае <tex>p</tex> — наибольшая вероятность попасть в поглощающее состояние <tex>j</tex>, совершив при этом не более чем <tex>m</tex> шагов.
 +
 
 +
Тогда вероятность перехода в состояние <tex>j</tex> на шаге <tex>m</tex> равна <tex>p_{m} = \sum\limits_{j} {q^{m}_{ij}}</tex>, где  <tex>q_{ij}^{m}</tex> — элемент матрицы <tex>Q^{m}</tex>.
 +
 
 +
В то же время, <tex>\sum\limits_{j} {q^m_{ij}}\leqslant p</tex> потому что <tex>p_{m} \leqslant p, \forall m</tex> по условию обозначения <tex>p</tex>. Возведем обе части в степень <tex>k \rightarrow \infty</tex>, получим:  <tex>\sum\limits_{j} {q^{mk}_{ij}}\leqslant p^k\xrightarrow{k\xrightarrow{}+\infty}0</tex>
 +
 
 +
В итоге получаем, что непоглощающие состояния стремятся к <tex>0</tex>, а значит поглощающие в итоге приходят к <tex>1</tex>, то есть цепь приходит в поглощающее состояние.
 +
}}
 +
 
 +
== См.также ==
 +
* [[Марковская цепь]]
 +
* [[Эргодическая марковская цепь]]
 +
* [[Регулярная марковская цепь]]
 +
 
 +
== Источники информации ==
 +
* ''Дж. Кемени, Дж. Снелл'' — "Конечные цепи Маркова", издание "Наука", 1970г., стр. 62
 +
 
 +
[[Категория:Дискретная математика и алгоритмы]]
 +
 
 +
[[Категория: Марковские цепи ]]

Текущая версия на 19:18, 4 сентября 2022

Определение:
Матрицу [math]Q[/math] называют непоглощающей (англ. not-absorbing), если она не содержит поглощающих состояний. То есть [math]q_{ii} \neq 1, \forall i [/math]


Определение:
Стохастическую матрицу с [math]r[/math] поглощающими состояниями и [math]t[/math] непоглощающими, можно перевести в каноническую форму (англ. canonical form):

[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]1[/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]m[/math] шагов из состояния [math]i[/math], тогда обозначим [math]p_{m}[/math] — вероятность попасть в поглощающее состояние [math]j[/math] за такое количество шагов. Заметим, что [math]p_{m} \lt 1[/math]

Теперь обобщим в большую сторону для любого количества шагов: пусть [math]p = \max(p_{m})\lt 1[/math]. В таком случае [math]p[/math] — наибольшая вероятность попасть в поглощающее состояние [math]j[/math], совершив при этом не более чем [math]m[/math] шагов.

Тогда вероятность перехода в состояние [math]j[/math] на шаге [math]m[/math] равна [math]p_{m} = \sum\limits_{j} {q^{m}_{ij}}[/math], где [math]q_{ij}^{m}[/math] — элемент матрицы [math]Q^{m}[/math].

В то же время, [math]\sum\limits_{j} {q^m_{ij}}\leqslant p[/math] потому что [math]p_{m} \leqslant p, \forall m[/math] по условию обозначения [math]p[/math]. Возведем обе части в степень [math]k \rightarrow \infty[/math], получим: [math]\sum\limits_{j} {q^{mk}_{ij}}\leqslant p^k\xrightarrow{k\xrightarrow{}+\infty}0[/math]

В итоге получаем, что непоглощающие состояния стремятся к [math]0[/math], а значит поглощающие в итоге приходят к [math]1[/math], то есть цепь приходит в поглощающее состояние.
[math]\triangleleft[/math]

См.также

Источники информации

  • Дж. Кемени, Дж. Снелл — "Конечные цепи Маркова", издание "Наука", 1970г., стр. 62