Редактирование: Расчёт вероятности поглощения в состоянии

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
−
[[Марковская цепь#Поглощающая цепь| Поглощающее состояние]] — состояние с вероятностью перехода в самого себя <tex>p_{ii}=1</tex>.
+
Поглощающее(существенное) состояние цепи Маркова - состояние с вероятностью перехода в самого себя <tex>p_{ii}=1</tex>.
−
 
+
Составим матрицу G, элементы которой <tex>g_{ij}</tex> равны вероятности того, что, выйдя из i, попадём в поглощающее состояние j.
−
Составим матрицу <tex>\mathtt{G}</tex>, элементы которой <tex>g_{ij}</tex> равны вероятности того, что, выйдя из <tex>i</tex>, попадём в поглощающее состояние <tex>j</tex>.
 
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
−
<tex> \mathtt{G} = N \cdot R </tex>, где <tex>N</tex> — фундаментальная матрица, и <tex>R</tex> — матрица перехода из несущественных состояний в существенные.
+
<tex> G = N \cdot R </tex>
 
|proof=
 
|proof=
−
Пусть этот переход будет осуществлён за <tex>r</tex> шагов:  <tex>i</tex> &rarr;  <tex>i_{1}</tex> &rarr; <tex>i_{2}</tex> &rarr; <tex>\ldots</tex> &rarr; <tex>i_{r-1}</tex> &rarr; j, где все <tex>i, i_{1}, \ldots i_{r-1}</tex> являются несущественными.
+
Пусть этот переход будет осуществлён за r шагов:  i &rarr;  <tex>i_{1}</tex> &rarr; <tex>i_{2}</tex> &rarr; ... &rarr; <tex>i_{r-1}</tex> &rarr; j, где все <tex>i, i_{1}, ... i_{r-1}</tex> являются несущественными.
−
Тогда рассмотрим сумму <tex>\sum\limits_{\forall(i_{1} \ldots i_{r-1})} {p_{i, i_{1}} \cdot p_{i_{1}, i_{2}} \cdot \ldots  \cdot p_{i_{r-1}, j}} = Q^{r-1} \cdot R</tex>, где <tex>Q</tex> — матрица переходов между несущественными состояниями, <tex>R</tex> — из несущественного в существенное.  
+
Тогда рассмотрим сумму <tex>\sum\limits_{\forall(i_{1} ... i_{r-1})} {p_{i, i_{1}} \cdot p_{i_{1}, i_{2}} \cdot ... \cdot p_{i_{r-1}, j}} = Q^{r-1} \cdot R</tex>, где Q - матрица переходов между несущественными состояниями, R - из несущественного в существенное.  
−
Матрица <tex>\mathtt{G}</tex> определяется их суммированием по всем длинам пути из i в j: <tex>\mathtt{G} = \sum\limits_{r = 1}^{\infty}{Q^{r-1} \cdot R} = (I + Q + Q^{2} + Q^{3} + \ldots) \cdot R = NR</tex>, т.к. <tex>(I + Q + Q^2 + \ldots) \cdot (I - Q) = I - Q + Q - Q^{2} + \ldots = I</tex>, а фундаментальная матрица марковской цепи <tex>N = (I - Q)^{-1}</tex> }}
+
Матрица G определяется их суммированием по всем длинам пути из i в j: <tex>G = \sum\limits_{r = 1}^{\infty}{Q^{r-1} \cdot R} = (I + Q + Q^{2} + Q^{3} + ...) \cdot R = NR</tex>, т.к. <tex>(I + Q + Q^2 + ...) \cdot (I - Q) = I - Q + Q - Q^{2} + ... = I</tex>, а фундаментальная матрица марковской цепи <tex>N = (I - Q)^{-1}</tex> }}
−
==Псевдокод==
+
=Псевдокод=
−
Выведем ответ: в <tex>\mathtt{i}</tex>-ой строке вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии. Естественно, для несущественного состояния это <tex>0</tex>, в ином случае <tex>\mathtt{p_i}=\left(\sum\limits_{k=1}^{n} \mathtt{G}[k][j]+1\right)/n</tex> где <tex>\mathtt{j}</tex> — номер соответствующий <tex>\mathtt{i}</tex>-ому состоянию в матрице <tex>\mathtt{G}</tex> (т.е. под которым оно располагалось в матрице <tex> \mathtt{R} </tex> т.е. значение <tex>\mathtt{position}[\mathtt{i}]</tex>). Прибавлять <tex>1</tex> нужно т.к. вероятность поглотиться в <tex>\mathtt{i}</tex>-ом поглощающем состоянии, оказавшись изначально в нем же равна <tex>1</tex>.
+
Пусть <tex>n</tex> - количество состояний Марковской цепи, <tex>m</tex> - количество переходов. Состояния пронумерованы от <tex>0</tex> до <tex>n - 1</tex>, переходы от <tex>0</tex> до <tex>m - 1</tex>.  Входные данные хранятся в массиве <tex>input</tex> где <tex>i</tex>-ая строка характеризует <tex>i</tex>-ый переход таким образом: <tex>input[i][2]</tex> - вероятность перехода из состояния <tex>input[i][0]</tex> в состояние <tex>input[i][1]</tex>.
−
*<tex>\mathtt{probability}[\mathtt{i}]</tex> — вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии
+
Создадим массив <tex>absorbing</tex> типа boolean, где <tex>i</tex>-ое true обозначает что <tex>i</tex>-ое состояние является поглощающим и наоборот. Обнаружим поглощающие состояния по такому признаку: если состояние поглощающее, то с вероятностью 1 оно переходит само в себя. Также посчитаем количество поглощающих состояний <tex>abs</tex>.
−
*<tex>\mathtt{absorbing}[\mathtt{i}]</tex> — является ли <tex>\mathtt{i}</tex>-е состояние поглощающим
+
<code style = "display: inline-block;">
−
 
