Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи
Версия от 02:10, 21 марта 2018; Igusev (обсуждение | вклад) (Igusev переименовал страницу Подсчет поглощающих состояний марковской цепи в [[Подсчет количества поглощающих состояний и построение ма…)
Подсчет количества поглощащих состояний
Пусть
- массив переходов марковской цепи, где - вероятность перехода из состояния в . Тогда, по определению поглощающего состояния, если - поглощающее состояние, то . По этому признаку помно определить все поглощающие состояния в цепи.Псевдокод
- - массив состояний. Если 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]