Математическая культура. Мациевский С.В. - 47 стр.

        1. Ассоциированный орграф цепи Маркова — это такой орграф, где
     каждое состояние Ei представлено соответствующей ему вершиной vi, а
     дуги из vi в vj проведены для тех и только тех вершин, для которых pij ≠ 0.
        Ассоциированный орграф задачи о пьянице приведен ниже.

v1               v2     v3         v4+        v5             v6
        Пример. Ниже приведена еще одна                          v1  v2
     матрица перехода
                         ⎛ 1 1/ 4 1/ 2 0 0 1/ 4 ⎞
     цепи Маркова и ее ⎜                                 ⎟
                             0    1    0   0    0    0
     ассоциированный ⎜                                   ⎟ v6                 v3
                         ⎜ 1 / 2 1 / 3 0 1 / 12 0 1 / 12 ⎟
     орграф.
                         ⎜ 0 0 0 0 1 0 ⎟
                         ⎜ 0 0 0 0 0 1 ⎟
                         ⎜ 0 0 0 1 0 0 ⎟
                         ⎝                               ⎠    v5    v6
        Теперь ясно, что в цепи Маркова из состояния Ei в состояние Ej можно
     попасть в том и только в том случае, если в ассоциированном орграфе су-
     ществует орцепь из vi в vj, и что наименьшее возможное время попадания
     равно длине кратчайшей из таких орцепей.
        2. Классификация. Цепь Маркова, в которой из любого состояния
     можно попасть в любое другое, неприводима. Цепь Маркова неприводима
     тогда и только тогда, когда ее ассоциированный орграф сильно связен.
        Упр. 10. Выше описаны две цепи Маркова. Они неприводимы? Почему?
        Различают те состояния, в которые продолжают возвращаться незави-
     симо от продолжительности процесса, и другие. Более точно: если началь-
     ное состояние есть Ei и вероятность возвращения в Ei на некотором более
     позднем шаге равна 1, то Ei возвратно, или рекуррентно; в противном
     случае состояние Ei невозвратно. Состояние, из которого нельзя попасть
     ни в какое другое, называется поглощающим.
        Пример. В задаче о пьянице состояния E1 и E6 возвратны, а все другие
     состояния невозвратны. Также эти состояния E1 и E6 поглощающие.
        Упр. 11. Какие состояния во 2-й цепи невозвратны, а какие поглощаю-
     щие?
        Состояние периодическое с периодом t (t >1), если в него можно вер-
     нуться только по истечению времени, кратного t; если такого t нет, то со-
     стояние непериодическое. Каждое состояние Ei, для которого pii ≠ 0, непе-
     риодическое. Поэтому каждое поглощающее состояние непериодическое.
        Пример. В задаче о пьянице все состояния непериодические.
        Упр. 12. Какой период имеет каждое состояние во 2-й цепи Маркова?
        Состояние цепи Маркова называется эргодическим, если оно одновре-
     менно возвратно и непериодично. Если любое состояние цепи Маркова
     эргодично, то она называется эргодической цепью. Эргодические цепи
     очень важны во многих отношениях.

                                         46