78
правок
Изменения
Нет описания правки
Поглощающее(существенное) состояние цепи Маркова - состояние с вероятностью перехода в самого себя <tex>p_{ii}=1</tex>.
Составим матрицу <tex>G</tex>, элементы которой <tex>g_{ij}</tex> равны вероятности того, что, выйдя из <tex>i</tex>, попадём в поглощающее состояние <tex>j</tex>.
{{Теорема
|statement=
Пусть этот переход будет осуществлён за <tex>r</tex> шагов: <tex>i</tex> → <tex>i_{1}</tex> → <tex>i_{2}</tex> → ... → <tex>i_{r-1}</tex> → j, где все <tex>i, i_{1}, ... i_{r-1}</tex> являются несущественными.
Тогда рассмотрим сумму <tex>\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</tex>, где <tex>Q</tex> - матрица переходов между несущественными состояниями, <tex>R</tex> - из несущественного в существенное.
Матрица <tex>G </tex> определяется их суммированием по всем длинам пути из 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> - количество переходов. Состояния пронумерованы от <tex>0</tex> до <tex>n - 1</tex>, переходы от <tex>0</tex> до <tex>m - 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>.
