19
правок
Изменения
Лишний псевдокод вынесене в одельную статью и редактирован(ссылка добавлена в "Смотри также", имена переменных были обернуты в \mathtt.
Тогда рассмотрим сумму <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>, где <tex>Q</tex> - матрица переходов между несущественными состояниями, <tex>R</tex> - из несущественного в существенное.
Матрица <tex>G</tex> определяется их суммированием по всем длинам пути из 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\mathtt{i}</tex> - количество состояний Марковской цепи, ой строке вероятность поглощения в <tex>m\mathtt{i}</tex> - количество переходовом состоянии. Состояния пронумерованы от Естественно, для несущественного состояния это <tex>\mathtt{0}</tex> до , в ином случае <tex>\mathtt{p_i=((\sum_{k=1}^n - G[k][j]+1<)/tex>, переходы от <tex>0</tex> до <tex>m - 1</tex>. Входные данные хранятся в массиве <tex>inputn}</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[i][1]}</tex>).Создадим массив Прибавлять <tex>absorbing\mathtt{1}</tex> типа boolean, где <tex>i</tex>-ое true обозначает что нужно т.к. вероятность поглотиться в <tex>\mathtt{i}</tex>-ое состояние является поглощающим и наоборот. Обнаружим поглощающие состояния по такому признаку: если состояние поглощающееом поглощающем состоянии, то с вероятностью 1 оно переходит само оказавшись изначально в себя. Также посчитаем количество поглощающих состояний нем же равна <tex>abs\mathtt{1}</tex>.*<code style = "display: inline-block;"tex> '''for''' i = 0 '''to''' m - 1 '''if''' input[i][0] == input\mathtt{probability[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</tex> где <tex>\mathtt{i}</tex>-ый элемент указывает под каким номером будет находиться ом состоянии*<tex>\mathtt{absorbing[i]}</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.<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 '''iffunction''' getAbsorbingProbability(absorbing: boolean[input[in][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, G: inline-block;"> '''for''' i = 0 '''to''' nonabs - 1 Nfloat[in][in] = 1) Efloat probability[i][in] = 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 n - 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 prob = 0 '''to''' nonabs - 1 '''if''' i <tex> \neq </tex> row mul = E[row]absorbing[i]
'''for''' j = 0 '''to''' nonabs - 1
=Литература=Смотри также==*[http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%B4%D1%81%D1%87%D0%B5%D1%82_%D0%BA%D0%BE%D0%BB%D0%B8%D1%87%D0%B5%D1%81%D1%82%D0%B2%D0%B0_%D0%BF%D0%BE%D0%B3%D0%BB%D0%BE%D1%89%D0%B0%D1%8E%D1%89%D0%B8%D1%85_%D1%81%D0%BE%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B9_%D0%B8_%D0%BF%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86_%D0%BF%D0%B5%D1%80%D0%B5%D1%85%D0%BE%D0%B4%D0%BE%D0%B2_%D0%BC%D0%B0%D1%80%D0%BA%D0%BE%D0%B2%D1%81%D0%BA%D0%BE%D0%B9_%D1%86%D0%B5%D0%BF%D0%B8 Подсчет количества поглощающих состояний и построение матриц переходов марковской цепи]==Источники информации==
* [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 Википедия - Цепи Маркова]
* Кемени Дж., Снелл Дж. "Конечные цепи Маркова".
