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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Псевдокод)
(не показано 38 промежуточных версий 11 участников)
Строка 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> G = N \cdot R </tex>
+
<tex> \mathtt{G} = N \cdot R </tex>, где <tex>N</tex> — фундаментальная матрица, и <tex>R</tex> — матрица перехода из несущественных состояний в существенные.
 
|proof=
 
|proof=
Пусть этот переход будет осуществлён за 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>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> являются несущественными.
Тогда рассмотрим сумму <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>\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> — из несущественного в существенное.  
Матрица 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{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> }}
=Псевдокод=
+
==Псевдокод==
<tex>n</tex> - количество состояний Марковской цепи, <tex>m</tex> - количество переходов. Состояния и переходы пронумерованы от 0 до <tex>n - 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{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>absorbing</tex> типа Boolean, где <tex>i</tex>-ое <tex>true</tex> обозначает что <tex>i</tex>-ое состояние является поглощающим. Если состояние поглощающее то с вероятностью 1 оно переходит само в себя. Найдем такие состояния. Также посчитаем количество поглощающих состояний <tex>abs</tex>_<tex>num</tex>.
+
*<tex>\mathtt{probability}[\mathtt{i}]</tex> — вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии
<code style = "display: inline-block;">
+
*<tex>\mathtt{absorbing}[\mathtt{i}]</tex> — является ли <tex>\mathtt{i}</tex>-е состояние поглощающим
  for i=0 to n-1
+
 
    if (input[i][0] == input[i][1] && input[i][2] == 1)
+
'''float[]''' getAbsorbingProbability(absorbing: '''boolean'''[n], G: '''float'''[n][n], position: '''int'''[n]):
      absorbing[input[i][0]] = true;
+
     '''float''' probability[n]
      abs_num++;
+
</code>
+
    '''for''' i = 0 '''to''' n - 1
Найдем число несущественных состояний <tex>nonabs=n-abs</tex>_<tex>num</tex>. Теперь нужно заполнить массивы Q (переходов между несущественными состояниями) и R (переходов из несущественных состояний в поглощающие). Для этого создадим сначала массив <tex>position</tex> где <tex>i</tex>-ый элемент указывает под каким номером будет находиться <tex>i</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
+
      '''float''' prob = 0
<code style = "display: inline-block;">
+
      '''if''' absorbing[i]
  count_q = 0;
+
          '''for''' j = 0 '''to''' nonabs - 1
  count_r = 0;
+
            prob += G[j][position[i]]
  for i = 0 to n - 1
+
          prob++
    if abs[i]
+
          prob /= n
      position[i] = count_r;
+
      probability[i] = prob
      count_r++;
+
    else
+
    '''return''' probability
      position[i] = count_q;
+
 
      count_q++;
+
==См. также==
  for i = 0 to m - 1
+
*[[Марковская цепь]]
    if absorbing[input[i][1]]
+
*[[Подсчет количества поглощающих состояний и построение матриц переходов марковской цепи]]
      if absabsorbing[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>
+
==Источники информации==
Найдем Матрицу E = I - Q и создадим единичную матрицу N.
+
* [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 Википедия — Цепи Маркова]
<code style = "display: inline-block;">
+
* [http://www.studmed.ru/kemeni-dzh-snell-dzh-konechnye-cepi-markova_eb290d9f6f2.html Кемени Дж. и Снелл Дж., "Конечные цепи Маркова"]
  for i=0 to nonabs
 
    N[i][i]=1;'
 
    E[i][i]=1;
 
    for j=0 to nonabs
 
      E[i][j]-=Q[i][j]
 
</code>
 
Теперь приведем матрицу E к единичной методом Гаусса—Жордана, применяя те же преобразования к матрице N. В результате <tex>N=E^{-1}</tex>  т.е. N - фундаментальная матрица Марковской цепи.
 
<code style = "display: inline-block;">
 
  for i = 0 to nonabs
 
    if E[i][i] != 1
 
        mul = E[i][i];
 
        for j = 0 to nonabs
 
          E[i][j] /= mul;
 
          N[i][j] /= mul;
 
      for row = 0 to nonabs
 
          if i != row
 
            mul = E[row][i];
 
            for j = 0 to nonabs
 
                E[row][j] -= mul * E[i][j];
 
                N[row][j] -= mul * N[i][j];
 
</code>
 
Найдем матрицу G = N * R
 
<code style = "display: inline-block;">
 
  for i = 0 to nonabs
 
      for j = 0 to absorbing
 
          G[i][j] = 0;
 
          for k = 0 to nonabs
 
              G[i][j] += N[i][k] * R[k][j];
 
</code>
 
Выведем ответ: В <tex>i</tex>-ой строке вероятность поглощения в <tex>i</tex>-ом состоянии. Естественно для несущественного состояния это 0, в ином случае <tex>p=(($$\sum_{k=1}^n G[k][j]$$)+1)/n</tex> где j - номер соответствующий состоянию в G. Прибавлять 1 нужно т.к. вероятность поглотиться в <tex>i</tex> поглощающем состоянии, оказавшись изначально в нем же равна 1.
 
<code style = "display: inline-block;">
 
  for i = 0 to n
 
      prob = 0;
 
      if absorbing[i]
 
        for j = 0 to nonabs
 
            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, Википедия - Цепи Маркова]
 
* Кемени Дж., Снелл Дж. "Конечные цепи Маркова".
 
  
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
  
 
[[Категория: Марковские цепи ]]
 
[[Категория: Марковские цепи ]]

Версия 23:48, 31 января 2019

Поглощающее состояние — состояние с вероятностью перехода в самого себя [math]p_{ii}=1[/math].

Составим матрицу [math]\mathtt{G}[/math], элементы которой [math]g_{ij}[/math] равны вероятности того, что, выйдя из [math]i[/math], попадём в поглощающее состояние [math]j[/math].

Теорема:
[math] \mathtt{G} = N \cdot R [/math], где [math]N[/math] — фундаментальная матрица, и [math]R[/math] — матрица перехода из несущественных состояний в существенные.
Доказательство:
[math]\triangleright[/math]

Пусть этот переход будет осуществлён за [math]r[/math] шагов: [math]i[/math][math]i_{1}[/math][math]i_{2}[/math][math]\ldots[/math][math]i_{r-1}[/math] → j, где все [math]i, i_{1}, \ldots i_{r-1}[/math] являются несущественными. Тогда рассмотрим сумму [math]\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[/math], где [math]Q[/math] — матрица переходов между несущественными состояниями, [math]R[/math] — из несущественного в существенное.

Матрица [math]\mathtt{G}[/math] определяется их суммированием по всем длинам пути из i в j: [math]\mathtt{G} = \sum\limits_{r = 1}^{\infty}{Q^{r-1} \cdot R} = (I + Q + Q^{2} + Q^{3} + \ldots) \cdot R = NR[/math], т.к. [math](I + Q + Q^2 + \ldots) \cdot (I - Q) = I - Q + Q - Q^{2} + \ldots = I[/math], а фундаментальная матрица марковской цепи [math]N = (I - Q)^{-1}[/math]
[math]\triangleleft[/math]

Псевдокод

Выведем ответ: в [math]\mathtt{i}[/math]-ой строке вероятность поглощения в [math]\mathtt{i}[/math]-ом состоянии. Естественно, для несущественного состояния это [math]0[/math], в ином случае [math]\mathtt{p_i}=\left(\sum\limits_{k=1}^{n} \mathtt{G}[k][j]+1\right)/n[/math] где [math]\mathtt{j}[/math] — номер соответствующий [math]\mathtt{i}[/math]-ому состоянию в матрице [math]\mathtt{G}[/math] (т.е. под которым оно располагалось в матрице [math] \mathtt{R} [/math] т.е. значение [math]\mathtt{position}[\mathtt{i}][/math]). Прибавлять [math]1[/math] нужно т.к. вероятность поглотиться в [math]\mathtt{i}[/math]-ом поглощающем состоянии, оказавшись изначально в нем же равна [math]1[/math].

  • [math]\mathtt{probability}[\mathtt{i}][/math] — вероятность поглощения в [math]\mathtt{i}[/math]-ом состоянии
  • [math]\mathtt{absorbing}[\mathtt{i}][/math] — является ли [math]\mathtt{i}[/math]-е состояние поглощающим
float[] getAbsorbingProbability(absorbing: boolean[n], G: float[n][n], position: int[n]):
   float probability[n]

   for i = 0 to n - 1
      float prob = 0
      if absorbing[i]
         for j = 0 to nonabs - 1
            prob += G[j][position[i]]
         prob++
         prob /= n
      probability[i] = prob

   return probability

См. также

Источники информации