78
правок
Изменения
Нет описания правки
{{Определение|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> ,
|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>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</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>, то есть цепь приходит в поглощающее состояние.}} ==См.также ==* [[Марковская цепь]]* [[Эргодическая марковская цепь]]* [[Регулярная марковская цепь]] И== Источники информации ==* ''Дж.ВКемени, Дж. Романовский Снелл'' — "Дискретный анализКонечные цепи Маркова", 2003издание "Наука", 1970г., стр. 62 [[Категория:Дискретная математика и алгоритмы]] [[Категория: Марковские цепи ]]