54
правки
Изменения
м
Поправлены: источники информации, см.также, дефисы, где нужно, заменены на тире
Поглощающее(существенное) состояние цепи Маркова - — состояние с вероятностью перехода в самого себя <tex>p_{ii}=1</tex>.
Составим матрицу <tex>G</tex>, элементы которой <tex>g_{ij}</tex> равны вероятности того, что, выйдя из <tex>i</tex>, попадём в поглощающее состояние <tex>j</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{probability[i]}</tex> — вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии
*<tex>\mathtt{absorbing[i]}</tex> — является ли i-е состояние поглощающим
==См. также==
*[[Марковская цепь]]
*[[Подсчет количества поглощающих состояний и построение матриц переходов марковской цепи]]
*[[Фундаментальная матрица]]
*[[Теорема о поглощении]]
==Источники информации==
* [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 Кемени Дж., и Снелл Дж. , "Конечные цепи Маркова".]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Марковские цепи ]]
