Фундаментальная матрица

Определение:

Фундаментальной матрицей (англ. 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]

См.также

• Марковская цепь
• Расчет вероятности поглощения в состоянии

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

• Дж. Кемени, Дж. Снелл — "Конечные цепи Маркова", издание "Наука", 1970г., стр. 66
• Wikipedia — Absorbing Markov Chain, Fundamental matrix