Моделирование динамики систем на основе цепи Маркова с дискретным временем

    Матрица Q размерности sxs определяет поведение процесса до выхода из множества невозвратных состояний.

    Матрица R размерности sx(n-s) определяет вероятности перехода из множества невозвратных состоянии в эргодическое множество.

    При возведении матрицы Р в степень  перемножаются блоки, указанные в (9), и произвольная степень канонической матрицы имеет вид 

    (10) 

    Рассмотрим  структуру матрицы R(k). Вычисляя последовательно степени матрицы Р с учетом (9), получим:

    R(1)=R;

    R(2) = QR(1)+ R(1)W =QR+RW

    R(3) = QR(2)+ R(2)W = Q²R + 2QRW + RW²;

    ….

         _k

    R(k+l)= ∑ C^l_kQ^k-lRW^l

                 ⁱ⁼⁰

    где C^l_k – биномиальные коэффициенты. В соответствии со сказанным выше, i-я строка матрицы R(k) содержит вероятности перехода системы во все состояния эргодического множества за k шагов при старте из состояния S_i ϵ Т.

    Если  цепь Маркова поглощающая, то W = I - единичная матрица размерности n-s, и все ее степени - также единичная матрица той же размерности. 
 
 

            Оценка  длительности пребывания системы во множестве  Т

    Рассмотрим  поведение цепи Маркова при росте числа шагов к. Из анализа структуры матрицы Р^к следует,  процесс, стартовав из некоторого состояния S_i, принадлежащего невозвратному множеству Т , на каждом шаге с вероятностями, определенными матрицей R, переходит в эргодическое множество . Через определенное число шагов процесс окажется в эргодическом множестве с вероятностью, как угодно близкой к единице.

    При моделировании реальных систем с  помощью конечных цепей Маркова  часто бывает необходимо оценивать  показатели продолжительности работы системы или трудоемкости процессов. Для этой цели нужно уметь рассчитывать число шагов, в течение которых процесс покидает множество Т («время жизни» процесса), а также «время жизни» отдельных состояний этого множества.

    Обозначим n_ij общее число моментов времени (тактов работы системы), проведенных процессом в состоянии S_i при условии, что он стартовал из состояния S_i (S_i,S_j ϵ T). Понятно что n_ij - случайная величина, принимающая целочисленные значения 0,1,2,... с соответствующими вероятностями, которые мы будем обозначать P_ij(1),...,P_ij(k),... . Таким образом P_ij(k)=P_r{n_ij=k}- вероятность того, что система за все «время жизни» процесса  находилась в состоянии S_i при старте из S_i, k раз. При этом

    ∞

    ∑P_ij(k)=1

    k=0

    Зная  распределение вероятностей P_ij(k),  можно вычислить все необходимые статистические характеристики процесса - математическое ожидание, Дисперсию и другие. Однако вычисление таких распределений в общем случае - достаточно сложная задача, поэтому мы ограничимся в данном разделе рассмотрением трех более простых практически важных задач:

• оценки вида функции распределения P_ij(k); 
• вычисления математического ожидания величин n_ij. т.е. M[n_ij] ^и средних значений трудоемкости процесса;
• вычисления дисперсий п_ij, т.е. D[n_ij] и среднеквадратичных  отклонений трудоемкости  процесса.

 
    

1. Оценим  вид, функции распределения р_ij(к) случайных величин n_ij. Обратимся к матрице.

    R(k)=||r_ij(k)||,

    S_i принадлежит невозвратному множеству S_j принадлежит эргодическому множеству.

    Элемент этой матрицы r_ij (к) представляет собой вероятность перехода в S_j принадлежит эргодическому множеству при старте из S_i  принадлежит невозвратному  множеству  за к шагов. Разность P_ij(k)=r_ij(k)-r_ij(k-1) есть вероятность перехода S_j принадлежит эргодическому множеству точно на к шаге при старте из S_i  принадлежит невозвратному  множеству. Эта разность всегда неотрицательна в силу структуры матрицы Р^к

    Задача  нахождения вероятностей распределения упрощается, если рассматривать переходы не между отельными состояниями, а между множествами Т и эргодическому множеством.  Граф Цепи Маркова примет вид, показанный на рисунке 3.5.

      

    

