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

Обозначим 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 в формуле. Поскольку по определению все элементы матрицы 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.3 Исследование динамики цепей Маркова

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

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

 

 

 

2. Практический раздел

2.1 Граф состояний и  матрица вероятностей переходов

 

 

Рисунок 2.1– Граф состояний.

 

Таблица 2.1 – Матрица вероятностей переходов.

	1	2	3	4	5	6	7	8
1	1	1	3	5	0	0	0	0
2	0	0	6	4	0	0	0	0
3	6	0	0	0	4	0	0	0
4	0	0	3	2	0	1	0	5
5	0	0	0	0	3	4	3	0
6	0	0	0	0	8	2	0	0
7	0	0	0	0	0	6	4	0
8	0	0	0	0	0	0	0	10

 

Таблица 2.2 – Начальный вектор.

1

0

0

0

0

0

0

0

 

 

 

 

2.2 Таблицы векторов X(t)

Таблица 2.3 – Векторы Х(t), рассчитанные теоретически.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Далее представлены значения, просчитанные практически при значениях N равных 100, 1000, 2000 (таблицы 2.4 – 2.18) и их сравнительная характеристика с использованием графиков (рисунки 2.2 – 2.16).

Таблица 2.4

Шаг 1
N=100	0,10077	0,09603	0,30574	0,49744	0	0	0	0
N=1000	0,10096	0,09617	0,30506	0,49779	0	0	0	0
N=2000	0,10122	0,09632	0,30406	0,49838	0	0	0	0
Теоретически	0,1	0,1	0,3	0,5	0	0	0	0