Изменения

Пусть <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> типа boolean, где <tex>i</tex>-ое true обозначает что <tex>i</tex>-ое состояние является поглощающим и наоборот. Обнаружим поглощающие состояния по такому признаку: если состояние поглощающее то с вероятностью 1 оно переходит само в себя. Также посчитаем количество поглощающих состояний <tex>abs</tex>_<tex>num</tex>.

'''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 abs++;

Найдем число несущественных состояний <tex>nonabs=n-abs</tex>_<tex>num</tex>. Теперь нужно заполнить массивы матрицы <tex>Q</tex> (переходов между несущественными состояниями) и <tex>R</tex> (переходов из несущественных состояний в поглощающие). Для этого создадим сначала массив <tex>position</tex> где <tex>i</tex>-ый элемент указывает под каким номером будет находиться <tex>i</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.

count_q = 0; count_r = 0; '''for ''' i = 0 '''to ''' n - 1 '''if ''' abs[i] position[i] = count_r; count_r++; '''else ''' position[i] = count_q; count_q++; '''for ''' i = 0 '''to ''' m - 1

'''if ''' absabsorbing[input[i][0]] R[position[input[i][0]]][position[input[i][1]]] = input[i][2]; '''else''' Q[position[input[i][0]]][position[input[i][1]]] = input[i][2];

'''for ''' i=0 '''to ''' nonabs- 1 N[i][i]=1;' E[i][i]=1; '''for ''' j=0 '''to ''' nonabs- 1 E[i][j]-=Q[i][j];

'''for ''' i = 0 '''to ''' nonabs- 1 '''if ''' E[i][i] != 1 mul = E[i][i]; '''for ''' j = 0 '''to ''' nonabs- 1

'''for ''' row = 0 '''to ''' nonabs- 1 '''if ''' i != row mul = E[row][i]; '''for ''' j = 0 '''to ''' nonabs- 1 E[row][j] -= mul * E[i][j]; N[row][j] -= mul * N[i][j];

В результате <tex>N=E^{-1}</tex> т.е. <tex>N</tex> - фундаментальная матрица Марковской цепи. Найдем матрицу <tex>G = N * R</tex>.

'''for ''' i = 0 '''to ''' nonabs- 1 '''for ''' j = 0 '''to ''' absorbing- 1 G[i][j] = 0; '''for ''' k = 0 '''to ''' nonabs- 1 G[i][j] += N[i][k] * R[k][j];

Выведем ответ: В в <tex>i</tex>-ой строке вероятность поглощения в <tex>i</tex>-ом состоянии. Естественно для несущественного состояния это 0, в ином случае <tex>p=(($$\sum_{k=1}^n G[k][j]$$)+1)/n</tex> где <tex>j </tex> - номер соответствующий состоянию в <tex>G</tex>. Прибавлять 1 нужно т.к. вероятность поглотиться в <tex>i</tex>-ом поглощающем состоянии, оказавшись изначально в нем же равна 1.

'''for ''' i = 0 '''to ''' n- 1 prob = 0; '''if ''' absorbing[i] '''for ''' j = 0 '''to ''' nonabs- 1 prob += G[j][position[i]]; prob++; prob /= n; println(prob);