+
'''for''' i = 0 '''to''' m - 1
−
  '''float[]''' getAbsorbingProbability(absorbing: '''boolean'''[n], G: '''float'''[n][n], position: '''int'''[n]):
+
    '''if''' input[i][0] == input[i][1] '''and''' input[i][2] == 1
−
     '''float''' probability[n]
+
      absorbing[input[i][0]] = ''true''
−
   
+
      abs++
−
     '''for''' i = 0 '''to''' n - 1
+
</code>
−
      '''float''' prob = 0
+
Найдем число несущественных состояний <tex>nonabs = n - abs</tex>. Теперь нужно заполнить матрицы <tex>Q</tex> (переходов между несущественными состояниями) и <tex>R</tex> (переходов из несущественных состояний в поглощающие). Для этого создадим сначала массив <tex>position</tex> где <tex>i</tex>-ый элемент указывает под каким номером будет находиться <tex>i</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
−
       '''if''' absorbing[i]
+
<code style = "display: inline-block;">
 +
count_q = 0
 +
count_r = 0
 +
  '''for''' i = 0 '''to''' n - 1
 +
    '''if''' absorbing[i]
 +
      position[i] = count_r
 +
      count_r++
 +
    '''else'''
 +
      position[i] = count_q
 +
      count_q++
 +
'''for''' i = 0 '''to''' m - 1
 +
    '''if''' absorbing[input[i][1]]
 +
      '''if''' !absorbing[input[i][0]]
 +
          R[position[input[i][0]]][position[input[i][1]]] = input[i][2]
 +
    '''else'''
 +
      Q[position[input[i][0]]][position[input[i][1]]] = input[i][2]
 +
</code>
 +
Найдем Матрицу <tex>E = I - Q</tex> и создадим единичную матрицу <tex>N</tex>.
 +
<code style = "display: inline-block;">
 +
'''for''' i = 0 '''to''' nonabs - 1
 +
    N[i][i] = 1
 +
    E[i][i] = 1
 +
     '''for''' j = 0 '''to''' nonabs - 1
 +
      E[i][j] -= Q[i][j]
 +
