105
правок
Изменения
м
Дмитрий Мурзин переименовал страницу Расчет вероятности поглощения в состоянии в Расчёт вероятности поглощения в состоянии: Ёфикац…
[[Марковская цепь#Поглощающая цепь| Поглощающее(существенное) состояние цепи Маркова ]] — состояние с вероятностью перехода в самого себя <tex>p_{ii}=1</tex>.
Составим матрицу <tex>\mathtt{G}</tex>, элементы которой <tex>g_{ij}</tex> равны вероятности того, что, выйдя из <tex>i</tex>, попадём в поглощающее состояние <tex>j</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>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>\mathtt{probability}[\mathtt{i}]</tex> — вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии
*<tex>\mathtt{absorbing}[\mathtt{i}]</tex> — является ли <tex>\mathtt{i}</tex>-е состояние поглощающим
'''float[]''' getAbsorbingProbability(absorbing: '''boolean'''[n], G: '''float'''[n][n], position: '''int'''[n]):
'''float''' probability[n]
'''for''' i = 0 '''to''' n - 1
'''float''' prob = 0
prob /= n
probability[i] = prob
'''return''' probability
