Дискретная математика: графы и автоматы. Альпин Ю.А - 47 стр.

§ 6. Цепи Маркова                                                     47


    Теорема 2. Марковская система с матрицей переходных веро-
ятностей P = (pij ) тогда и только тогда является эргодической,
когда граф цепи примитивен.
   Д о к а з а т е л ь с т в о. Если положительный предел lim P k =
                                                              k→∞
P ∞ существует, то для достаточно больших k матрицы P k обязаны
быть положительными. Но это и означает, что граф цепи примитивен.
   Обратно, пусть граф цепи примитивен и, следовательно, P — при-
митивная матрица. В силу п.1 леммы 3 для любого вещественного
столбца x имеем последовательность вложенных отрезков
                    [x] ⊇ [P x] ⊇ ... ⊇ [P k x] ⊇ . . . .
Докажем, что эта последовательность стягивается в точку и, следо-
вательно, элементы столбцов P k x сходятся при k → ∞ к общему
пределу.
   Действительно, пусть m — показатель, для которого P m > 0 (в
силу следствия 1 предложения 5 §5 можно положить m = n2 −2n+2).
Согласно упражнению 3 имеем δ(P m ) < 1, а применяя п.2 леммы 3,
получаем
              d(P ml x) ≤ δ l (P m )d(x) → 0 при l → ∞ .
    Таким образом, невозрастающая последовательность d(P k x) со-
держит подпоследовательность, стремящуюся к нулю. Значит, и вся
последовательность сходится к нулю и желаемое доказано. Теперь по-
ложим x = ej , где ej — столбец с единицей на j-м месте и нулями на
прочих. Столбец P k ej равен j-му столбцу матрицы P k , его элементы
сходятся при k → ∞ к некоторому общему пределу πj . ¤
    Вычисление вектора предельных вероятностей π = (π1 , ..., πn ) ос-
новано на простых сведениях из линейной алгебры. Переходя к преде-
лу в равенстве P k P = P k+1 , получаем равенство P ∞ P = P ∞ , то есть,
πP = π. Задача свелась к вычислению собственного вектора, отвеча-
ющего данному собственному значению. В нашем случае собственное
подпространство, отвечающее собственному значению 1, одномерно
(докажите это) и, следовательно, содержит единственный стохасти-
ческий вектор.
    На основе теоремы 1 легко понять асимптотику переходных ве-
роятностей и в том случае, когда граф марковской системы сильно
связен, но не примитивен, то есть, d > 1. Предположим, что матри-
ца P системы находится в нормальной форме и рассмотрим матрицу