Редактирование: Расчёт вероятности поглощения в состоянии
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 1: | Строка 1: | ||
− | + | Поглощающее(существенное) состояние цепи Маркова - состояние с вероятностью перехода в самого себя <tex>p_{ii}=1</tex>. | |
− | + | Составим матрицу G, элементы которой <tex>g_{ij}</tex> равны вероятности того, что, выйдя из i, попадём в поглощающее состояние j. | |
− | Составим матрицу | ||
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
− | <tex> | + | <tex> G = N \cdot R </tex> |
|proof= | |proof= | ||
− | Пусть этот переход будет осуществлён за | + | Пусть этот переход будет осуществлён за r шагов: i → <tex>i_{1}</tex> → <tex>i_{2}</tex> → ... → <tex>i_{r-1}</tex> → j, где все <tex>i, i_{1}, ... i_{r-1}</tex> являются несущественными. |
− | Тогда рассмотрим сумму <tex>\sum\limits_{\forall(i_{1} | + | Тогда рассмотрим сумму <tex>\sum\limits_{\forall(i_{1} ... i_{r-1})} {p_{i, i_{1}} \cdot p_{i_{1}, i_{2}} \cdot ... \cdot p_{i_{r-1}, j}} = Q^{r-1} \cdot R</tex>, где Q - матрица переходов между несущественными состояниями, R - из несущественного в существенное. |
− | Матрица | + | Матрица G определяется их суммированием по всем длинам пути из i в j: <tex>G = \sum\limits_{r = 1}^{\infty}{Q^{r-1} \cdot R} = (I + Q + Q^{2} + Q^{3} + ...) \cdot R = NR</tex>, т.к. <tex>(I + Q + Q^2 + ...) \cdot (I - Q) = I - Q + Q - Q^{2} + ... = I</tex>, а фундаментальная матрица марковской цепи <tex>N = (I - Q)^{-1}</tex> }} |
− | + | =Псевдокод= | |
− | + | Пусть <tex>n</tex> - количество состояний Марковской цепи, <tex>m</tex> - количество переходов. Состояния пронумерованы от <tex>0</tex> до <tex>n - 1</tex>, переходы от <tex>0</tex> до <tex>m - 1</tex>. Входные данные хранятся в массиве <tex>input</tex> где <tex>i</tex>-ая строка характеризует <tex>i</tex>-ый переход таким образом: <tex>input[i][2]</tex> - вероятность перехода из состояния <tex>input[i][0]</tex> в состояние <tex>input[i][1]</tex>. | |
− | + | Создадим массив <tex>absorbing</tex> типа boolean, где <tex>i</tex>-ое true обозначает что <tex>i</tex>-ое состояние является поглощающим и наоборот. Обнаружим поглощающие состояния по такому признаку: если состояние поглощающее, то с вероятностью 1 оно переходит само в себя. Также посчитаем количество поглощающих состояний <tex>abs</tex>. | |
− | + | <code style = "display: inline-block;"> | |
− | + | '''for''' i = 0 '''to''' m - 1 | |
− | ''' | + | '''if''' input[i][0] == input[i][1] '''and''' input[i][2] == 1 |
− | ''' | + | absorbing[input[i][0]] = ''true'' |
− | + | abs++ | |
− | '''for''' | + | </code> |
− | + | Найдем число несущественных состояний <tex>nonabs = n - abs</tex>. Теперь нужно заполнить матрицы <tex>Q</tex> (переходов между несущественными состояниями) и <tex>R</tex> (переходов из несущественных состояний в поглощающие). Для этого создадим сначала массив <tex>position</tex> где <tex>i</tex>-ый элемент указывает под каким номером будет находиться <tex>i</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы. | |
− | '''if''' | + | <code style = "display: inline-block;"> |
+ | count_q = 0 | ||
+ | count_r = 0 | ||
+ | '''for''' i = 0 '''to''' n - 1 | ||
+ | '''if''' absorbing[i] | ||
+ | position[i] = count_r | ||
+ | count_r++ | ||
+ | '''else''' | ||
+ | position[i] = count_q | ||
+ | count_q++ | ||
+ | '''for''' i = 0 '''to''' m - 1 | ||
+ | '''if''' absorbing[input[i][1]] | ||
+ | '''if''' !absorbing[input[i][0]] | ||
+ | R[position[input[i][0]]][position[input[i][1]]] = input[i][2] | ||
+ | '''else''' | ||
+ | Q[position[input[i][0]]][position[input[i][1]]] = input[i][2] | ||
+ | </code> | ||
+ | Найдем Матрицу <tex>E = I - Q</tex> и создадим единичную матрицу <tex>N</tex>. | ||
+ | <code style = "display: inline-block;"> | ||
+ | '''for''' i = 0 '''to''' nonabs - 1 | ||
+ | N[i][i] = 1 | ||
+ | E[i][i] = 1 | ||
+ | '''for''' j = 0 '''to''' nonabs - 1 | ||
+ | E[i][j] -= Q[i][j] | ||
+ | </code> | ||
+ | Теперь приведем матрицу <tex>E</tex> к единичной методом Гаусса - Жордана, применяя те же преобразования к матрице <tex>N</tex>. | ||
+ | <code style = "display: inline-block;"> | ||
+ | '''for''' i = 0 '''to''' nonabs - 1 | ||
+ | '''if''' E[i][i] <tex> \neq </tex> 1 | ||
+ | mul = E[i][i] | ||
+ | '''for''' j = 0 '''to''' nonabs - 1 | ||
+ | E[i][j] /= mul | ||
+ | N[i][j] /= mul | ||
+ | '''for''' row = 0 '''to''' nonabs - 1 | ||
+ | '''if''' i <tex> \neq </tex> row | ||
+ | mul = E[row][i] | ||
'''for''' j = 0 '''to''' nonabs - 1 | '''for''' j = 0 '''to''' nonabs - 1 | ||
− | + | E[row][j] -= mul * E[i][j] | |
− | + | N[row][j] -= mul * N[i][j] | |
− | + | </code> | |
− | + | В результате <tex>N = E^{-1}</tex> т.е. <tex>N</tex> - фундаментальная матрица Марковской цепи. Найдем матрицу <tex>G = NR</tex>. | |
− | + | <code style = "display: inline-block;"> | |
− | ''' | + | '''for''' i = 0 '''to''' nonabs - 1 |
− | + | '''for''' j = 0 '''to''' abs - 1 | |
− | + | G[i][j] = 0 | |
− | + | '''for''' k = 0 '''to''' nonabs - 1 | |
− | + | G[i][j] += N[i][k] * R[k][j] | |
− | + | </code> | |
− | *[ | + | Выведем ответ: в <tex>i</tex>-ой строке вероятность поглощения в <tex>i</tex>-ом состоянии. Естественно, для несущественного состояния это <tex>0</tex>, в ином случае <tex>p_i=(($$\sum_{k=1}^n G[k][j]$$)+1)/n</tex> где <tex>j</tex> - номер соответствующий <tex>i</tex>-ому состоянию в матрице <tex>G</tex> (т.е. под которым оно располагалось в матрице <tex>R</tex> т.е. значение <tex>position[i]</tex>). Прибавлять 1 нужно т.к. вероятность поглотиться в <tex>i</tex>-ом поглощающем состоянии, оказавшись изначально в нем же равна 1. |
− | + | <code style = "display: inline-block;"> | |
− | + | '''for''' i = 0 '''to''' n - 1 | |
− | == | + | prob = 0 |
− | + | '''if''' absorbing[i] | |
− | + | '''for''' j = 0 '''to''' nonabs - 1 | |
+ | prob += G[j][position[i]] | ||
+ | prob++ | ||
+ | prob /= n | ||
+ | println(prob) | ||
+ | </code> | ||
+ | =Литература= | ||
+ | * [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 Википедия - Цепи Маркова] | ||
+ | * Кемени Дж., Снелл Дж. "Конечные цепи Маркова". | ||
[[Категория:Дискретная математика и алгоритмы]] | [[Категория:Дискретная математика и алгоритмы]] | ||
[[Категория: Марковские цепи ]] | [[Категория: Марковские цепи ]] |