Изменения

[[Марковская цепь#Поглощающая цепь| Поглощающее(существенное) состояние цепи Маркова - ]] — состояние с вероятностью перехода в самого себя <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> - количество переходовом состоянии. Состояния и переходы пронумерованы от 0 до Естественно, для несущественного состояния это <tex>n - 10</tex>. Пусть входные данные хранятся , в массиве ином случае <tex>input\mathtt{p_i}=\left(\sum\limits_{k=1}^{n} \mathtt{G}[k][j]+1\right)/n</tex> где <tex>i\mathtt{j}</tex>-ая строка характеризует — номер соответствующий <tex>\mathtt{i}</tex>-ый переход таким образом: ому состоянию в матрице <tex>input[i][2]\mathtt{G}</tex> - вероятность перехода из состояния (т.е. под которым оно располагалось в матрице <tex>input[i][0]\mathtt{R} </tex> в состояние т.е. значение <tex>input\mathtt{position}[\mathtt{i][1}]</tex>).Создадим массив Прибавлять <tex>absorbing1</tex> типа Boolean, где нужно т.к. вероятность поглотиться в <tex>\mathtt{i}</tex>-ое ом поглощающем состоянии, оказавшись изначально в нем же равна <tex>true1</tex> обозначает что .*<tex>\mathtt{probability}[\mathtt{i}]</tex>-ое состояние является поглощающим. Если состояние поглощающее то с вероятностью 1 оно переходит само — вероятность поглощения в себя. Найдем такие состояния. Также посчитаем количество поглощающих состояний <tex>abs\mathtt{i}</tex>_-ом состоянии*<tex>num\mathtt{absorbing}[\mathtt{i}]</tex>.— является ли <code style = "display: inline-block;"tex> for \mathtt{i=0 to n}</tex>-1е состояние поглощающим  if (input '''float[i]''' getAbsorbingProbability(absorbing: '''boolean'''[0n] == input, G: '''float'''[in][1n] && input, position: '''int'''[i][2n] == 1): absorbing '''float''' probability[input[in][0]] = true; abs_num++; </code>Найдем число несущественных состояний <tex>nonabs '''for''' i =0 '''to''' n-abs</tex>_<tex>num</tex>. Теперь нужно заполнить массивы Q (переходов между несущественными состояниями) и R (переходов из несущественных состояний в поглощающие). Для этого создадим сначала массив <tex>position</tex> где <tex>i</tex>-ый элемент указывает под каким номером будет находиться <tex>i</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.1<code style = "display: inline-block;"> count_q '''float''' prob = 0; count_r = 0; '''if''' absorbing[i] '''for i ''' j = 0 '''to n ''' nonabs - 1 if abs prob += G[ij] [position[i] = count_r;] count_r prob++; else prob /= n position probability[i] = count_q;prob '''return''' probability count_q++; for i = 0 to m - 1=См. также== if absorbing*[input[i][1Марковская цепь]] if absabsorbing*[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>Найдем Матрицу E = I - Q и создадим единичную матрицу N.<code style = "display: inline-block;"> for iИсточники информации=0 to nonabs N[i][i]=1;' E* [ihttp://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BF%D1%8C_%28%D0%BC%D0%B0%D1%82%D0%B5%D0%BC.%29 Википедия — Цепи Маркова][i]=1; for j=0 to nonabs E* [i][j]http://www.studmed.ru/kemeni-dzh-snell-dzh-konechnye-cepi-=Q[i][jmarkova_eb290d9f6f2.html Кемени Дж. и Снелл Дж., "Конечные цепи Маркова"]; </code>