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

44                                                 Глава 2. Ориентированные графы


и потому обладает кольцевым свойством kABk ≤ kAkkBk и, следо-
вательно, свойством kAk k ≤ kAkk .1)
   Лемма 1. Если kAq k = θ < 1 для некоторого показателя q, то
Ak → 0 при k → ∞.
    В формулировке леммы и дальше сходимость последовательности
матриц понимается поэлементно: Ak → B означает, что (Ak )ij →
(B)ij для всех i, j.
    Д о к а з а т е л ь с т в о. Из равенства Ak = Alq Ar (0 ≤ r ≤ q − 1)
и кольцевого свойства следует, что kAk k ≤ θl kAr k. Если k → ∞, то
l → ∞ и обе части неравенства стремятся к 0. Тогда из определения
функции k · k следует, что Ak сходится к нулевой матрице. ¤
  Лемма 2. Если Ak → 0 при k → ∞, то матрица E − A обра-
тима.
    Д о к а з а т е л ь с т в о. Из условия леммы вытекает, что
собственные значения λ1 , . . . , λn матрицы A по модулю меньше еди-
ницы, следовательно, среди собственных значений 1 − λ1 , . . . , 1 − λn
матрицы E − A нет нулей, следовательно, эта матрица обратима. ¤
    Теорема 1. Пусть переходные вероятности поглощающей мар-
ковской системы заданы матрицами (4). Тогда предельные переход-
ные вероятности существуют и выражаются матричными равен-
ствами:

      µ             ¶       µ            ¶
           E   0                 E 0
lim        (k)          =                    , где Q(∞) = lim Q(k) = (E−R)−1 Q.
k→∞       Q    Rk               Q(∞) 0                     k→∞


    Д о к а з а т е л ь с т в о. Согласно предложению 3 §1 конец
максимального простого пути с началом в невозвратном состоянии
является поглощающим состоянием и, разумеется, единственно воз-
можное продолжение этого пути состоит в повторении этого состо-
яния. Поскольку длина простого пути не более n − 1, то имеется
положительная вероятность попадания за n − 1 шагов в множество
поглощающих состояний, в каком бы из невозвратных состояний ни
стартовала система. Другими словами, вероятность остаться в классе
невозвратных состояний после n − 1 шагов меньше единицы, то есть,
строчные суммы матрицы Rn−1 меньше единицы. Таким образом, для
матрицы Rn−1 выполнено условие леммы 1 и мы можем заключить,
что Rk → 0 nри k → ∞.
  1)
     O нормах см., например, Хорн Р., Джонсон Ч. Матричный анализ — М.:Мир,1989. Впрочем,
кольцевое свойство этой функции нетрудно доказать и непосредственно.