Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(sta)
м (Igusev переименовал страницу Подсчет поглощающих состояний марковской цепи в [[Подсчет количества поглощающих состояний и построение ма…)
(нет различий)

Версия 02:10, 21 марта 2018

Подсчет количества поглощащих состояний

Пусть [math]\mathtt{transition}[/math] - массив переходов марковской цепи, где [math]\mathtt{transition[i][2]}[/math] - вероятность перехода из состояния [math]\mathtt{transition[i][0}[/math] в [math]\mathtt{transition[i][1]}[/math]. Тогда, по определению поглощающего состояния, если [math]\mathtt{j}[/math] - поглощающее состояние, то [math]\mathtt{transition[j][2] = 1}[/math]. По этому признаку помно определить все поглощающие состояния в цепи.

Псевдокод

  • [math]\mathtt{absorbing}: boolean:[\mathtt{n}][/math] - массив состояний. Если i - посглощающее состояние absorbing[i] = true
  • [math]\mathtt{n}[/math] - количество состояний
  • [math]\mathtt{m}[/math] - количество переходов
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оздадим сначала массив [math]\mathtt{position}[/math] где [math]\mathtt{i}[/math]-ый элемент указывает под каким номером будет находиться [math]\mathtt{i}[/math]-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.

Псевдокод

  • [math]\mathtt{position[n]}[/math] - массив нумерации состояний относительно существенной/ несущественной матрицы.
  • [math]\mathtt{Q}[/math] - матрица перехода мужду несущественными состояниями.
  • [math]\mathtt{R}[/math] - матрица из несущественных состояний в поглощающие.
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]


Источники информации