Изменения
→Псевдокод
Матрица 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> - количество переходов. Состояния и переходы пронумерованы от <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>.Создадим массив <tex>absorbing</tex> типа Booleanboolean, где <tex>i</tex>-ое <tex>true</tex> обозначает что <tex>i</tex>-ое состояние является поглощающими наоборот. Если Обнаружим поглощающие состояния по такому признаку: если состояние поглощающее то с вероятностью 1 оно переходит само в себя. Найдем такие состояния. Также посчитаем количество поглощающих состояний <tex>abs</tex>_<tex>num</tex>.
<code style = "display: inline-block;">
for i=0 to n-1
if (input[i][0] == input[i][1] && and input[i][2] == 1)
absorbing[input[i][0]] = true;
abs_num++;
</code>
Найдем число несущественных состояний <tex>nonabs=n-abs</tex>_<tex>num</tex>. Теперь нужно заполнить массивы <tex>Q </tex> (переходов между несущественными состояниями) и <tex>R </tex> (переходов из несущественных состояний в поглощающие). Для этого создадим сначала массив <tex>position</tex> где <tex>i</tex>-ый элемент указывает под каким номером будет находиться <tex>i</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
<code style = "display: inline-block;">
count_q = 0;
Q[position[input[i][0]]][position[input[i][1]]] = input[i][2];
</code>
Найдем Матрицу <tex>E = I - Q </tex> и создадим единичную матрицу <tex>N</tex>.
<code style = "display: inline-block;">
for i=0 to nonabs
E[i][j]-=Q[i][j];
</code>
Теперь приведем матрицу <tex>E </tex> к единичной методом Гаусса—ЖорданаГаусса - Жордана, применяя те же преобразования к матрице N. В результате <tex>N=E^{-1}</tex> т.е. N - фундаментальная матрица Марковской цепи.
<code style = "display: inline-block;">
for i = 0 to nonabs
N[row][j] -= mul * N[i][j];
</code>
В результате <tex>N=E^{-1}</tex> т.е. <tex>N</tex> - фундаментальная матрица Марковской цепи. Найдем матрицу <tex>G = N * R</tex>.
<code style = "display: inline-block;">
for i = 0 to nonabs
G[i][j] += N[i][k] * R[k][j];
</code>
Выведем ответ: В <tex>i</tex>-ой строке вероятность поглощения в <tex>i</tex>-ом состоянии. Естественно для несущественного состояния это 0, в ином случае <tex>p=(($$\sum_{k=1}^n G[k][j]$$)+1)/n</tex> где j - номер соответствующий состоянию в <tex>G</tex>. Прибавлять 1 нужно т.к. вероятность поглотиться в <tex>i</tex> -ом поглощающем состоянии, оказавшись изначально в нем же равна 1.
<code style = "display: inline-block;">
for i = 0 to n
