105
правок
Изменения
м
Дмитрий Мурзин переименовал страницу Расчет вероятности поглощения в состоянии в Расчёт вероятности поглощения в состоянии: Ёфикац…
[[Марковская цепь#Поглощающая цепь| Поглощающее(существенное) состояние цепи Маркова ]] — состояние с вероятностью перехода в самого себя <tex>p_{ii}=1</tex>. Составим матрицу <tex>\mathtt{G}</tex>, элементы которой <tex>g_{ij}</tex> равны вероятности того, что, выйдя из <tex>i</tex>, попадём в поглощающее состояние <tex>j</tex>.
{{Теорема
|statement=
<tex> \mathtt{G } = N \cdot R </tex>, где <tex>N</tex> — фундаментальная матрица, и <tex>R</tex> — матрица перехода из несущественных состояний в существенные.
|proof=
Пусть этот переход будет осуществлён за <tex>r</tex> шагов: <tex>i</tex> → <tex>i_{1}</tex> → <tex>i_{2}</tex> → <tex>\ldots</tex> → <tex>i_{r-1}</tex> → j, где все <tex>i, i_{1}, \ldots 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>\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>\mathtt{i}</tex>-ой строке вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии. Естественно, для несущественного состояния это <tex>\mathtt{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>\mathtt{1}</tex> нужно т.к. вероятность поглотиться в <tex>\mathtt{i}</tex>-ом поглощающем состоянии, оказавшись изначально в нем же равна <tex>\mathtt{1}</tex>.*<tex>\mathtt{probability}[\mathtt{i}]}</tex> — вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии*<tex>\mathtt{absorbing}[\mathtt{i}]}</tex> — является ли <tex>\mathtt{i}</tex>-е состояние поглощающим
'''functionfloat[]''' 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 /= n
probability[i] = prob
'''return ''' probability
==См. также==
*[[Фундаментальная матрица]]
*[[Теорема о поглощении]]
*[[Математическое ожидание времени поглощения]]
==Источники информации==
* [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 Википедия — Цепи Маркова]
