Изменения

С вероятностью, равной 1, марковская цепь перейдет в поглощающее состояние. '''Альтернативная формулировка''' Пусть '''''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>у нее существует такое состояние.

Обозначим через ''d'' минимальный элемент матрицы Пусть '''''P''''' (''d''>0). Введем функцию ''f''- матрица переходов, переводящую вероятностный вектор в другой: где элемент <tex>f=p \times Pp_{ij}</tex>равен вероятности перехода из i-го состояния в j-ое. Отображение ''f'' сжимающиесяОна будет выглядеть как матрица из 4-х блоков, т.е. отношение "расстояния" между ''f(p)'' и ''f(q)'' к расстоянию между векторами ''p'' и ''q'' не превосходитгде Q - несущественные состояния, некоторого ''R'' (''а R''<1). Пусть расстояние между ''p'' и ''q'' равно: <tex>r(p,r) = \sum_{i} {|p_i I - q_i|}</tex> Введем матрицу '''''D''''', элементы которой на ''d'' меньше, чем у '''''P'''''существенные. Тогда <tex>f(p) = p \times 1 + p \times D</tex>т.к. Таким образом <tex>f(pцепь поглощающая, то из любого несущественного можно попасть в существенное) - f(q) = {(p- q)} \times D</tex>[[Файл:Матрница_перехода.GIF‎]]

Подставляем это выражение Пусть вектор <tex>c^{(t)}</tex> - вектор вероятности нахождения на шаге t.Он вычисляется, как произведение вектора на нулевом шаге на матрицу перехода в определение расстояния и получаем выражениестепени t. <tex> c^{(t)} = c^{(0)} * P^t</tex>Рассмотрим, что представляет из себя возведение матрицы P в степень:

<tex>rдля t=1 :[[Файл:Матрница перехода (f(pперемножение).GIF]]Отсюда видно, 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> P^n</tex>имеет такой вид, где X - некоторые значения.[[Файл:Vfnhbwf d n-jq cntgtyb.GIF]]

Где Следовательно нам надо доказать, что <tex>(1-md)Q^n \xrightarrow{} 0< 1/tex>, при <tex> n\xrightarrow{}+\infty</tex>, следовательно оно равно ''R''.

В итоге получаем Рассмотрим путь из i-го состояния в поглощающее, равное <tex>r(pP,qP)\leqslant R \times r(p,q)m_i</tex>, из которого следует для любого ''n'' . Пусть <tex>r(pP^n,qP^n)\leqslant R^n \times r(p,q)<1</tex>. Отсюда получаем сходимость - вероятность того, что через <tex>p^{(0)}P^nm_i</tex>шагов из шага i не попадет в поглощающее состояние. И переходя в исходном уравнении к пределу, в итоге получаем уравнение для предельного вектора Пусть <tex>\bar pm = max(m_i)</tex> , а <tex>\bar p = \bar p Pmax(p_i)< 1</tex>.

Единственность решения для уравнения следует из этого же неравенства. Если Тогда получаем: <tex>p_1\sum_{j} {Q^m_{ij}}\leqslant p</tex> и <tex>p_2\Rightarrow</tex> решения системы, то получаем <tex>r(p_1,p_2)=r(p_1P,p_2P)\sum_{j} {Q^{mk}_{ij}}\leqslant R p^k\xrightarrow{k\xrightarrow{}+\times r(p_1,p_2)infty}0</tex>, что возможно только при совпадении этих решений.

== Используемая литература ==ИВ итоге получаем, что несущественные состояния стремятся к 0, а значит существенные в итоге приходят к 1, т.Ве. цепь приходит в поглощающее состояние. Романовский "Дискретный анализ", 2003