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

Описание алгоритма

Пусть [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

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

• Wikipedia: Absorbing Markov chain