Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи — различия между версиями
Igusev (обсуждение | вклад) (Создание страницы) |
м (rollbackEdits.php mass rollback) |
||
(не показано 28 промежуточных версий 4 участников) | |||
Строка 1: | Строка 1: | ||
− | == | + | ==Подсчет количества поглощащих состояний== |
− | + | Для хранения переходов марковской цепи создадим структуру <tex> \mathtt{jump}</tex>. | |
− | |||
− | + | Введем <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>. По этому признаку можно определить все поглощающие состояния в цепи. |
− | '''boolean''' absorbing[ | + | |
− | '''for''' | + | ===Псевдокод=== |
− | + | *<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{m}</tex> — количество переходов | ||
+ | |||
+ | '''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 | '''return''' absorbing | ||
+ | |||
+ | ==Построение матриц переходов== | ||
+ | Cоздадим сначала массив <tex>\mathtt{position}</tex> где <tex>\mathtt{i}</tex>-ый элемент указывает под каким номером будет находиться <tex>\mathtt{i}</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы. | ||
+ | ===Псевдокод=== | ||
+ | *<tex>\mathtt{position}[\mathtt{n}]</tex> — массив нумерации состояний относительно существенной/несущественной матрицы. | ||
+ | *<tex>\mathtt{Q}</tex> — матрица перехода мужду несущественными состояниями. | ||
+ | *<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие. | ||
+ | |||
+ | '''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 | ||
+ | |||
+ | == См. также == | ||
+ | *[[Марковская цепь]] | ||
+ | *[[Расчет вероятности поглощения в состоянии]] | ||
+ | *[[Математическое ожидание времени поглощения]] | ||
== Источники информации == | == Источники информации == | ||
− | *[https://en.wikipedia.org/wiki/Absorbing_Markov_chain Wikipedia | + | *[https://en.wikipedia.org/wiki/Absorbing_Markov_chain Wikipedia — Absorbing Markov chain] |
+ | |||
+ | [[Категория:Дискретная математика и алгоритмы]] | ||
+ | [[Категория: Марковские цепи ]] |
Текущая версия на 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
См. также
- Марковская цепь
- Расчет вероятности поглощения в состоянии
- Математическое ожидание времени поглощения