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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Псевдокод: исправлен псевдокод)
м (Псевдокод: исправлен псевдокод)
Строка 4: Строка 4:
  
 
===Псевдокод===
 
===Псевдокод===
*<tex>\mathtt{absorbing}: boolean[\mathtt{n}]</tex> — массив состояний. Если <tex>\mathtt{i}</tex> — посглощающее состояние <tex>\mathtt{absorbing}[\mathtt{i}] = true</tex> иначе <tex>\mathtt{absorbing}[\mathtt{i}] = false</tex>
+
*<tex>\mathtt{absorbing}[\mathtt{n}]</tex> — массив состояний. Если <tex>\mathtt{i}</tex> — посглощающее состояние <tex>\mathtt{absorbing}[\mathtt{i}] = true</tex> иначе <tex>\mathtt{absorbing}[\mathtt{i}] = false</tex>
 
*<tex>\mathtt{n}</tex> — количество состояний
 
*<tex>\mathtt{n}</tex> — количество состояний
 
*<tex>\mathtt{m}</tex> — количество переходов
 
*<tex>\mathtt{m}</tex> — количество переходов
Строка 22: Строка 22:
 
*<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие.
 
*<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие.
  
  '''procedure''' buildTransitionMatrix():
+
  '''procedure''' buildTransitionMatrix(absorbing: boolean[]):
     count_q = 0
+
     '''int''' count_q = 0
     count_r = 0
+
     '''int''' count_r = 0
 
     '''for''' i = 0 '''to''' n - 1
 
     '''for''' i = 0 '''to''' n - 1
 
       '''if''' absorbing[i]
 
       '''if''' absorbing[i]

Версия 00:57, 20 июня 2018

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

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

Псевдокод

  • [math]\mathtt{absorbing}[\mathtt{n}][/math] — массив состояний. Если [math]\mathtt{i}[/math] — посглощающее состояние [math]\mathtt{absorbing}[\mathtt{i}] = true[/math] иначе [math]\mathtt{absorbing}[\mathtt{i}] = false[/math]
  • [math]\mathtt{n}[/math] — количество состояний
  • [math]\mathtt{m}[/math] — количество переходов
boolean[] findAbsorbings(transition: int[m][2]):
   boolean absorbing[n] 
   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}[\mathtt{n}][/math] — массив нумерации состояний относительно существенной/несущественной матрицы.
  • [math]\mathtt{Q}[/math] — матрица перехода мужду несущественными состояниями.
  • [math]\mathtt{R}[/math] — матрица из несущественных состояний в поглощающие.
procedure buildTransitionMatrix(absorbing: boolean[]):
   int count_q = 0
   int 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]

См. также

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