Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи — различия между версиями
Arimon (обсуждение | вклад) м (→Подсчет количества поглощащих состояний: упразднен if) |
м (rollbackEdits.php mass rollback) |
||
(не показано 16 промежуточных версий 3 участников) | |||
Строка 1: | Строка 1: | ||
==Подсчет количества поглощащих состояний== | ==Подсчет количества поглощащих состояний== | ||
− | + | Для хранения переходов марковской цепи создадим структуру <tex> \mathtt{jump}</tex>. | |
− | Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> — поглощающее состояние, то <tex>\mathtt{transition}[\mathtt{j}] | + | |
+ | Введем <tex>\mathtt{transition}:</tex> <tex> \mathtt{jump}[\mathtt{m}] </tex>, где <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: | Строка 11: | ||
*<tex>\mathtt{m}</tex> — количество переходов | *<tex>\mathtt{m}</tex> — количество переходов | ||
− | '''boolean[]''' findAbsorbings(transition: ''' | + | '''boolean[]''' findAbsorbings(transition: '''jump'''[m]): |
'''boolean''' absorbing[n] | '''boolean''' absorbing[n] | ||
− | '''for''' i | + | |
− | absorbing | + | '''for''' '''jump''' i '''in''' transition |
+ | absorbing[i.from] = i.from == i.to '''and''' i.prob == 1 | ||
+ | |||
'''return''' absorbing | '''return''' absorbing | ||
Строка 21: | Строка 26: | ||
*<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие. | *<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие. | ||
− | ''' | + | '''float[][]''' buildTransitionMatrix(absorbing: '''boolean'''[n], transition: '''jump'''[m]): |
'''int''' count_q = 0 | '''int''' count_q = 0 | ||
'''int''' count_r = 0 | '''int''' count_r = 0 | ||
+ | '''float''' Q[n][n] | ||
+ | '''float''' R[n][n] | ||
+ | '''int''' position[n] | ||
+ | |||
'''for''' i = 0 '''to''' n - 1 | '''for''' i = 0 '''to''' n - 1 | ||
'''if''' absorbing[i] | '''if''' absorbing[i] | ||
Строка 31: | Строка 40: | ||
position[i] = count_q | position[i] = count_q | ||
count_q++ | count_q++ | ||
− | '''for''' i | + | |
− | '''if''' absorbing | + | '''for''' '''jump''' i '''in''' transition |
− | '''if''' !absorbing | + | '''if''' absorbing[i.to] |
− | R[position | + | '''if''' !absorbing[i.from] |
+ | R[position[i.from]][position[i.to]] = i.prob | ||
'''else''' | '''else''' | ||
− | Q[position | + | Q[position[i.from]][position[i.to]] = i.prob |
+ | |||
+ | '''return''' Q | ||
== См. также == | == См. также == |
Текущая версия на 19:13, 4 сентября 2022
Содержание
Подсчет количества поглощащих состояний
Для хранения переходов марковской цепи создадим структуру
.Введем
, где — вероятность перехода из состояния в .Тогда, по определению поглощающего состояния, если
— поглощающее состояние, то . По этому признаку можно определить все поглощающие состояния в цепи.Псевдокод
- — массив состояний. Если — посглощающее состояние иначе
- — количество состояний
- — количество переходов
boolean[] findAbsorbings(transition: jump[m]): boolean absorbing[n] for jump i in transition absorbing[i.from] = i.from == i.to and i.prob == 1 return absorbing
Построение матриц переходов
Cоздадим сначала массив
где -ый элемент указывает под каким номером будет находиться -ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.Псевдокод
- — массив нумерации состояний относительно существенной/несущественной матрицы.
- — матрица перехода мужду несущественными состояниями.
- — матрица из несущественных состояний в поглощающие.
float[][] buildTransitionMatrix(absorbing: boolean[n], transition: jump[m]): int count_q = 0 int count_r = 0 float Q[n][n] float R[n][n] int position[n] for i = 0 to n - 1 if absorbing[i] position[i] = count_r count_r++ else position[i] = count_q count_q++ for jump i in transition if absorbing[i.to] if !absorbing[i.from] R[position[i.from]][position[i.to]] = i.prob else Q[position[i.from]][position[i.to]] = i.prob return Q
См. также
- Марковская цепь
- Расчет вероятности поглощения в состоянии
- Математическое ожидание времени поглощения