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

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


переходных вероятностей. Неотрицательная матрица P = (pij ) поряд-
ка n называется стохастической, если
                     n
                     X
                           pij = 1, i = 1, . . . , n.           (1)
                     j=1

   Упражнение 1. Докажите, что произведение стохастических
матриц и любая степень стохастической матрицы — стохастические
матрицы.
    Полезно следующее образное представление: по графу стохасти-
ческой матрицы блуждает частица, переходя из вершины i в вершину
j с вероятностью pij . Больше того, можно описать марковскую систе-
му без явного задания стохастической матрицы, с помощью стоха-
стического графа, то есть графа, каждой дуге i → j которого припи-
сано неотрицательное число pij , причём выполняются равенства (1).
    Пример 1. Марковские системы, определяемые стохастическими
матрицами
                 0 1 0 0 
        α β 0
       0 α β ,       β 0 α 0 
                     0 β 0 α  , (0 < α, β < 1, α + β = 1),
        β 0 α
                        0 0 1 0
описываются также стохастическими графами, изображёнными на
рис. 6 и 7.




                                  Рис. 6




                                  Рис. 7