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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Псевдокод: изменен тип transition)
м (Косметические изменения, введена структура jump, исправлен псевдокод)
Строка 1: Строка 1:
 
==Подсчет количества поглощащих состояний==
 
==Подсчет количества поглощащих состояний==
Пусть <tex>\mathtt{transition}</tex> — массив переходов марковской цепи, где <tex>\mathtt{transition}[\mathtt{i}][2]</tex> — вероятность перехода из состояния  <tex>\mathtt{transition}[\mathtt{i}][0]</tex> в <tex>\mathtt{transition}[\mathtt{i}][1]</tex>.
+
Для хранения переходов марковской цепи создадим структуру <tex> \mathtt{jump}</tex> jump.
Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> — поглощающее состояние, то <tex>\mathtt{transition}[\mathtt{j}][2] = 1</tex>. По этому признаку можно определить все поглощающие состояния в цепи.
+
Пусть <tex>\mathtt{transition}</tex> — <tex> \mathtt{jump}[\mathtt{m}], где <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.prob}</tex> — вероятность перехода из состояния  <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.from}</tex> в <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.to}</tex>.
 +
Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> — поглощающее состояние, то <tex>\mathtt{transition}[\mathtt{j}]\mathtt{.prob} = 1</tex>. По этому признаку можно определить все поглощающие состояния в цепи.
  
 
===Псевдокод===
 
===Псевдокод===
Строка 8: Строка 9:
 
*<tex>\mathtt{m}</tex> — количество переходов
 
*<tex>\mathtt{m}</tex> — количество переходов
  
  '''boolean[]''' findAbsorbings(transition: '''float'''[m][3]):
+
  '''boolean[]''' findAbsorbings(transition: '''jump'''[m]):
 
     '''boolean''' absorbing[n]  
 
     '''boolean''' absorbing[n]  
     '''for''' i = 0 '''to''' m - 1
+
 
       absorbing[transition[i][0]] = transition[i][0] == transition[i][1] '''and''' transition[i][2] == 1
+
     '''for''' jump i: transition
 +
       absorbing[i.from] = i.from == i.to '''and''' i.prob == 1
 +
 
 
     '''return''' absorbing
 
     '''return''' absorbing
  
Строка 21: Строка 24:
 
*<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие.
 
*<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие.
  
  '''procedure''' buildTransitionMatrix(absorbing: '''boolean'''[n]):
+
  '''float[][]''' buildTransitionMatrix(absorbing: '''boolean'''[n], transition: '''jump'''[m]):
 
     '''int''' count_q = 0
 
     '''int''' count_q = 0
 
     '''int''' 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]
Строка 31: Строка 35:
 
           position[i] = count_q
 
           position[i] = count_q
 
           count_q++
 
           count_q++
 +
 
     '''for''' i = 0 '''to''' m - 1
 
     '''for''' i = 0 '''to''' m - 1
       '''if''' absorbing[transition[i][1]]
+
       '''if''' absorbing[transition[i].to]
           '''if''' !absorbing[transition[i][0]]
+
           '''if''' !absorbing[transition[i].from]
             R[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]
+
             R[position[transition[i].from]][position[transition[i].to]] = transition[i].prob
 
       '''else'''
 
       '''else'''
           Q[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]
+
           Q[position[transition[i].from]][position[transition[i].to]] = transition[i].prob
 +
 
 +
    '''return Q'''
  
 
== См. также ==
 
== См. также ==

Версия 23:37, 23 июня 2018

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

Для хранения переходов марковской цепи создадим структуру [math] \mathtt{jump}[/math] jump. Пусть [math]\mathtt{transition}[/math][math] \mathtt{jump}[\mathtt{m}], где \lt tex\gt \mathtt{transition}[\mathtt{i}]\mathtt{.prob}[/math] — вероятность перехода из состояния [math]\mathtt{transition}[\mathtt{i}]\mathtt{.from}[/math] в [math]\mathtt{transition}[\mathtt{i}]\mathtt{.to}[/math]. Тогда, по определению поглощающего состояния, если [math]\mathtt{j}[/math] — поглощающее состояние, то [math]\mathtt{transition}[\mathtt{j}]\mathtt{.prob} = 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: jump[m]):
   boolean absorbing[n] 
   for jump i: transition 
      absorbing[i.from] = i.from == i.to and i.prob == 1
   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] — матрица из несущественных состояний в поглощающие.
float[][] buildTransitionMatrix(absorbing: boolean[n], transition: jump[m]):
   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].to]
         if !absorbing[transition[i].from]
            R[position[transition[i].from]][position[transition[i].to]] = transition[i].prob
      else
         Q[position[transition[i].from]][position[transition[i].to]] = transition[i].prob
   return Q

См. также

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