Изменения

{{Определение|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>), равной 1<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-х блоков, где '''''Q''''' - несущественные состояния, а '''''R''''' и '''''I''''' - существенные.(т.к. цепь поглощающая, то из любого несущественного можно попасть Приведем ее в существенное) '''''I''''' - единичная матрица.[[Файлканоническую форму:Матрница_перехода.GIF‎]]

для ''t<tex>P =1'' :\begin{pmatrix}[[Файл:Матрница перехода (перемножение).GIF]]Q & R \\ 0 & I\end{pmatrix}</tex>

Следовательно нам надо доказать, что Пусть вектор <tex>Qc^n \xrightarrow{(t)} 0</tex>— вектор вероятности нахождения на шаге <tex>t</tex>.Он вычисляется, при как произведение вектора на нулевом шаге на матрицу перехода в степени <tex>t</tex>. <tex> n\xrightarrowc^{(t)} = c^{(0)}+\inftytimes P^t</tex>Рассмотрим, что представляет из себя возведение матрицы <tex>P</tex> в степень:

Тогда получаем: Для <tex>\sum_{j} {Q^m_{ij}}\leqslant p</tex> <tex>\Rightarrow</tex> <tex>\sum_{j} {Q^{mk}_{ij}}\leqslant p^k\xrightarrow{k\xrightarrow{}+\infty}0t = 2</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>I \times I = I</tex>); <tex>X</tex> — некоторые значения (не важны для доказательства теоремы, так как чтобы доказать теорему достаточно доказать, что непоглощающие состояния стремятся к 0). Продолжив вычисления, получим, что <tex>P^n</tex> имеет следующий вид: <tex>\begin{pmatrix}Q^n & X \\ 0 & I\end{pmatrix}</tex> . Докажем, что <tex>Q^n \xrightarrow{} 0</tex>, при <tex> n\xrightarrow{}+\infty</tex>.  Рассмотрим путь из <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 [[Категория:Дискретная математика и алгоритмы]]