Расчёт вероятности поглощения в состоянии
Поглощающее состояние — состояние с вероятностью перехода в самого себя .
Составим матрицу , элементы которой равны вероятности того, что, выйдя из , попадём в поглощающее состояние .
| Теорема: |
, где — фундаментальная матрица, и — матрица перехода из несущественных состояний в существенные. |
| Доказательство: |
|
Пусть этот переход будет осуществлён за шагов: → → → → → j, где все являются несущественными. Тогда рассмотрим сумму , где — матрица переходов между несущественными состояниями, — из несущественного в существенное. Матрица определяется их суммированием по всем длинам пути из i в j: , т.к. , а фундаментальная матрица марковской цепи |
Псевдокод
Выведем ответ: в -ой строке вероятность поглощения в -ом состоянии. Естественно, для несущественного состояния это , в ином случае где — номер соответствующий -ому состоянию в матрице (т.е. под которым оно располагалось в матрице т.е. значение ). Прибавлять нужно т.к. вероятность поглотиться в -ом поглощающем состоянии, оказавшись изначально в нем же равна .
- — вероятность поглощения в -ом состоянии
- — является ли -е состояние поглощающим
float[] getAbsorbingProbability(absorbing: boolean[n], G: float[n][n]):
float probability[n]
for i = 0 to n - 1
float prob = 0
if absorbing[i]
for j = 0 to nonabs - 1
prob += G[j][position[i]]
prob++
prob /= n
probability[i] = prob
return probability
