Изменения
Нет описания правки
{{Определение
|definition=
'''Фундаментальной матрицей ''' (англ. ''Fundamental matrix'') цепи Маркова называется матрица <tex> N = \sum\limits_{i=10}^{\infty} Q^n</tex>, где <tex>Q - </tex> — '''матрица переходов между непоглощающими состояниями. ''', в которой отсутствуют строки с [[Марковская цепь#Поглощающая цепь | поглощающими состояниями]]
}}
Домножим обе части равенства в определении на <tex> (I - Q) </tex>:
<tex> (I - Q)N = (I - Q)(I + Q + Q^2 + \ldots) = I - Q + Q - Q^2 + Q^3 2 - Q^3 + \ldots = I</tex>
Так как <tex> \lim\limits_{n \rightarrow \infty} Q ^ n = 0 </tex>, то ряд действительно сходится.
Далее, домножив на <tex> (I - Q) ^ {-1} </tex>, получим требуемое равенство.
Осталось лишь доказать, что матрица <tex> (I - Q) ^ {-1} </tex> существует, то есть <tex>(I - Q) </tex> — невырожденная. Рассмотрим систему линейных уравнений вида:
<tex> (I - Q) x = 0 </tex>
<tex> Ix = Qx </tex>
<tex> x = Qx </tex>
Домножив слева последнее равенство на матрицу <tex> Q </tex> слева, получим:
<tex> Qx = Q^2x </tex>
Но <tex> x = Qx </tex>, значит, <tex> x = Q^2x </tex>
Аналогично, <tex> x = Q^nx </tex> для сколь угодно большого n.
Так как <tex> \lim\limits_{n \rightarrow \infty} Q ^ n = 0 </tex>, то обязательно <tex> x = 0</tex>. Значит, по альтернативе Фредгольма, матрица <tex> (I - Q)</tex> — невырожденная.
}}
== Применение ==
Фундаментальная матрица задает средние времена, которые марковский процесс проводит в непоглощающих состояниях.
Так же фундаментальная матрица используется при [[Расчет вероятности поглощения в состоянии|расчете вероятности поглощения в состоянии]]
==Построение матриц переходов==
Cоздадим сначала массив <tex>\mathtt{position}</tex>, где <tex>\mathtt{i}</tex>-ый элемент указывает под каким номером будет находиться <tex>\mathtt{i}</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
===Псевдокод===
*<tex>\mathtt{position[n]}</tex> — массив нумерации состояний относительно существенной/ несущественной матрицы.
*<tex>\mathtt{Q}</tex> — матрица перехода мужду несущественными состояниями.
*<tex>\mathtt{R}</tex> — матрица перехода из несущественных состояний в поглощающие.
'''procedure''' buildTransitionMatrix()
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[transition[i][1]]
'''if''' !absorbing[transition[i][0]]
R[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]
'''else'''
Q[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]
== См.также ==
* [[Марковская цепь]]
* [[Расчет вероятности поглощения в состоянии]]
== Источники информации ==
* ''Дж. Кемени, Дж. Снелл'' — "Конечные цепи Маркова", издание "Наука", 1970г., стр. 66
* [https://en.wikipedia.org/wiki/Absorbing_Markov_chain#Fundamental_matrix Wikipedia — Absorbing Markov Chain, Fundamental matrix]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Марковские цепи ]]
