Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи
Версия от 17:02, 16 июня 2018; Arimon (обсуждение | вклад) (Исправлены грамматические ошибки, добавлено см.также)
Содержание
Подсчет количества поглощащих состояний
Пусть
— массив переходов марковской цепи, где — вероятность перехода из состояния в . Тогда, по определению поглощающего состояния, если — поглощающее состояние, то . По этому признаку можно определить все поглощающие состояния в цепи.Псевдокод
- — массив состояний. Если i — посглощающее состояние absorbing[i] = true
- — количество состояний
- — количество переходов
function findAbsorbings(transition: int[m][2]): boolean absorbing[m] for i = 0 to m - 1 if transition[i][0] == transition[i][1] and transition[i][2] == 1 absorbing[transition[i][0]] = true return absorbing
Построение матриц переходов
Cоздадим сначала массив
где -ый элемент указывает под каким номером будет находиться -ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.Псевдокод
- — массив нумерации состояний относительно существенной/несущественной матрицы.
- — матрица перехода мужду несущественными состояниями.
- — матрица из несущественных состояний в поглощающие.
procedure buildTransitionMatrix() count_q = 0 count_r = 0 for i = 0 to n - 1 if absorbing[i] position[i] = count_r count_r++ else position[i] = count_q count_q++ for i = 0 to m - 1 if absorbing[transition[i][1]] if !absorbing[transition[i][0]] R[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2] else Q[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]
См. также
- Марковская цепь
- Расчет вероятности поглощения в состоянии
- Математическое ожидание времени поглощения