Модели вычислительных систем, основанные на концепции состояния - цепи Маркова

Для цепи Маркова с 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 = 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, и все ее степени - также единичная матрица той же размерности.

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

Рассмотрим поведение цепи Маркова  при росте числа шагов к. Из анализа структуры матрицы Р^к следует,  процесс, стартовав из некоторого состояния 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.

r_i

Старт из S_i

1

 

Ť

Т

1-r_i=q_i

2.Переходя к вычислению матожидания величины n_ij, начнем с изучения свойств матрицы Q^k, входящей в структуру P^k в формуле. Поскольку по определению все элементы матрицы QP_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_iS_j Т

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

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

5. Рассмотрим теперь случай, когда система может стартовать из любого состояния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

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

C_∑i= ∑ n_ij*C_j=1

I=1

7. Оценим дисперсию числа пребываний  процесса в множестве невозвратных состояний М [n_ij].Этот показатель характеризует степень разброса величин n_ij относительно среднего.

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

N_sq=||M²[n_ij]||

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

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

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

σ=||σ_ij||

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

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

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

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

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

P = UɅU^-1

Ʌ=

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

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

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

det(P- ʎI) = 0, 

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

Преобразование удобно тем, что  при возведении в степень матрицы  фактически возводится в степень  только диагональная матрица P^k=(UɅU)^k=UɅ^kU^-1

Причем Ʌ ^k

ʎk1	….	0
….	….	….
0	….	ʎkn

 

Таким образом, динамику изменения  матрицы Р^к легко оценить по поведению ʎ_i, i= 1,...,п.

Мы уже упоминали, что матрица Р, определяющая однородную цепь Маркова, является стохастической матрицей. Особенностью этой матрицы является то, что ее максимальное собственное число равно 1, и ему соответствует собственный вектор, составленный из единиц: [l,l,...l].

2. При анализе цепей Маркова, имеющих состояния, относящиеся к эргодическому множеству, типовой задачей является вычисление предельного вектора вероятностей нахождения процесса в каждом из состояний

X_пред⁼limX(t_k) k→∞.

Напомним, что вектор состоянияX{t_k) определяете» формулой:

X(t_k)=X(t₀)P^k а к-я степень канонической стохастической матрицы имеет структуру: P^k=

Qk	R(k)
0	Wk

 

При большом числе шагов, как  мы установили, матрица Q^k-»0, а матрицыW^k иR(k) стремятся к некоторым предельнымW^k -»W_nред, R(k) -»R_пред. Таким образом, в предельном случае: Р_пред=limP^k , k→∞, =

 

0	Rпред
0	Wпред

Матрицу Р_пред можно найти описанным выше способом,

выполнив спектральное разложение матрицы Р и положив k→∞. Тогда

X_пред= X(t₀)*P_пред

Однако существует более простой  способ определении Х_пред. Он основан на том, что при большом числе шагов вектор X(t_k) сходится к Х_пред . Из соотношения

X(t_k+1) = X{t_k)*P, приk→∞,, следует, что

X(t_k) -»X{t_k+])-»X_пред

и

X_пред=X_пред*P

Решая уравнение относительно неизвестных x1_пред,x2_пред,   …, xn_пред   при дополнительном условии

Σx_{i пред}=1, при i→∞,.Получим вектор X_пред.