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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Псевдокод)
Строка 9: Строка 9:
 
Матрица 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> }}
 
Матрица 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>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>absorbing[]</tex> типа Boolean, где <tex>i</tex>-ое <tex>true</tex> обозначает что <tex>i</tex>-ое состояние является поглощающим. Если состояние поглощающее то с вероятностью 1 оно переходит само в себя. Найдем такие состояния. Также посчитаем количество поглощающих состояний <tex>abs</tex>_<tex>num</tex>.
 +
 
=Литература=
 
=Литература=
 
* [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, Википедия - Цепи Маркова]

Версия 16:20, 5 января 2013

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

Теорема:
[math] G = N \cdot R [/math]
Доказательство:
[math]\triangleright[/math]

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

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

Псевдокод

[math]n[/math] - количество состояний Марковской цепи, [math]m[/math] - количество переходов. Состояния пронумерованы от 0 до [math]n - 1[/math]. Пусть входные данные хранятся в массиве [math]input[/math] где [math]i[/math]-ая строка характеризует [math]i[/math]-ый переход таким образом: [math]input[i][2][/math] - вероятность перехода из состояния [math]input[i][0][/math] в состояние [math]input[i][1][/math]. Создадим массив [math]absorbing[][/math] типа Boolean, где [math]i[/math]-ое [math]true[/math] обозначает что [math]i[/math]-ое состояние является поглощающим. Если состояние поглощающее то с вероятностью 1 оно переходит само в себя. Найдем такие состояния. Также посчитаем количество поглощающих состояний [math]abs[/math]_[math]num[/math].

Литература