Граф переходов, связность и эргодические цепи Маркова

Для цепи Маркова с непрерывным временем строится ориентированный граф переходов (кратко — граф переходов) по следующим правилам:

• Множество вершин графа совпадает со множеством состояний цепи.
• Вершины  соединяются ориентированным ребром , если qij > 0 (то есть интенсивность потока из i го состояния в j е положительна.

Топологические свойства графа переходов связаны со спектральными свойствами матрицы Q. В частности, для конечных цепей Маркова верны следующие теоремы:

• Следующие три свойства А, Б, В конечной цепи Маркова эквивалентны (обладающие ими цепи иногда называют слабо эргодическими):

А. Для любых двух различных вершин графа переходов  найдется такая вершина k графа («общий сток»), что существуют ориентированные пути от вершины i к вершине k и от вершины j к вершине k. Замечание: возможен случай k = i или k = j; в этом случае тривиальный (пустой) путь от i к i или от j к j также считается ориентированным путем.

Б. Нулевое собственное число матрицы Q невырождено.

В. При  матрица P (t) стремится к матрице, у которой все строки совпадают (и совпадают, очевидно, с равновесным распределением).

• Следующие пять свойств А, Б, В, Г, Д конечной цепи Маркова эквивалентны (обладающие ими цепи называют эргодическими):

А. Граф переходов цепи ориентированно связен.

Б. Нулевое собственное число матрицы Q невырождено и ему соответствует строго положительный левый собственный вектор (равновесное распределение).

В. Для некоторого t > 0 матрица P (t) строго положительна (то есть P _ij (t) > 0 для всех i, j).

Г. Для всех tt > 0 матрица P (t) строго положительна.

Д. При t ®¥ матрица P (t) стремится к строго положительной матрице, у которой все строки совпадают (и совпадают, очевидно, с равновесным распределением).

Примеры

Рис. Примеры графов переходов для цепей Маркова: a) цепь не является слабо эргодической (не существует общего стока для состояний ); b) слабо эргодическая, но не эргодическая цепь (граф переходов не является ориентированно связным) c) эргодическая цепь (граф переходов ориентированно связен).

Рассмотрим цепи Маркова с тремя состояниями и с непрерывным временем, соответствующие графам переходов, представленным на рис. В случае (a) отличны от нуля только следующие недиагональные элементы матрицы интенсивностей — , в случае (b) отличны от нуля только , а в случае (c) — . Остальные элементы определяются свойствами матрицы  (сумма элементов в каждой строке равна 0). В результате для графов (a), (b), (c) матрицы интенсивностей имеют вид: