Редактирование: Расчёт вероятности поглощения в состоянии
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
| Текущая версия | Ваш текст | ||
| Строка 1: | Строка 1: | ||
| − | + | Поглощающее(существенное) состояние цепи Маркова — состояние с вероятностью перехода в самого себя <tex>p_{ii}=1</tex>. | |
| − | + | Составим матрицу <tex>G</tex>, элементы которой <tex>g_{ij}</tex> равны вероятности того, что, выйдя из <tex>i</tex>, попадём в поглощающее состояние <tex>j</tex>. | |
| − | Составим матрицу <tex> | ||
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
| − | <tex> | + | <tex> G = N \cdot R </tex>, где <tex>N</tex> — фундаментальная матрица, и <tex>R</tex> — матрица перехода из несущественных состояний в существенные. |
|proof= | |proof= | ||
Пусть этот переход будет осуществлён за <tex>r</tex> шагов: <tex>i</tex> → <tex>i_{1}</tex> → <tex>i_{2}</tex> → <tex>\ldots</tex> → <tex>i_{r-1}</tex> → j, где все <tex>i, i_{1}, \ldots i_{r-1}</tex> являются несущественными. | Пусть этот переход будет осуществлён за <tex>r</tex> шагов: <tex>i</tex> → <tex>i_{1}</tex> → <tex>i_{2}</tex> → <tex>\ldots</tex> → <tex>i_{r-1}</tex> → 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>\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> | + | Матрица <tex>G</tex> определяется их суммированием по всем длинам пути из i в j: <tex>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 | + | Выведем ответ: в <tex>\mathtt{i}</tex>-ой строке вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии. Естественно, для несущественного состояния это <tex>\mathtt{0}</tex>, в ином случае <tex>\mathtt{p_i=((\sum\limits_{k=1}^{n} G[k][j]+1)/n}</tex> где <tex>\mathtt{j}</tex> — номер соответствующий <tex>\mathtt{i}</tex>-ому состоянию в матрице <tex>\mathtt{G}</tex> (т.е. под которым оно располагалось в матрице <tex> \mathtt{R} </tex> т.е. значение <tex>\mathtt{position[i]}</tex>). Прибавлять <tex>\mathtt{1}</tex> нужно т.к. вероятность поглотиться в <tex>\mathtt{i}</tex>-ом поглощающем состоянии, оказавшись изначально в нем же равна <tex>\mathtt{1}</tex>. |
| − | *<tex>\mathtt{probability | + | *<tex>\mathtt{probability[i]}</tex> — вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии |
| − | *<tex>\mathtt{absorbing | + | *<tex>\mathtt{absorbing[i]}</tex> — является ли i-е состояние поглощающим |
| − | ''' | + | '''function''' getAbsorbingProbability(absorbing: boolean[n], G: float[n][n]) |
| − | + | float probability[n] | |
| − | |||
'''for''' i = 0 '''to''' n - 1 | '''for''' i = 0 '''to''' n - 1 | ||
| − | + | prob = 0 | |
'''if''' absorbing[i] | '''if''' absorbing[i] | ||
'''for''' j = 0 '''to''' nonabs - 1 | '''for''' j = 0 '''to''' nonabs - 1 | ||
| Строка 25: | Строка 23: | ||
prob /= n | prob /= n | ||
probability[i] = prob | probability[i] = prob | ||
| − | + | return probability | |
| − | |||
==См. также== | ==См. также== | ||
| Строка 33: | Строка 30: | ||
*[[Фундаментальная матрица]] | *[[Фундаментальная матрица]] | ||
*[[Теорема о поглощении]] | *[[Теорема о поглощении]] | ||
| − | |||
| − | |||
==Источники информации== | ==Источники информации== | ||
* [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://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BF%D1%8C_%28%D0%BC%D0%B0%D1%82%D0%B5%D0%BC.%29 Википедия — Цепи Маркова] | ||
