Изменения

Перейти к: навигация, поиск

Расчёт вероятности поглощения в состоянии

2735 байт добавлено, 23:48, 31 января 2019
м
[[Марковская цепь#Поглощающая цепь| Поглощающее(существенное) состояние цепи Маркова - ]] — состояние с вероятностью перехода в самого себя <tex>p_{ii}=1</tex>. Составим матрицу <tex>\mathtt{G}</tex>, элементы которой <tex>g_{ij}</tex> равны вероятности того, что, выйдя из <tex>i</tex>, попадём в поглощающее состояние <tex>j</tex>.
{{Теорема
|statement=
<tex> \mathtt{G } = N \cdot R </tex>, где <tex>N</tex> — фундаментальная матрица, и <tex>R</tex> — матрица перехода из несущественных состояний в существенные.
|proof=
Пусть этот переход будет осуществлён за <tex>r </tex> шагов: <tex>i </tex> &rarr; <tex>i_{1}</tex> &rarr; <tex>i_{2}</tex> &rarr; ... <tex>\ldots</tex> &rarr; <tex>i_{r-1}</tex> &rarr; j, где все <tex>i, i_{1}, ... \ldots i_{r-1}</tex> являются несущественными.Тогда рассмотрим сумму <tex>\sum\limits_{\forall(i_{1} ... \ldots i_{r-1})} {p_{i, i_{1}} \cdot p_{i_{1}, i_{2}} \cdot ... \ldots \cdot p_{i_{r-1}, j}} = Q^{r-1} \cdot R</tex>, где <tex>Q - </tex> — матрица переходов между несущественными состояниями, <tex>R - </tex> — из несущественного в существенное. Матрица <tex>\mathtt{G }</tex> определяется их суммированием по всем длинам пути из i в j: <tex>\mathtt{G } = \sum\limits_{r = 1}^{\infty}{Q^{r-1} \cdot R} = (I + Q + Q^{2} + Q^{3} + ...\ldots) \cdot R = NR</tex>, т.к. <tex>(I + Q + Q^2 + ...\ldots) \cdot (I - Q) = I - Q + Q - Q^{2} + ... \ldots = I</tex>, а фундаментальная матрица марковской цепи <tex>N = (I - Q)^{-1}</tex> }}=Литература=Псевдокод==Выведем ответ: в <tex>\mathtt{i}</tex>-ой строке вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии. Естественно, для несущественного состояния это <tex>0</tex>, в ином случае <tex>\mathtt{p_i}=\left(\sum\limits_{k=1}^{n} \mathtt{G}[k][j]+1\right)/n</tex> где <tex>\mathtt{j}</tex> — номер соответствующий <tex>\mathtt{i}</tex>-ому состоянию в матрице <tex>\mathtt{G}</tex> (т.е. под которым оно располагалось в матрице <tex> \mathtt{R} </tex> т.е. значение <tex>\mathtt{position}[\mathtt{i}]</tex>). Прибавлять <tex>1</tex> нужно т.к. вероятность поглотиться в <tex>\mathtt{i}</tex>-ом поглощающем состоянии, оказавшись изначально в нем же равна <tex>1</tex>.*<tex>\mathtt{probability}[\mathtt{i}]</tex> — вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии*<tex>\mathtt{absorbing}[\mathtt{i}]</tex> — является ли <tex>\mathtt{i}</tex>-е состояние поглощающим  '''float[]''' getAbsorbingProbability(absorbing: '''boolean'''[n], G: '''float'''[n][n], position: '''int'''[n]): '''float''' probability[n] '''for''' i = 0 '''to''' n - 1 '''float''' prob = 0 '''if''' absorbing[i] '''for''' j = 0 '''to''' nonabs - 1 prob += G[j][position[i]] prob++ prob /= n probability[i] = prob '''return''' probability ==См. также==*[[Марковская цепь]]*[[Подсчет количества поглощающих состояний и построение матриц переходов марковской цепи]]*[[Фундаментальная матрица]]*[[Теорема о поглощении]]*[[Математическое ожидание времени поглощения]] ==Источники информации==* [http://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BF%D1%8C_%28%D0%BC%D0%B0%D1%82%D0%B5%D0%BC.%29, Википедия - Цепи Маркова]* [http://www.studmed.ru/kemeni-dzh-snell-dzh-konechnye-cepi-markova_eb290d9f6f2.html Кемени Дж., и Снелл Дж. , "Конечные цепи Маркова".]  [[Категория:Дискретная математика и алгоритмы]] [[Категория: Марковские цепи ]]

Навигация