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

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


   Предположим, что в начальный момент времени система нахо-
дится в состоянии i. В рамках описываемой модели произведение
                                      pil1 pl1 l2 . . . plk−1 j
понимается как вероятность того, что система (частица), находясь
вначале в состоянии (вершине) i, пройдёт путь i, l1 , . . . , lk−1 , j. Тогда
число                   X
                             pil1 pl1 l2 . . . plk−1 j ,                  (2)
                             l1 , . . . ,lk−1

где суммирование производится по всевозможным (i, j)-путям длины
k, равно вероятности перехода системы из состояния i в состояние j
за k шагов.
    Случайные процессы такого типа впервые изучались А.А. Марко-
вым в начале 20-го века и по традиции называются цепями Маркова.1)
    Цепь Маркова определяется, стало быть, если фиксировано на-
чальное состояние системы. Можно сказать, что марковская система
есть совокупность марковских цепей, которые получаются при раз-
личном выборе начального состояния системы.
    Докажите простой, но решающий для применимости стохастиче-
ских матриц в теории цепей Маркова факт:
   Предложение 1. Вероятность (2) перехода из состояния i в
                              (k)
состояние j за k шагов равна pij , то есть, равна (ij)-элементу
матрицы P k .
    Иногда бывает нужно знать вероятность перехода за k шагов из
состояния i в какое-либо из состояний множества α. Из предложе-
                                         P     (k)
ния 1 вытекает, что эта вероятность равна j∈α pij .
    Мы рассмотрим, в качестве приложения теории графов, одну из
основных задач теории цепей Маркова — задачу об асимптотическом
                                     (k)
поведении переходных вероятностей pij при k → ∞. Для двух типов
                                                                                       (k)
марковских систем будет доказано существование пределов lim pij
                                                                                 k→∞
для любых состояний i, j. Другими словами, будет доказано, что по-
следовательность P k , k = 1, 2, . . . поэлементно сходится к некоторой
предельной матрице P ∞ (очевидно, стохастической).
   Соответственно нашему подходу состояния марковской системы
отождествляются с вершинами графа этой системы, понятия компо-
ненты, циклического класса и т.п. переносятся на состояния системы.
  1)
     Для углублённого знакомства см., например, Кемени Дж., Снелл Дж. Конечные цепи Мар-
кова. — М.: Наука, 1970, или Ширяев А.Н. Вероятность (в 2-х кн.). — М.: МЦНМО, 2004.