Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи — различия между версиями
Arimon (обсуждение | вклад) м (Косметические изменения) |
м (Дмитрий Мурзин переименовал страницу Подсчет количества поглощающих состояний и построение матриц переходов марковской цепи в [[Подс…) |
||
(не показано 5 промежуточных версий 1 участника) | |||
Строка 2: | Строка 2: | ||
Для хранения переходов марковской цепи создадим структуру <tex> \mathtt{jump}</tex>. | Для хранения переходов марковской цепи создадим структуру <tex> \mathtt{jump}</tex>. | ||
− | Введем <tex>\mathtt{transition}</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>. По этому признаку можно определить все поглощающие состояния в цепи. | Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> — поглощающее состояние, то <tex>\mathtt{transition}[\mathtt{j}]\mathtt{.prob} = 1</tex>. По этому признаку можно определить все поглощающие состояния в цепи. | ||
Строка 14: | Строка 14: | ||
'''boolean''' absorbing[n] | '''boolean''' absorbing[n] | ||
− | '''for''' jump i | + | '''for''' '''jump''' i '''in''' transition |
absorbing[i.from] = i.from == i.to '''and''' i.prob == 1 | absorbing[i.from] = i.from == i.to '''and''' i.prob == 1 | ||
Строка 29: | Строка 29: | ||
'''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 | ||
Строка 38: | Строка 41: | ||
count_q++ | count_q++ | ||
− | '''for''' i | + | '''for''' '''jump''' i '''in''' transition |
− | '''if''' absorbing | + | '''if''' absorbing[i.to] |
− | '''if''' !absorbing | + | '''if''' !absorbing[i.from] |
− | R[position | + | R[position[i.from]][position[i.to]] = i.prob |
'''else''' | '''else''' | ||
− | Q[position | + | Q[position[i.from]][position[i.to]] = i.prob |
− | '''return | + | '''return''' Q |
== См. также == | == См. также == |
Версия 23:48, 31 января 2019
Содержание
Подсчет количества поглощащих состояний
Для хранения переходов марковской цепи создадим структуру
.Введем
, где — вероятность перехода из состояния в .Тогда, по определению поглощающего состояния, если
— поглощающее состояние, то . По этому признаку можно определить все поглощающие состояния в цепи.Псевдокод
- — массив состояний. Если — посглощающее состояние иначе
- — количество состояний
- — количество переходов
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
См. также
- Марковская цепь
- Расчет вероятности поглощения в состоянии
- Математическое ожидание времени поглощения