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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Исправлены грамматические ошибки, добавлено см.также)
Строка 1: Строка 1:
 
==Подсчет количества поглощащих состояний==
 
==Подсчет количества поглощащих состояний==
Пусть <tex>\mathtt{transition}</tex> - массив переходов марковской цепи, где <tex>\mathtt{transition[i][2]}</tex> - вероятность перехода из состояния  <tex>\mathtt{transition[i][0]}</tex> в <tex>\mathtt{transition[i][1]}</tex>.
+
Пусть <tex>\mathtt{transition}</tex> массив переходов марковской цепи, где <tex>\mathtt{transition[i][2]}</tex> вероятность перехода из состояния  <tex>\mathtt{transition[i][0]}</tex> в <tex>\mathtt{transition[i][1]}</tex>.
Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> - поглощающее состояние, то <tex>\mathtt{transition[j][2] = 1}</tex>. По этому признаку помно определить все поглощающие состояния в цепи.
+
Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> поглощающее состояние, то <tex>\mathtt{transition[j][2] = 1}</tex>. По этому признаку можно определить все поглощающие состояния в цепи.
  
 
===Псевдокод===
 
===Псевдокод===
*<tex>\mathtt{absorbing}: boolean:[\mathtt{n}]</tex> - массив состояний. Если i - посглощающее состояние absorbing[i] = true
+
*<tex>\mathtt{absorbing}: boolean:[\mathtt{n}]</tex> массив состояний. Если i посглощающее состояние absorbing[i] = true
*<tex>\mathtt{n}</tex> - количество состояний
+
*<tex>\mathtt{n}</tex> количество состояний
*<tex>\mathtt{m}</tex> - количество переходов
+
*<tex>\mathtt{m}</tex> количество переходов
  
 
  '''function''' findAbsorbings(transition: '''int'''[m][2]):
 
  '''function''' findAbsorbings(transition: '''int'''[m][2]):
Строка 18: Строка 18:
 
Cоздадим сначала массив <tex>\mathtt{position}</tex> где <tex>\mathtt{i}</tex>-ый элемент указывает под каким номером будет находиться <tex>\mathtt{i}</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
 
Cоздадим сначала массив <tex>\mathtt{position}</tex> где <tex>\mathtt{i}</tex>-ый элемент указывает под каким номером будет находиться <tex>\mathtt{i}</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
 
===Псевдокод===
 
===Псевдокод===
*<tex>\mathtt{position[n]}</tex> - массив нумерации состояний относительно существенной/ несущественной матрицы.
+
*<tex>\mathtt{position[n]}</tex> массив нумерации состояний относительно существенной/несущественной матрицы.
*<tex>\mathtt{Q}</tex> - матрица перехода мужду несущественными состояниями.
+
*<tex>\mathtt{Q}</tex> матрица перехода мужду несущественными состояниями.
*<tex>\mathtt{R}</tex> - матрица из несущественных состояний в поглощающие.
+
*<tex>\mathtt{R}</tex> матрица из несущественных состояний в поглощающие.
  
 
  '''procedure''' buildTransitionMatrix()
 
  '''procedure''' buildTransitionMatrix()
Строка 39: Строка 39:
 
           Q[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]
 
           Q[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]
  
 +
== См. также ==
 +
*[[Марковская цепь]]
 +
*[[Расчет вероятности поглощения в состоянии]]
 +
*[[Математическое ожидание времени поглощения]]
  
 
== Источники информации ==
 
== Источники информации ==

Версия 17:02, 16 июня 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]

См. также

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