</code>
 +
Теперь приведем матрицу <tex>E</tex> к единичной методом Гаусса - Жордана, применяя те же преобразования к матрице <tex>N</tex>.
 +
<code style = "display: inline-block;">
 +
  '''for''' i = 0 '''to''' nonabs - 1
 +
     '''if''' E[i][i] <tex> \neq </tex> 1
 +
      mul = E[i][i]
 +
      '''for''' j = 0 '''to''' nonabs - 1
 +
          E[i][j] /= mul
 +
          N[i][j] /= mul
 +
    '''for''' row = 0 '''to''' nonabs - 1
 +
       '''if''' i <tex> \neq </tex> row
 +
          mul = E[row][i]
 
           '''for''' j = 0 '''to''' nonabs - 1
 
           '''for''' j = 0 '''to''' nonabs - 1
−
             prob += G[j][position[i]]
+
             E[row][j] -= mul * E[i][j]
−
          prob++
+
            N[row][j] -= mul * N[i][j]
−
          prob /= n
+
</code>
−
      probability[i] = prob
+
В результате <tex>N = E^{-1}</tex>  т.е. <tex>N</tex> - фундаментальная матрица Марковской цепи. Найдем матрицу <tex>G = NR</tex>.
−
   
+
<code style = "display: inline-block;">
−
     '''return''' probability
+
  '''for''' i = 0 '''to''' nonabs - 1
−
 
+
     '''for''' j = 0 '''to''' abs - 1
−
==См. также==
+
      G[i][j] = 0
−
*[[Марковская цепь]]
+
      '''for''' k = 0 '''to''' nonabs - 1
−
*[[Подсчет количества поглощающих состояний и построение матриц переходов марковской цепи]]
+
          G[i][j] += N[i][k] * R[k][j]
−
*[[Фундаментальная матрица]]
+
</code>
−
*[[Теорема о поглощении]]
+
Выведем ответ: в <tex>i</tex>-ой строке вероятность поглощения в <tex>i</tex>-ом состоянии. Естественно, для несущественного состояния это <tex>0</tex>, в ином случае <tex>p_i=(($$\sum_{k=1}^n G[k][j]$$)+1)/n</tex> где <tex>j</tex> - номер соответствующий <tex>i</tex>-ому состоянию в матрице <tex>G</tex> (т.е. под которым оно располагалось в матрице <tex>R</tex> т.е. значение <tex>position[i]</tex>). Прибавлять 1 нужно т.к. вероятность поглотиться в <tex>i</tex>-ом поглощающем состоянии, оказавшись изначально в нем же равна 1.
−
*[[Математическое ожидание времени поглощения]]
+
<code style = "display: inline-block;">
−
 
+
'''for''' i = 0 '''to''' n - 1
−
==Источники информации==
+
    prob = 0
−
* [http://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BF%D1%8C_%28%D0%BC%D0%B0%D1%82%D0%B5%D0%BC.%29 Википедия — Цепи Маркова]
+
    '''if''' absorbing[i]
−
* [http://www.studmed.ru/kemeni-dzh-snell-dzh-konechnye-cepi-markova_eb290d9f6f2.html Кемени Дж. и Снелл Дж., "Конечные цепи Маркова"]
+
      '''for''' j = 0 '''to''' nonabs - 1
 +
          prob += G[j][position[i]]
 +
      prob++
 +
      prob /= n
 +
    println(prob)
 +
</code>
  
 +
=Литература=
 +
* [http://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BF%D1%8C_%28%D0%BC%D0%B0%D1%82%D0%B5%D0%BC.%29 Википедия - Цепи Маркова]
 +
* Кемени Дж., Снелл Дж. "Конечные цепи Маркова".
  
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
  
 
[[Категория: Марковские цепи ]]
 
[[Категория: Марковские цепи ]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице:

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Расчёт_вероятности_поглощения_в_состоянии»