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

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

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

Обозначим п_ij общее число моментов времени (тактов работы системы), проведенных процессом в состоянии Sj при условии, что он стартовал из состояния S_i (Si,Sj € T). Понятно, что n_ij - случайная величина, принимающая целочисленные значения 0,1,2,... с соответствующими вероятностями, которые мы будем обозначать p_ij(l),...,p_iJ(k),... . Таким образом Р_ij{к)= Рi{n_ij=k} - вероятность того, что система за все «время жизни» процесса находилась в состоянии Sj при старте из Si, k раз. При этом

∞

∑Р_ij(k)=1. Зная распределение вероятностей можно вычислить все необходимые статистические

k=0

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

• оценки вида функции распределения _ij(k);

• вычисления математического ожидания величин п_ij, т.е. M n_ij и средних значений трудоемкости процесса;

• вычисления дисперсий п_ij, т.е. Dn_ij среднеквадратичных отклонений трудоемкости процесса.

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

R(k) = ||r_ij(k)||, S_i  T, S_j Ť.

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

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

Обозначим вероятность перехода между множествами T и Ť при старте из S_l T за один шаг

где r_ij - элемент матрицы R (3.9); q_i =l-r, - вероятность того, что процесс останется в Т.

Для рассматриваемой системы матрица переходных вероятностей имеет вид

и для нее по формуле (3.11) нетрудно подсчитать вероятности перехода из T в Ť за k шагов и на k -м шаге.

Можно убедиться в том, что p_j(k) = r_iq_i^k-1 представляет собой функцию распределения случайной величины n_i.

В самом деле, все _i(k)0, кроме того, воспользовавшись формулой для суммы членов геометрической прогрессии, получим:

Полученное распределение носит название показательного. График этой функции имеет вид, показанный на рисунке 3.6.

Из графика видно, что наиболее вероятны малые значения п_i ,а с ростом числа шагов вероятность _i(k) монотонно убывает.

Математическое ожидание и дисперсия числа пребываний процесса в множестве Т определяется по известным формулам (промежуточные выкладки опущены):

Вернемся к случайным величинам п_ij. Их функции распределения представляют собой аналоги показательного распределения, однако вычисляются в общем случае достаточно сложно. Что касается матожиданий и дисперсий этих величин, то для их вычисления, как мы увидим в следующих разделах, не нужно знать функции распределения.

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

S n

∑p_ij ≤ 1(в отличие от матрицы Р, для которой ∑p_ij = 1 S_i,S_j  Т, то при больших k эта матрица

j=1 j=1

стремится к нулевой, т.е. Q^k —> Ø_S при k —> ∞ ). Здесь Ø_S - нулевая квадратная матрица 5-го порядка.

Для дальнейшего нам понадобится формула, оценивающая матрицу (I - Q)^-1. Рассмотрим тождество

Матрица (I-Q) неособенная, т.е. det(I-Q)≠0, в чем легко убедиться.

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

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

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

Можно показать, что матрица математических ожиданий чисел n_ij равна N, т.е.

Для того, чтобы в этом убедиться, введем вспомогательную переменную u^k_ij, которая принимает единичное значение, если процесс, стартовав при t = t₀ из S=S_i оказывается при t = t_k в S = S_j, т.е.

1 , если S(t_k)=S_J | S(t₀)=S_i ,

u_i^k_j =

0 в противном случае.

Вероятность того, что u_i^k_j = 1, обозначим р_i^(k)_j .

∞

Легко видеть, что n_ij =∑ u_i^k_j .

k=0

Оценим теперь матожидание матрицы, образованной элементами п_ij:

Здесь р_i^(k)_j - элемент Р^k, S_i , S _j  T.

Таким образом, среднее число шагов, которое проводит процесс в невозвратном состоянии, S _j, начавшись в S_i , всегда конечно и определяется i-й строкой матрицы (I - Q)^-1.

4. Рассмотрим другой вывод формулы (3.14), который понадобится в дальнейшем.

Величина п_ij на каждом временном шаге k может быть определена соотношением

Первая сумма в написанном выражении относится к случаю, когда состояния S_i, и Sj совпадают, кроме того, процесс на следующем шаге уходит в эргодическое множество Ť. Вторая сумма представляет собой вклад в величину п_ij за счет перехода в j-е состояние из i-го через промежуточные l-e состояния, а слагаемое δij - добавление 1, если S_i = S_j .

Раскроем скобки во втором слагаемом и учтем, что

Тогда выражение для п_ij^(k+1) примет вид

