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

Значения вероятностей р,,р2,р3,р4 предопределяют ход вычислительного процесса. Эти значения вычисляются следующим образом.

Трудоёмкость алгоритма определяет, в частности, среднее число обращений к файлам.

Следовательно, среднее число переходов из состояния S0 в inтояния S,,S2,S3 должно быть N,+N2+N3. Один раз процесс переходит в поглощающее состояние S4. Таким образом, вычислительный процесс должен выходить из состояния S0 в среднем

N = ∑Nh+1 раз. (7)

Значение ph определяет долю переходов в состояние Sh по отношению к всевозможным переходам из состояния S0 в состояния S1,...,S4. Эта доля равна в среднем Nh/N где Nh - среднее число переходов в состояние Sh.

 

Следовательно, рh = Nh/N, h=1,...,3, р4=1/N.

 

Тогда средняя трудоемкость этапов счета, выполняемых за одну реализацию алгоритма, составит

Сср = С0N, откуда С0 = СсрN.

Трудоемкость конечного, этапа вычислительного процесса представляет собой случайную величину со средним значением Ch, h = 0,1,...,n.

Величины Сср, Nh и Сh могут быть, определены экспериментально путем анализа протоколов функционирования вычислительной системы при многократном решении рассматриваемой задачи.

 

 

 

3. Классификация состояний цепей Маркова:

Введем классификацию состояний цепи Маркова. Множество всех состояний может быть разбито на непересекающиеся подмножества, или классы: невозвратные и эргодические. Их свойства определяются следующим образом. Если процесс покинул класс первого типа, он никогда в него не возвращается. Если процесс попал в класс состояний второго типа, то он никогда его не покидает. Невозвратное множества мы будем обозначать Т, а эргодическое - Ť. При этом их объединение = S, а пересечение – пустое множество. Если эргодическое множество содержи только одно состояние, то это состояние называется поглощающим. Для такого состояния S, элемент переходной матрицы pij должен быть равен 1, следовательно, все остальные элементы соответствующей строки равны 0. Цепь, все эргодические состояния которой являются поглощающими, называется поглощающей цепью.

Для цепи Маркова с N состояниями, в которой имеют® как невозвратные, так и эргодические множества, структура матрицы вероятностей переходов имеет канонический вид

 

P	s	s-n
s	Q	R
s-n	0	W

(9)

 

где s - количество состояний в невозвратном множестве;

n-s - количество состояний в эргодическом множестве.

Матрица W размерности (n-s)x(n-s) определяет динамику эргодических состояний. Поскольку из множества Ť невозможно выйти, то матрица 0 размерности sx(n-s) состоит из нулей.

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

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

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

 

Pᵏ	s	s-n
s	Qᵏ	R(k)
s-n	0	Wᵏ

(10)

 

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

R(1)=R;

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

R(3) = QR(2)+ R(2)W = Q2R + 2QRW + RW2;

….

         k

R{k+l)= ∑ ClkQk-lRWl

       i=0

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

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

 

4. Оценка длительности пребывания процесса в множестве невозвратных состояний:

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

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

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

∞

∑Pij(k)=1

k=0

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

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

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

R(k)=||rij(k)||,

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

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

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

 

 

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

s

∑ Pij <= 1

j=1

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

n

∑ Pij = 1

j=1

Si, Sj ϵ т при больших к эта матрица стремится к нулевой, т.е. Qk →Øпри к →∞. Здесь Øs-нулевая квадратная матрица s-го порядка.

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

                          ∞

N = (I-Q)-1 =∑ Qi.

                  i=0

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

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

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

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

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

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

                                   s

X[0]=[x01,……….,x0s],  ∑ x0 i=1

                                   I=1

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

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

                                

 

                                    s

                              Nj  ∑ n ijX0 i

                                   i=1

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

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

                                   s

                          C∑i= ∑ n ij*Cj=1

                                   I=1

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

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

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

Nsq=||M2[nij]||

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

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

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

σ=||σij||

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

 

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

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

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

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

P = UɅU-1

Ʌ=

ʎ1	….	0
….	….	….
0	….	ʎn

 

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

Напомним, что i-е собственное число матрицы Р ʎi есть i-и корень алгебраического уравнения

det(P- ʎI) = 0, 

и собственный вектор u, соответствующий собственному числу ʎi , есть решения линейного уравнения

Pui = ʎi uj

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