Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи
(перенаправлено с «Подсчет поглощающих состояний марковской цепи»)
Содержание
Подсчет количества поглощащих состояний
Для хранения переходов марковской цепи создадим структуру .
Введем , где — вероятность перехода из состояния в .
Тогда, по определению поглощающего состояния, если — поглощающее состояние, то . По этому признаку можно определить все поглощающие состояния в цепи.
Псевдокод
- — массив состояний. Если — посглощающее состояние иначе
- — количество состояний
- — количество переходов
boolean[] findAbsorbings(transition: jump[m]):
boolean absorbing[n]
for jump i in transition
absorbing[i.from] = i.from == i.to and i.prob == 1
return absorbing
Построение матриц переходов
Cоздадим сначала массив где -ый элемент указывает под каким номером будет находиться -ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
Псевдокод
- — массив нумерации состояний относительно существенной/несущественной матрицы.
- — матрица перехода мужду несущественными состояниями.
- — матрица из несущественных состояний в поглощающие.
float[][] buildTransitionMatrix(absorbing: boolean[n], transition: jump[m]):
int count_q = 0
int count_r = 0
float Q[n][n]
float R[n][n]
int position[n]
for i = 0 to n - 1
if absorbing[i]
position[i] = count_r
count_r++
else
position[i] = count_q
count_q++
for jump i in transition
if absorbing[i.to]
if !absorbing[i.from]
R[position[i.from]][position[i.to]] = i.prob
else
Q[position[i.from]][position[i.to]] = i.prob
return Q
См. также
- Марковская цепь
- Расчет вероятности поглощения в состоянии
- Математическое ожидание времени поглощения
