105
правок
Изменения
м
Пусть Для хранения переходов марковской цепи создадим структуру <tex> \mathtt{jump}</tex>. Введем <tex>\mathtt{transition}:</tex> <tex> \mathtt{jump}[\mathtt{m}] </tex> - массив переходов марковской цепи, где <tex>\mathtt{transition}[\mathtt{i}][2]\mathtt{.prob}</tex> - — вероятность перехода из состояния <tex>\mathtt{transition}[\mathtt{i}][0\mathtt{.from}</tex> в <tex>\mathtt{transition}[\mathtt{i}][1]\mathtt{.to}</tex>. Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> - — поглощающее состояние, то <tex>\mathtt{transition}[\mathtt{j}][2] \mathtt{.prob} = 1}</tex>. По этому признаку помно можно определить все поглощающие состояния в цепи.
Дмитрий Мурзин переименовал страницу Подсчет количества поглощающих состояний и построение матриц переходов марковской цепи в [[Подс…
==Подсчет количества поглощащих состояний==
===Псевдокод===
*<tex>\mathtt{absorbing}: boolean:[\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> - — количество переходов
'''functionboolean[]''' findAbsorbings(transition: '''intjump'''[m][2]): '''boolean''' absorbing[mn] '''for''' i = 0 '''tojump''' m - 1 i '''ifin''' transition absorbing[i.from][0] = i.from == transition[i][1] .to '''and''' transition[i][2] .prob == 1 absorbing[transition[i][0]] = ''true''
'''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> - — матрица из несущественных состояний в поглощающие.
'''procedurefloat[][]''' 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_q
count_q++
'''for''' '''jump''' i = 0 '''toin''' m - 1transition '''if''' absorbing[transition[i][1].to] '''if''' !absorbing[transition[i][0].from] R[position[transition[i][0].from]][position[transition[i][1].to]] = transition[i][2].prob
'''else'''
Q[position[transition[i][0].from]][position[transition[i][1].to]] = transition[i][2].prob '''return''' Q
== См. также ==
*[[Марковская цепь]]
*[[Расчет вероятности поглощения в состоянии]]
*[[Математическое ожидание времени поглощения]]
== Источники информации ==
*[https://en.wikipedia.org/wiki/Absorbing_Markov_chain Wikipedia: — Absorbing Markov chain]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Марковские цепи ]]
