Изменения

[[Марковская цепь#Поглощающая цепь| Поглощающее(существенное) состояние цепи Маркова - ]] — состояние с вероятностью перехода в самого себя <tex>p_{ii}=1</tex>. Составим матрицу <tex>\mathtt{G}</tex>, элементы которой <tex>g_{ij}</tex> равны вероятности того, что, выйдя из <tex>i</tex>, попадём в поглощающее состояние <tex>j</tex>.

<tex> \mathtt{G } = N \cdot R </tex>, где <tex>N</tex> — фундаментальная матрица, и <tex>R</tex> — матрица перехода из несущественных состояний в существенные.

Пусть этот переход будет осуществлён за <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>n\mathtt{i}</tex> - количество состояний Марковской цепи, ой строке вероятность поглощения в <tex>m\mathtt{i}</tex> - количество переходовом состоянии. Состояния пронумерованы от Естественно, для несущественного состояния это <tex>0</tex> до , в ином случае <tex>\mathtt{p_i}=\left(\sum\limits_{k=1}^{n - } \mathtt{G}[k][j]+1<\right)/tex>, переходы от <tex>0n</tex> до где <tex>m - 1\mathtt{j}</tex>. Входные данные хранятся в массиве <tex>input</tex> где — номер соответствующий <tex>\mathtt{i}</tex>-ая строка характеризует ому состоянию в матрице <tex>i\mathtt{G}</tex>-ый переход таким образом: (т.е. под которым оно располагалось в матрице <tex>input[i][2]\mathtt{R} </tex> - вероятность перехода из состояния т.е. значение <tex>input\mathtt{position}[\mathtt{i][0}]</tex> в состояние ). Прибавлять <tex>input[i][1]</tex>нужно т.к.Создадим массив <tex>absorbing</tex> типа boolean, где вероятность поглотиться в <tex>\mathtt{i}</tex>-ое true обозначает что ом поглощающем состоянии, оказавшись изначально в нем же равна <tex>i</tex>-ое состояние является поглощающим и наоборот. Обнаружим поглощающие состояния по такому признаку: если состояние поглощающее то с вероятностью 1 оно переходит само в себя. Также посчитаем количество поглощающих состояний <tex>abs</tex>.*<code style = "display: inline-block;"tex> '''for''' i=0 '''to''' n - 1 '''if''' input\mathtt{probability}[\mathtt{i}][0] == input[i][1] '''and''' input[i][2] == 1 absorbing[input[i][0]] = true; abs++;</code>Найдем число несущественных состояний <tex>nonabs = n - abs</tex>. Теперь нужно заполнить матрицы <tex>Q</tex> (переходов между несущественными состояниями) и <tex>R</tex> (переходов из несущественных состояний — вероятность поглощения в поглощающие). Для этого создадим сначала массив <tex>position\mathtt{i}</tex> где -ом состоянии*<tex>\mathtt{absorbing}[\mathtt{i}]</tex>-ый элемент указывает под каким номером будет находиться — является ли <tex>\mathtt{i}</tex>-ое е состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.<code style = "display: inline-block;"> count_q = 0;поглощающим count_r = 0; '''for''' i = 0 '''to''' n - 1 '''if''' abs[i] position[i] = count_r; count_r++; '''else''' positionfloat[i] = count_q; count_q++; '''for''' i = 0 '''to''' m - 1 if getAbsorbingProbability(absorbing[input[i][1]] : '''ifboolean''' !absabsorbing[input[in][0]] R[position[input[i][0]]][position[input[i][1]]] = input[i][2]; , G: '''elsefloat''' Q[position[input[in][0n]]][, position[input[i][1]]] = input[i][2];</code>Найдем Матрицу <tex>E = I - Q</tex> и создадим единичную матрицу <tex>N</tex>.<code style = "display: inline-block;"> '''for''' i = 0 '''toint''' nonabs - 1 N[in][i] = 1; E[i][i] = 1;): '''forfloat''' j = 0 '''to''' nonabs - 1 Eprobability[in][j] -= Q[i][j]; </code>Теперь приведем матрицу <tex>E</tex> к единичной методом Гаусса - Жордана, применяя те же преобразования к матрице <tex>N</tex>.<code style = "display: inline-block;"> '''for''' i = 0 '''to''' nonabs n - 1 '''if''' E[i][i] != 1 mul = E[i][i]; '''forfloat''' j prob = 0 '''to''' nonabs - 1 E[i][j] /= mul; N[i][j] /= mul; '''for''' row = 0 '''to''' nonabs - 1 '''if''' i != row mul = E[row]absorbing[i];

E[row][j] -prob += mul * E[i]G[j]; N[row][j] -= mul * Nposition[i][j];</code> prob++В результате <tex>N = E^{-1}</tex> т.е. <tex>N< prob /tex> - фундаментальная матрица Марковской цепи. Найдем матрицу <tex>G = N * R</tex>.n<code style probability[i] = "display: inline-block;">prob '''for''' i = 0 '''to''' nonabs - 1 '''forreturn''' j probability ==См. также== 0 '''to''' absorbing - 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>-ом состоянии. Естественно для несущественного состояния это 0, в ином случае <tex>p_i=(($$\sum_{k=1}^n GИсточники информации==* [k][j]$$)+1)http:/n</tex> где <tex>j<ru.wikipedia.org/tex> - номер соответствующий <tex>i<wiki/tex>-ому состоянию в матрице <tex>G<%D0%A6%D0%B5%D0%BF%D1%8C_%28%D0%BC%D0%B0%D1%82%D0%B5%D0%BC.%29 Википедия — Цепи Маркова]* [http:/tex> (т.е. под которым оно располагалось в матрице <tex>R</tex> тwww.еstudmed. значение <tex>position[i]<ru/tex>)kemeni-dzh-snell-dzh-konechnye-cepi-markova_eb290d9f6f2. Прибавлять 1 нужно тhtml Кемени Дж.ки Снелл Дж. вероятность поглотиться в <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>