Применив к этой формуле операцию математической ожидания и рассматривая предельный случай (k —>∞ и n_kj^(k) —> n_kj), получим:

Перейдем к матрицам:

откуда N = (I - Q)^-1.

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

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

О тсюда, если представляет интерес только начальное состояние S_i T , достаточно рассмотреть i-ю строку уравнения (3.16) при этом величины n_ij определятся системой уравнений:

В правой части системы уравнений единица стоит в i-й строке.

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

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

В этом случае величина N₁. - среднее число тактов пребывания процесса в состоянии S_l  T - определяется взвешенной суммой элементов j-го столбца матрицы N:

Пример. Вернемся к рассмотренному ранее примеру. В нашей системе имеется одно поглощающее состояние, которое соответствует ожиданию сигнала оператора с клавиатуры,

остальные состояния - эргодические. Представим матрицу в виде

Вычислим

В ыпишем матрицу вероятностей переходов для множества Т невозвратных состояний

Здесь det{l -Q)=l-p₁~p₂- p₃ = р₄.

Матрица N показывает среднее число пребываний процесса в каждом из состояний S₀,S_l:S_?,S₃. Если процесс начинается с S_o, то, как видно по первой строке матрицы N,

1

в состоянии S_o процесс был в среднем — раз;

Р₄

Р₁

в состоянии S, процесс был в среднем —- раз;

Р₄

Р₂

в состоянии S₂ процесс был в среднем —— раз;

Р₄

Р₃

в состоянии S₃ процесс был в среднем —— раз.

Р₄

Например,

пусть р₁ =0.8, р₂ = 0.05, p₃ =0.1,p₄ =0.05.

Тогда в состоянии S₀ процесс был в среднем п₁₁ = 20 раз;

в состоянии S₁ процесс был в среднем п₁₂ = 16 раз;

в состоянии S₂ процесс был в среднем п₁₃ = 1 раз;

в состоянии S₃ процесс был в среднем п₁₄ - 2 раза.

Нетрудно проверить, что п₁₂ +п₁₃ +п₁₄ = 19, плюс система 1 раз перешла в состояние S₄, таким образом п₁₁ = 19 +1 = 20.

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

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

Пусть C₁ = 0.5с - среднее время работы процессора;

C₂= 0.75с - среднее время работы НЖМД;

С₃ = 2.5с - среднее время работы НГМД;

С₄=30с - среднее время работы принтера.

Тогда по формуле (1.19) общая средняя трудоемкость (продолжительность) одного цикла работы ВС при старте из состояния S_o составит

С_1о =0.5 -20 + 0.75 -16 + 2.5 -1 + 30- 2- 84.5с.

8. Оценим теперь дисперсию числа пребываний процесса в множестве невозвратных состояний М  n_ij .

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

В соответствии с определением дисперсии случайной величины n_ij имеем:

Перейдем к матрицам:

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

Вычислим теперь первое слагаемое в (3.20). Оно представляет собой матрицу, составленную из матожиданий случайной величины п_ij². Для вычисления М\п₁²\ воспользуемся

приемом, который был применен в п. 3 настоящего параграфа, для вычисления M[n_jJ j.

Рассматривая предельный случай (к —>∞), имеем

Здесь первое слагаемое определяет вклад в величину п₁². начального состояния, когда процесс, начавшись в S_i  Т , сразу же перешел в S_k Ť . Второе слагаемое определяет вклад в величину n_ij за счет перехода в Sj из Si через промежуточное S_kT

Добавка δ_kj. в круглой скобке относится к случаю, когда процесс стартовал из Sj  T.

Раскроем скобки во втором слагаемом (3.22) и, проделав элементарные преобразования, получим:

В последнем преобразовании использована следующая цепочка тождеств:

где (QN)_dg - матрица, полученная обнулением всех элементов исходной матрицы вне главной диагонали (благодаря множителю δ_ij в последнем слагаемом (3.23)). Далее проделаем некоторые преобразования над матрицами. Перенося неизвестную матрицу ||M[п²_kj|| в левую часть равенства, имеем:

т.к. I_dg=I.

Возвращаясь к (3.20) с учетом . (3.21), получим окончательно:

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

Эта матрица показывает дисперсию числа пребываний процесса в каждом из состояний. Мы видим, что вне зависимости от стартового состояния дисперсии числа пребываний в различных состояниях равны:

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

или в матричной форме

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

Пример. Для тех же численных значений вероятностей что рассматривались ранее

Располагая матрицей а, можно вычислить среднеквадратичное отклонение трудоемкости вычислительного процесса от среднего:

Для рассматриваемого примера