Изменения

{{Определение|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> состояний поглощающие.}}

|proof=Пусть '''''<tex>P''''' - </tex> — [[Марковская цепь|матрица переходов]], где элемент <tex>p_{ij}</tex> равен вероятности перехода из i-го состояния в j-ое, а <tex>p^{(t)}i</tex> вектор вероятностей нахождения -го состояния в определенном состоянии на шаге ''t'', тогда, если все элементы матрицы переходных состояний '''''P''''' положительны, то при ''t'' , стремящимся к бесконечности, вектор <tex>p^{(t)}</tex> стремится к вектору <tex>\bar p</tex>, являющемуся единственному решению системы <tex>p \times P=p j</tex>-ое. Приведем ее в каноническую форму:

<tex>P == Доказательство теоремы ==\begin{pmatrix}Q & R \\ 0 & I\end{pmatrix}</tex>

Пусть расстояние между ''p'' и ''q'' равно: вектор <tex>rc^{(pt)}</tex> — вектор вероятности нахождения на шаге <tex>t</tex>.Он вычисляется,rкак произведение вектора на нулевом шаге на матрицу перехода в степени <tex>t</tex>. <tex> c^{(t) } = \sum_c^{i} {|p_i - q_i|(0)}\times P^t</tex>Рассмотрим, что представляет из себя возведение матрицы <tex>P</tex> в степень:

Подставляем это выражение в определение расстояния и получаем выражениеДля <tex>t = 2</tex> :

<tex>r(f(p), f(q)) P^{2} = \sum_begin{ipmatrix} Q & R \\ 0 & I\end{|pmatrix}\sum_times\begin{jpmatrix}Q & R \\ 0 & I\end{p_j D_{jipmatrix}} - =\sum_begin{jpmatrix}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{q_i D_{ji}}|pmatrix} <= \sum_begin{ipmatrix}{Q^2 & X \\ 0 & I\sum_end{jpmatrix}{D_{ij}|p_j - q_j|}} = r(p,q)*(1- md)</tex>.

Где Произведение единичной матрицы на саму себя есть единичная матрица (<tex>I \times I = I</tex>(1-md); < 1tex>X</tex>— некоторые значения (не важны для доказательства теоремы, следовательно оно равно ''R''так как чтобы доказать теорему достаточно доказать, что непоглощающие состояния стремятся к 0).

В итоге получаем <tex>r(pPПродолжив вычисления,qP)\leqslant R \times r(pполучим,q)что </tex>, из которого следует для любого ''n'' <tex>r(pP^n,qPP^n)\leqslant R^n \times r(p,q)</tex>. Отсюда получаем сходимость имеет следующий вид: <tex>p^\begin{(0)pmatrix}PQ^n</tex>. И переходя в исходном уравнении к пределу в итоге получаем уравнение для предельного вектора <tex>& X \bar p</tex> : <tex>\bar p = 0 & I\bar p Pend{pmatrix}</tex>.

Единственность решения для уравнения следует из этого же неравенства. Если Докажем, что <tex>p_1Q^n \xrightarrow{} 0</tex> и <tex>p_2</tex> решения системы, то получаем при <tex>r(p_1,p_2)=(r(p_1P,p_2P)n\leqslant R xrightarrow{}+\times r(p_1,p_2)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>, то есть цепь приходит в поглощающее состояние.}} == См.также ==* [[Марковская цепь]]* [[Эргодическая марковская цепь]]* [[Регулярная марковская цепь]] == Используемая литература Источники информации ==И* ''Дж.ВКемени, Дж. Романовский Снелл'' — "Конечные цепи Маркова", издание "Дискретный анализНаука", 20031970г., стр. 62 [[Категория:Дискретная математика и алгоритмы]] [[Категория: Марковские цепи ]]