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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (Поправлены: источники информации, см.также, дефисы, где нужно, заменены на тире)
Строка 1: Строка 1:
Поглощающее(существенное) состояние цепи Маркова - состояние с вероятностью перехода в самого себя <tex>p_{ii}=1</tex>.
+
Поглощающее(существенное) состояние цепи Маркова состояние с вероятностью перехода в самого себя <tex>p_{ii}=1</tex>.
 
Составим матрицу <tex>G</tex>, элементы которой <tex>g_{ij}</tex> равны вероятности того, что, выйдя из <tex>i</tex>, попадём в поглощающее состояние <tex>j</tex>.
 
Составим матрицу <tex>G</tex>, элементы которой <tex>g_{ij}</tex> равны вероятности того, что, выйдя из <tex>i</tex>, попадём в поглощающее состояние <tex>j</tex>.
 
{{Теорема
 
{{Теорема
Строка 9: Строка 9:
 
Матрица <tex>G</tex> определяется их суммированием по всем длинам пути из i в j: <tex>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>G</tex> определяется их суммированием по всем длинам пути из i в j: <tex>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>\mathtt{i}</tex>-ой строке вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии. Естественно, для несущественного состояния это <tex>\mathtt{0}</tex>, в ином случае <tex>\mathtt{p_i=((\sum\limits_{k=1}^{n} G[k][j]+1)/n}</tex> где <tex>\mathtt{j}</tex> - номер соответствующий <tex>\mathtt{i}</tex>-ому состоянию в матрице <tex>\mathtt{G}</tex> (т.е. под которым оно располагалось в матрице <tex> \mathtt{R} </tex> т.е. значение <tex>\mathtt{position[i]}</tex>). Прибавлять <tex>\mathtt{1}</tex> нужно т.к. вероятность поглотиться в <tex>\mathtt{i}</tex>-ом поглощающем состоянии, оказавшись изначально в нем же равна <tex>\mathtt{1}</tex>.
+
Выведем ответ: в <tex>\mathtt{i}</tex>-ой строке вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии. Естественно, для несущественного состояния это <tex>\mathtt{0}</tex>, в ином случае <tex>\mathtt{p_i=((\sum\limits_{k=1}^{n} G[k][j]+1)/n}</tex> где <tex>\mathtt{j}</tex> номер соответствующий <tex>\mathtt{i}</tex>-ому состоянию в матрице <tex>\mathtt{G}</tex> (т.е. под которым оно располагалось в матрице <tex> \mathtt{R} </tex> т.е. значение <tex>\mathtt{position[i]}</tex>). Прибавлять <tex>\mathtt{1}</tex> нужно т.к. вероятность поглотиться в <tex>\mathtt{i}</tex>-ом поглощающем состоянии, оказавшись изначально в нем же равна <tex>\mathtt{1}</tex>.
 
*<tex>\mathtt{probability[i]}</tex> — вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии
 
*<tex>\mathtt{probability[i]}</tex> — вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии
 
*<tex>\mathtt{absorbing[i]}</tex> — является ли i-е состояние поглощающим
 
*<tex>\mathtt{absorbing[i]}</tex> — является ли i-е состояние поглощающим
Строка 26: Строка 26:
  
 
==См. также==
 
==См. также==
 +
*[[Марковская цепь]]
 
*[[Подсчет количества поглощающих состояний и построение матриц переходов марковской цепи]]
 
*[[Подсчет количества поглощающих состояний и построение матриц переходов марковской цепи]]
 +
*[[Фундаментальная матрица]]
 +
*[[Теорема о поглощении]]
 
==Источники информации==
 
==Источники информации==
* [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://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://www.studmed.ru/kemeni-dzh-snell-dzh-konechnye-cepi-markova_eb290d9f6f2.html Кемени Дж. и Снелл Дж., "Конечные цепи Маркова"]
 +
 
  
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
  
 
[[Категория: Марковские цепи ]]
 
[[Категория: Марковские цепи ]]

Версия 16:28, 16 июня 2018

Поглощающее(существенное) состояние цепи Маркова — состояние с вероятностью перехода в самого себя [math]p_{ii}=1[/math]. Составим матрицу [math]G[/math], элементы которой [math]g_{ij}[/math] равны вероятности того, что, выйдя из [math]i[/math], попадём в поглощающее состояние [math]j[/math].

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

  • [math]\mathtt{probability[i]}[/math] — вероятность поглощения в [math]\mathtt{i}[/math]-ом состоянии
  • [math]\mathtt{absorbing[i]}[/math] — является ли i-е состояние поглощающим
function getAbsorbingProbability(absorbing: boolean[n], G: float[n][n])
   float probability[n]
   for i = 0 to n - 1
      prob = 0
      if absorbing[i]
         for j = 0 to nonabs - 1
            prob += G[j][position[i]]
         prob++
         prob /= n
      probability[i] = prob
   return probability

См. также

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