Фундаментальная матрица — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 13 промежуточных версий 7 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Фундаментальной матрицей цепи Маркова называется матрица <tex> N = \sum\limits_{i=1}^{\infty} Q^n</tex>, где Q - матрица переходов между непоглощающими состояниями.
+
'''Фундаментальной матрицей''' (англ. ''Fundamental matrix'') цепи Маркова называется матрица <tex> N = \sum\limits_{i=0}^{\infty} Q^n</tex>, где <tex>Q</tex> — '''матрица переходов между непоглощающими состояниями''', в которой отсутствуют строки с [[Марковская цепь#Поглощающая цепь | поглощающими состояниями]]
 
}}
 
}}
  
Строка 10: Строка 10:
 
Домножим обе части равенства в определении на <tex> (I - Q) </tex>:
 
Домножим обе части равенства в определении на <tex> (I - Q) </tex>:
  
<tex> (I - Q)N = (I - Q)(I + Q + Q^2 + \ldots) = I - Q + Q - Q^2 + Q^3 - Q^3 + \ldots = I</tex>
+
<tex> (I - Q)N = (I - Q)(I + Q + Q^2 + \ldots) = I - Q + Q - Q^2 + Q^2 - Q^3 + \ldots = I</tex>
  
 
Так как <tex> \lim\limits_{n \rightarrow \infty} Q ^ n = 0 </tex>, то ряд действительно сходится.
 
Так как <tex> \lim\limits_{n \rightarrow \infty} Q ^ n = 0 </tex>, то ряд действительно сходится.
 
Далее, домножив на <tex> (I - Q) ^ {-1} </tex>, получим требуемое равенство.
 
Далее, домножив на <tex> (I - Q) ^ {-1} </tex>, получим требуемое равенство.
  
Осталось лишь доказать, что матрица <tex> (I - Q) ^ {-1} </tex> существует, то есть <tex>(I - Q) </tex> - невырожденная. Рассмотрим систему линейных уравнений вида:
+
Осталось лишь доказать, что матрица <tex> (I - Q) ^ {-1} </tex> существует, то есть <tex>(I - Q) </tex> невырожденная. Рассмотрим систему линейных уравнений вида:
  
 
<tex> (I - Q) x = 0 </tex>
 
<tex> (I - Q) x = 0 </tex>
Строка 31: Строка 31:
 
Аналогично, <tex> x = Q^nx </tex> для сколь угодно большого n.
 
Аналогично, <tex> x = Q^nx </tex> для сколь угодно большого n.
  
Так как <tex> \lim\limits_{n \rightarrow \infty} Q ^ n = 0 </tex>, то обязательно <tex> x = 0</tex>. Значит, по альтернативе Фредгольма, матрица <tex> I - Q</tex> - невырожденная.
+
Так как <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]
 +
 
 +
[[Категория:Дискретная математика и алгоритмы]]
 +
 
 +
[[Категория: Марковские цепи ]]

Текущая версия на 19:33, 4 сентября 2022

Определение:
Фундаментальной матрицей (англ. Fundamental matrix) цепи Маркова называется матрица [math] N = \sum\limits_{i=0}^{\infty} Q^n[/math], где [math]Q[/math]матрица переходов между непоглощающими состояниями, в которой отсутствуют строки с поглощающими состояниями


Теорема:
[math] N = (I - Q) ^ {-1} [/math]
Доказательство:
[math]\triangleright[/math]

Домножим обе части равенства в определении на [math] (I - Q) [/math]:

[math] (I - Q)N = (I - Q)(I + Q + Q^2 + \ldots) = I - Q + Q - Q^2 + Q^2 - Q^3 + \ldots = I[/math]

Так как [math] \lim\limits_{n \rightarrow \infty} Q ^ n = 0 [/math], то ряд действительно сходится. Далее, домножив на [math] (I - Q) ^ {-1} [/math], получим требуемое равенство.

Осталось лишь доказать, что матрица [math] (I - Q) ^ {-1} [/math] существует, то есть [math](I - Q) [/math] — невырожденная. Рассмотрим систему линейных уравнений вида:

[math] (I - Q) x = 0 [/math]

[math] Ix = Qx [/math]

[math] x = Qx [/math]

Домножив слева последнее равенство на матрицу [math] Q [/math] слева, получим:

[math] Qx = Q^2x [/math]

Но [math] x = Qx [/math], значит, [math] x = Q^2x [/math]

Аналогично, [math] x = Q^nx [/math] для сколь угодно большого n.

Так как [math] \lim\limits_{n \rightarrow \infty} Q ^ n = 0 [/math], то обязательно [math] x = 0[/math]. Значит, по альтернативе Фредгольма, матрица [math] (I - Q)[/math] — невырожденная.
[math]\triangleleft[/math]

Применение

Фундаментальная матрица задает средние времена, которые марковский процесс проводит в непоглощающих состояниях.

Так же фундаментальная матрица используется при расчете вероятности поглощения в состоянии

Построение матриц переходов

Cоздадим сначала массив [math]\mathtt{position}[/math], где [math]\mathtt{i}[/math]-ый элемент указывает под каким номером будет находиться [math]\mathtt{i}[/math]-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.

Псевдокод

  • [math]\mathtt{position[n]}[/math] — массив нумерации состояний относительно существенной/ несущественной матрицы.
  • [math]\mathtt{Q}[/math] — матрица перехода мужду несущественными состояниями.
  • [math]\mathtt{R}[/math] — матрица перехода из несущественных состояний в поглощающие.
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]

См.также

Источники информации