2. Переходя  к вычислению матожидания величины n_ij, начнем с изучения свойств матрицы Q^k, входящей в структуру P^k в формуле. Поскольку по определению все элементы матрицы Q P_ij <= 1, и

 

    s

    ∑ P_ij <= 1

    j=1

    в отличие от матрицы Р, для которой

    n

    ∑ P_ij = 1

    j=1 

    S_i, S_j ϵ т при больших к эта матрица стремится к нулевой, т.е. Q^k →Øпри к →∞. Здесь Ø_s-нулевая квадратная матрица s-го порядка.

    Существует  обратная матрица (I-Q)^-1, которая играет большую роль при изучении марковских процессов с матрицей переходных вероятностей вида. Эту матрицу называют фундаментальной и обозначают

                              ∞

    N = (I-Q)^-1 =∑ Qⁱ.

                      i=0 

    3.   Оценке среднего «времени жизни» состояний процесса, относящихся к невозвратному множеству.

    Обозначим, как и прежде, через n_ij общее число моментов времени, проводимых процессом в состоянии S_j при условии, что он начался из состояния S_i. Эта функция определена только для невозвратного множества, т.е. S_i, S_j  ϵ  Т.

    Можно показать, что матрица математических ожиданий чисел n_ij равная N, т.е.  ||M[n_ij] ||= N, где S_i S_j ϵ Т.

    5. Напомним, что i-я строка матрицы N определяет среднее число тактов пребывания марковского процесса в различных состояниях невозвратного множества при старте из S_i. Поэтому если нас интересует только одно конкретное начальное состояние, то вычисление всей матрицы N дает избыточную информацию. В этом случае вычисления можно упростить. 

    Формулу  N = (I - Q)^-1 можно переписать иначе: N (I-Q)= I

    6.   Рассмотрим теперь случай, когда система может стартовать из любого состояния S_i ϵ Т с заданной Вероятностью, т.е. вектор начальных состояний имеет вид

                                       s

    X[0]=[x⁰₁,_……….,x⁰_s],  ∑ x⁰ _i=1

                                       I=1

    где х _I ⁰ - вероятность того, что марковский процесс начнется из S _i.

    В этом случае величина N _j- среднее число тактов пребывания процесса в состоянии S _j ϵ Т - определяется взвешенной суммой элементов j-го столбца матрицы N:

                                        s

                                  N_j  ∑ n _ijX⁰ _i

                                       i=1

    7.   Зная среднее число пребываний процесса в невозвратном состоянии и трудоемкость каждого этапа, можно вычислить среднюю трудоемкость алгоритма в целом.

    Если  C₁,...,C_S - средние трудоемкости этапов, то при старте процесса из состояния S_i общая средняя трудоемкость вычислительного процесса равна

                                       s

                              C_∑i= ∑ n _ij*C_j=1

                                       i=1

    8.   Оценим дисперсию числа пребываний процесса в множестве невозвратных состояний М [n _ij].

    Этот  показатель характеризует степень  разброса величин n _ij относительно среднего.

    Второе  слагаемое в - это матрица, образованная из квадратов элементов матрицы N. Обозначим ее

    N_sq=||M²[n_ij]||

    Находим первое слагаемое обозначим его  N_dg. Для нахождения N_dg  обнулением всех элементов исходной матрицы (N)

    Для того что бы оценить среднеквадратичное  отклонение от среднего числа пребываний процесса в множестве невозвратных состояний D , где D=N(2Ndg-E)-N_sq

    В ряде случаев исследователя интересует не дисперсия, а среднеквадратичное отклонение числа пребываний процесса от среднего, которое вычисляется  по матричной формуле 

    σ=||σ_ij||

    Таким образом, матрица среднеквадратичных отклонений получается извлечением квадратного корня из каждого элемента матрицы D. 

          Исследование  динамики цепей Маркова при большом числе шагов

    В этом параграфе рассмотрен класс  задач, связанных с оценкой предельных вероятностей пребывания системы в состояниях эргодического множества. Такие задачи особенно важны, если цепь Маркова не содержит множества невозвратных состояний.

    Как было выяснено выше, динамика смены  состояний однородной цепи Маркова  определяется поведением матрицы Р^k при к = 1,2,.... Однако непосредственное применение формулы для определения переходных характеристик этого процесса, в частности, скорости сходимости к предельным вероятностям пребывания в различных состояниях при k→∞, неудобно.

    1. Для оценки скорости сходимости можно привести матрицу Р к диагональному виду с помощью линейного Преобразования. Предположим, что матрица Р имеет п собственных чисел ʎ_i ,..., ʎ_n. Тогда ее можно привести к виду:

    P = UɅU^-1 

    Ʌ=

 

    Где Ʌ - диагональная матрица, a матрица U составлена из собственных векторов матрицы Р так, что i-й столбец матрицы U является собственным вектором матрицы Р при собственном числе ʎ_i.