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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
'''Формулировка'''
 
'''Формулировка'''
  
−
С вероятностью, равной 1, марковская цепь перейдет в поглощающее состояние.
+
С вероятностью, равной 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 P</tex>. Отображение ''f'' сжимающиеся, т.е. отношение "расстояния" между ''f(p)'' и ''f(q)'' к расстоянию между векторами ''p'' и ''q'' не превосходит, некоторого ''R'' (''R''<1).
+
Пусть '''''P''''' - матрица переходов, где элемент <tex>p_{ij}</tex> равен вероятности перехода из i-го состояния в j-ое. Она будет выглядеть как матрица из 4-х блоков, где Q - несущественные состояния, а R и I - существенные.(т.к. цепь поглощающая, то из любого несущественного можно попасть в существенное)
−
 
+
[[Файл:Матрница_перехода.GIF‎]]
−
Пусть расстояние между ''p'' и ''q'' равно: <tex>r(p,r) = \sum_{i} {|p_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>.
 
  
−
Подставляем это выражение в определение расстояния и получаем выражение:
+
Пусть вектор <tex>c^{(t)}</tex> - вектор вероятности нахождения на шаге t.
 +
Он вычисляется, как произведение вектора на нулевом шаге на матрицу перехода в степени t.
 +
<tex> c^{(t)} = c^{(0)} * P^t</tex>
 +
Рассмотрим, что представляет из себя возведение матрицы P  в степень:
  
−
<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>
+
для t=1 :
 +
[[Файл:Матрница перехода (перемножение).GIF]]
 +
Отсюда видно, что <tex> P^n</tex> имеет такой вид, где X - некоторые значения.
 +
[[Файл:Vfnhbwf d n-jq cntgtyb.GIF]]
  
−
Где <tex>(1-md)< 1</tex>, следовательно оно равно ''R''.
+
Следовательно нам надо доказать, что <tex>Q^n \xrightarrow{} 0</tex>, при <tex> n\xrightarrow{}+\infty</tex>
  
−
В итоге получаем  <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>.
+
Рассмотрим путь из i-го состояния в поглощающее, равное <tex>m_i</tex>. Пусть <tex>p<1</tex> - вероятность того, что через <tex>m_i</tex> шагов из шага i не попадет в поглощающее состояние.
 +
Пусть <tex>m = max(m_i)</tex>, а <tex>p = max(p_i)< 1</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>\sum_{j} {Q^m_{ij}}\leqslant p</tex> <tex>\Rightarrow</tex> <tex>\sum_{j} {Q^{mk}_{ij}}\leqslant p^k\xrightarrow{k\xrightarrow{}+\infty}0</tex>
  
−
== Используемая литература ==
+
В итоге получаем, что несущественные состояния стремятся к 0, а значит существенные в итоге приходят к 1, т.е. цепь приходит в поглощающее состояние.
−
И.В. Романовский "Дискретный анализ", 2003
 

Версия 00:10, 16 января 2011

Формулировка теоремы

Формулировка

С вероятностью, равной 1, марковская цепь перейдет в поглощающее состояние, если у нее существует такое состояние.

Доказательство теоремы

Пусть P - матрица переходов, где элемент [math]p_{ij}[/math] равен вероятности перехода из i-го состояния в j-ое. Она будет выглядеть как матрица из 4-х блоков, где Q - несущественные состояния, а R и I - существенные.(т.к. цепь поглощающая, то из любого несущественного можно попасть в существенное) Матрница перехода.GIF

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

для t=1 : Матрница перехода (перемножение).GIF Отсюда видно, что [math] P^n[/math] имеет такой вид, где X - некоторые значения. Vfnhbwf d n-jq cntgtyb.GIF

Следовательно нам надо доказать, что [math]Q^n \xrightarrow{} 0[/math], при [math] n\xrightarrow{}+\infty[/math]

Рассмотрим путь из i-го состояния в поглощающее, равное [math]m_i[/math]. Пусть [math]p\lt 1[/math] - вероятность того, что через [math]m_i[/math] шагов из шага i не попадет в поглощающее состояние. Пусть [math]m = max(m_i)[/math], а [math]p = max(p_i)\lt 1[/math]

Тогда получаем: [math]\sum_{j} {Q^m_{ij}}\leqslant p[/math] [math]\Rightarrow[/math] [math]\sum_{j} {Q^{mk}_{ij}}\leqslant p^k\xrightarrow{k\xrightarrow{}+\infty}0[/math]

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теорема_о_поглощении&oldid=7050»