Предельные вероятности состояний

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

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

Определение 2. Пусть марковский процесс характеризуется ве­роятностями перехода из состояния i в состояние j за время t

p_ij(t) (0£i£n; 0£j£n).

Процесс называется транзитивным, если существует такое t>0, что p_ij(t)>0 (0£i£n; 0£j£n). Из определений 1 и 2 следует, что процессы в марковских цепях с эргодическим свойством являются транзитивными.

Теорема Маркова [4]. Для любого транзитивного марковского процесса предел  существует и не зависит от начального состояния i.

 

Это означает, что при t®¥ в системе устанавливается неко­торый предельный стационарный режим, характеризующийся постоян­ной, не зависящей от времени, вероятностью каждого из состояний системы. При этом данная вероятность представляет собой среднее относительное время пребывания системы в данном состоянии. Это значит, что если время работы всей системы 100 ч, а вероятность состояния S₁ равна p₁=0,15, то система будет находиться в состоянии S₁ в среднем 15 ч.

Пределы, к которым стремятся вероятности каждого из состоя­ний марковской цепи с эргодическим свойством при t®¥, называ­ются предельными вероятностями. При рассмотрении СМО мы будем иметь дело только с эргодическими марковскими цепями. Пусть V - некоторое подмножество множества состояний системы S, а V’ - его дополнение до S. Если множество V обладает эргодическим свойс­твом и ни из одного состояния множества V нельзя перейти ни в од­но из состояний множества V’, то множество называется замкнутым или эргодическим множеством. Эргодические системы состоят из од­ного единственного эргодического множества (S=V, V’=Æ) и называются поэтому неразложимыми. Если в системе S множество V'¹Æ или в этой системе можно выделить несколько эргодических множеств S = V₁ÈV₂È…ÈV_n, то такая система называется разложимой. Примеры таких систем приведены на рис.1.3.

На рис.1.3,а представлена сис­тема с двумя эргодическими множест­вами V₁=(S₂,S₃,S₄) и V₂(S₅,S₆). На рис.1.3,б эргодическое множество состоит лишь из одного состояния (S₄). Если эргодическое множест­во состоит лишь из одного состоя­ния, то это состояние называется поглощающим, так как попав в не­го однажды, процесс остается нав­сегда в поглощающем состоянии. Ха­рактерная особенность графа состо­яний неразложимой эргодической мар­ковской системы заключается в том, что каждой вершине этого графа ин­цидентны дуги как с положительной, так и с отрицательной инцидент­ностью (т.е. у каждой вершины име­ются дуги, направленные как к вер­шине, так и от нее, см., например, рис. 1.1 и 1.2).

 

                  а                  б

                         Рис.1.3  

 

Вычисление предельных вероят­ностей состояний для таких систем упрощается в связи с тем, что, поскольку все эти вероятности яв­ляются постоянными величинами, то их производные по времени рав­ны 0 (dp_i/dt=0 для всех i). Поэтому левые части системы уравнений Колмогорова (1.7) приравниваются нулю и она превращается в систе­му линейных алгебраических уравнений

             .                                     (1.8)

Нетривиальное решение системы (1.8) может быть получено только в случае вырожденности матрицы L. Выше было доказано, что матрица плотностей вероятностей L является вырожденной. Система (1.8) без одного из своих уравнений дополняется условием нормировки

                                                 (1.9)

 

Соотношения (1.8) и (1.9) позволяют определить предельные вероят­ности состояний. Поскольку часть слагаемых, соответствующая дугам с отрицательной инцидентностью, положительна, а другая часть, со­ответствующая дугам с положительной инцидентностью, отрицательна, то каждое уравнение системы (1.8) может быть составлено с учетом мнемонического правила: для каждого состояния сумма членов, соот­ветствующих входящим дугам, равна сумме членов, соответствующих выходящим дугам.

Пример. Для системы, изображенной на рис.1.2, из уравнений Колмогорова (1.7) следует

(l₁₂+l₁₃)p₁=l₄₁p₄ (l₄₁+l₄₅)p₄=l₃₄p₃

 l₂₅p₁=l₁₂p₁+l₃₂p₃     l₅₃p₃=l₅₂p₂+l₄₅p₄

(l₃₂+l₃₄)p₄=l₁₃p₁+l₅₃p₅                                           (1.10)

Для решения (1.10) нужно исключить любое из первых пяти уравнений (например, пятое, как содержащее наибольшее число членов).

Предельные вероятности состояний используются в ТМО значи­тельно чаще, чем решения уравнений Колмогорова, причем, зная ре­шение системы уравнений Колмогорова, можно определить момент окончания переходного процесса изменения вероятностей состояний во времени. Это дает возможность рассчитать, промежуток времени начиная от включения системы в работу, по истечении которого ве­роятности состояний достигнут своих предельных значений и будут справедливы оценки, использующие эти значения. В заключение этого параграфа рассмотрим один частный, но практически очень важный класс марковских процессов, широко применяемых при исследовании СМО. Это - процессы "размножения и гибели". К ним относятся мар­ковские цепи, представимые размеченным графом, который состоит из вытянутой цепочки состояний, изображенной на рис.1.4.

 

 

Рис.1.4

 

Матрица плотностей вероятностей переходов такой системы яв­ляется якобиевой (тридиагональной):

 

Рассматривая начальное состояние S₀, получим в соответствии с (1.8)

        l₀₁p₀=l₁₀p₁                                           (1.11)

Для состояния S₁ имеем

        l₀₁p₀+l₂₁p₂=l₁₀p₁+l₁₂p₁                                                  (1.12)

Вычитая из (1.12) равенство (1.11), получим

        l₂₁p₂ = l₁₂p₁                                          (1.13)

Продолжая этот процесс до n-гo состояния включительно, получим

        l_n,n-1p_n=l_n-1,np_n-1                                       

Из (1.11) теперь можно выразить p₁ через р₀:

           p₁=p₀(l₀₁/l₁₀)                                     (1.14)

Подставляя (1.14) в (1.13), получим

           p₂=p₀(l₀₁l₁₂/l₁₀l₂₁)  

Очевидно, что для произвольного k (1£k£n) будет справедливо вы­ражение

                      .           (1.15)

 

В соответствии с (1.15) и размеченным графом состояний, представленным на рис.1.4, можно сформулировать правило, с по­мощью которого можно выразить предельные вероятности состояний процесса "размножения и гибели" через вероятность начального сос­тояния р₀. Это правило гласит: вероятность произвольного состоя­ния p_k (l£k£n) равна вероятности начального состояния р₀, умно­женной на дробь, числитель которой равен произведению плотностей вероятностей перехода для дуг, переводящих состояние системы сле­ва направо, а знаменатель - произведение плотностей вероятностей перехода справа налево от начального до k-гo состояний включи­тельно.

Вероятность р₀ находится из условия нормировки  и выражений (1.15) следующим образом:  

                   (1.16)

 

Выражения (1.15) и (1.16) полностью определяют предельные вероят­ности процесса "размножения и гибели".

 

Простейший поток событий

Цепи Маркова с непрерывным временем являются математическими моделями СМО. Для анализа СМО необходимо также иметь математичес­кие модели входных потоков заявок на обслуживание. Эти математи­ческие модели представляют собой потоки события, являющиеся от­дельным классом случайных процессов. Потоком событий называется последовательность однородных событий, следующих одно за другим в случайные моменты времени [1]. Этот поток количественно может быть охарактеризован числом событий x(t), имевших место в течение определенного промежутка времени (0,t). Тогда случайный поток со­бытий можно определить как случайный процесс x(t) (t³0), в кото­ром функция x(t) является неубывающей функцией времени, способной принимать лишь целые неотрицательные значения. Иными словами, график функции x(t) является ступенчатой кривой с постоянной вы­сотой ступеньки, равной единице, причем ширина ступеньки - слу­чайная величина (см.рис.1.5,а). Примерами таких потоков могут служить: поток вызовов на АТС, поток запросов в вычислительный центр коллективного пользования и т.п. Моменты появления событий можно отобразить точками на временной оси, поэтому поток событий часто представляется и как последовательность таких точек (см.рис.1.5,б). Поток событий называется регулярным, если события следуют одно за другим через одинаковые, строго фиксированные промежутки времени.

 

Рис.1.5

 

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

Простейшими называются потоки, обладающие следующими тремя свойствами: стационарностью, ординарностью и отсутствием последействия. Рассмотрим эти свойства подробнее.

1. Поток событий называется стационарным, если вероятность p_k(l) того, что за отрезок времени t произойдет k событий, зави­сит только от его длины t и не зависит от его расположения на временной оси (см.рис.1.5), т.е. p_k(t’,t’+t)=p_k(t). Из определения однородной марковской цепи следует, что стационар­ность - это однородность потока по времени.

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

 

3. Поток событий называется потоком без последействия, если вероятность попадания событий на некоторый участок временной оси не зависит от того, сколько событий попало на другие участки. Иными словами, условная вероятность наступления k событий за про­межуток времени (t’,t’+t), вычисленная при любом условии чередо­вания событий до момента t', равна безусловной вероятности p_k(t) того же события, т.е.

p[(t’,t’+t),k/(t",t"+t),m]=p_k(t),tÇt_k=Æ, t"<t’.

На практике редко встречаются потоки, удовлетворяющие всем трем допущениям одновременно. Например, поток вызовов в АТС в дневные часы более интенсивен, чем в ночные. Тем не менее, рассматривая работу АТС в периоды с 12 до 13 ч дня и с 2 до 3 ч ночи, поток вызовов на этих более коротких промежутках можно с высокой степенью точности считать стационарным. Этот пример говорит о том, что в большом числе случаев можно ввести определенные упрощения, вытекающие из принципов работы конкретных реальных систем и позволяющие проводить исследование реальных СМО путем замены их входных потоков простейшими. Это дает возможность существенно упростить математический аппарат исследования СМО.

Указанные свойства простейших потоков позволяют просто опре­делить их распределение вероятностей p_k(t), т.е. вероятность того, что за отрезок времени длиной t произойдет k событий. Прежде всего следует оговорить, что мы будем рассматривать только те по­токи, в которых за конечный промежуток времени t с вероятностью 1 будет происходить лишь конечное число событий, т.е.

                                                   (1.17)

Тогда простейший поток можно представить цепью Маркова, изобра­женной на рис.1.6,а, где состояние S₀ означает отсутствие собы­тий в интервале t, S₁ - появление одного события за время t, S₂ - появление двух событий за время t,…, S_k - появление k событий за время t. Применив правила составления уравнений Колмогорова для такого размеченного графа состояний, получим:

dp₀(t)/dt = - lp₀(t),

dp₁(t)/dt = - lp₁(t)+lp₀(t)                                     (1.18)

…

dp_k(t)/dt = - lp_k(t)+lp_k-1

_…

с начальными условиями: р₀(0)=1, р₁(0)=0,…, р_k=0,…

Плотность вероятности перехода l, которая участвует в уравнениях (1.18), является в данном случае интенсивностью потока собы­тий. Под интенсивностью потока понимается среднее по ансамблю реализаций число событий в единицу времени. Вероятность перехода р_i,i+1(t,t+Dt) равна веро­ятности появления одного события в интервале от t до t+Dt, поскольку ординар­ность потока исключает появление большего числа событий в этом интервале. Очевидно, что эта вероятность равна среднему числу по­явлений одного события за время Dt. Тогда с учетом определения (1.2) можно сделать вывод, что плотность вероятности перехода для марковской цепи (рис.1.6) равна интенсивности простейшего потока. В стационарном простейшем потоке l = const, тогда как в не­стационарном потоке интенсивность зависит от времени: l = l(t).

 

             а                      б

                       Рис.1.6

 

Решить систему (1.18) можно различными методами. Одним из наиболее простых является метод производящих функций. Производя­щей функцией распределения вероятностей состояний p_k(t) называет­ся ряд

                    ,                 (1.19)

где |z|£l.

С учетом (1.17) ряд (1.19) сходится абсолютно. Умножая на z^k все уравнения (1.18) и суммируя по k от 0 до ¥, получим:

         

откуда следует

        dln Ф/dt = l(z-1)                                (1.20)

Интегрируя (1.20), получим

        ln Ф(t,z) – ln Ф(0,z) = l(z-1)t

С учетом начальных условий системы (1.18) можно написать

        Ф(0,z) = p₀(0) = 1, ln Ф(0,z) = 0.

Следовательно,

Подставив вместо Ф(t,z) выражение (1.19), получим окончательно

                                           (1.21)

 

Распределение (1.21) является известным распределением Пуассона, поэтому простейшие потоки называются пуассоновскими.

Важнейшей характеристикой любого потока является закон рас­пределения интервала времени Т между двумя соседними событиями в потоке (см.рис.1.6,б). Определим этот закон для пуассоновских потоков. Вначале рассмотрим интегральный закон распределения F(t)=p(t>T), т.е. вероятность того, что случайная величина Т при­мет значение, меньшее чем t. Для этого необходимо определить ве­роятность того, что в интервал времени t, отсчитываемый от момента t₀ появления некоторого события, попадет еще хотя бы одно событие (см.рис.1.6,б). Эту вероятность можно определить, зная вероятность отсутствия событий в интервале t, равную вероятности p₀(t) состояния S₀ на графе рис.1.6, а. В соответствии с (1.21)

                     p₀(t)=e^-lt

откуда следует

                F(t)=p(t>T)=1-e^-lt, t>0     .         (1.22)

Дифференцируя (1.22) по времени, получим искомый закон распреде­ления

                                          (1.23)

Закон распределения (1.4.9) называется показательным (экспоненци­альным). Определим первые два момента показательного распределе­ния:

- математическое ожидание

                                       (1.24)

- дисперсия

                                           (1.25)

Интегрируя (1.24) и (1.25) по частям, получим

 

              .    (1.26)

 

Из (1.26) следует, что для показательного распределения математи­ческое ожидание и среднеквадратичное отклонение равны друг другу. Кроме того из (1.26) следует, что в простейшем потоке среднее время между двумя соседними событиями равно обратной величине ин­тенсивности потока.

Определим теперь вероятность попадания одного события в простейшем потоке на элементарный участок временной оси (см.рис.1.6,б). Так же, как и в предыдущем случае, эта вероятность

P₁(Dt) = 1 – P₀(t) = 1 - e^-lDt. 

Разлагая e^-lDt в ряд по степеням lDt и ограничиваясь только первой степенью (в силу малости Dt), получим

             P₁(Dt) = lDt.                             (1.27)

Выражение в правой части (1.27) называется элементом вероятности появления события в простейшем потоке.

 

Потоки Пальма и Эрланга

Потоки Пальма или потоки с ограниченным последействием явля­ются обобщением потоков элементарных событий.

Определение. Потоком Пальма называется поток, в котором промежутки времени между двумя соседними событиями представляют собой независимые случайные величины, распределенные по одному и тому же закону.

Частным случаем потоков Пальма являются простейшие потоки, в которых интервалы между соседними событиями распределены по пока­зательному закону. Если интервалы между событиями подчиняются гауссовскому распределению, то такие потоки называются нормальными.

Очевидно, что для регулярного потока закон распределения вы­ражается d-функцией.

В теории массового обслуживания широко используются потоки Эрланга. Они образуются из простейших потоков путем применения к ним операции "просеивания". Эта операция заключается в том, что из простейшего потока удаляется некоторое число точек по опреде­ленному правилу.

Если удаляются точки через одну, т.е. остается каждая 2-я точка, то поток Эрланга называется потоком 2-го порядка (Э₂). Ес­ли удаляются две точки подряд и остается каждая 3-я точка, то по­лучается поток Эрланга 3-го порядка (Э₃). Если удаляются (k-l) точек подряд, а остается каждая k-я точка, то поток Эрланга на­зывается потоком k-го порядка (Э_к). Очевидно, что простейший по­ток является потоком Эрланга 1-го порядка.

Определим закон распределения f_k(t) интервалов Т₁ для пото­ка Э_k. Для этого необходимо найти вероятность появления события в потоке Э_k на элементарном участке (t,t+Dt), что будет иметь место в том случае, когда конец интервала Т = ST_i окажется в пределах элементарного участка: t £ ST_i £ t+dt. Вероятность этого события равна f_k(t)dt. С другой стороны, эта вероятность равна произведению вероятностей двух событий:

- на участок длиной t должна попасть k-l точка простейшего потока;

- последняя (k-я) точка должна попасть на участок (t,t+Dt).

Вероятность первого события можно определить в соответствии с пуассоновским законом (1.21)

.

Вероятность второго события равна, по определению, элементу веро­ятности появления события в простейшем потоке (1.27), т.е. ldt. Перемножая эти вероятности, получим

 

откуда следует

                  .           (1.28)

 

Закон распределения (1.28) называется законом Эрланга. При k=1 закон Эрланга вырождается в показательное распределение.

Каждый интервал в потоке Э_k равен: Т = ST_i, где T_i - неза­висимые случайные величины, распределенные по показательному за­кону с первыми двумя моментами, определяемыми выражениями (1.26). Применяя теоремы о сложении математических ожиданий и дисперсий для суммы независимых случайных величин, получим

                              (1.29)

 

Целесообразно выразить параметры непосредственно через интенсив­ность потока Эрланга Э_k. Очевидно, что L_k = l/k, l = kL_k. Пред­ставив таким образом интенсивность исходного пуассоновского пото­ка, получим в соответствии с (1.29):

 

                           (1.30)

 

Сделав соответствующую подстановку в (1.28), определим закон Эр­ланга в виде

 

 

Из (1.30) следует, что, устремляя порядок k потока Эрланга к бесконечности, получим m_t = 1/L_k; D_t ® 0. Это означает, что случай­ная величина Т приближается к постоянной величине, равной матема­тическому ожиданию. При этом поток Эрланга вырождается в регуляр­ный поток.

Отмеченное свойство потоков Эрланга и является причиной, по которой они широко используются для аппроксимации реальных пото­ков, изменяя k от 1 (полное отсутствие последействий, пуассоновский поток) до ¥ (жесткая связь между моментами появления событий, регулярный поток), можно получить широкий спектр различных случа­ев, располагающихся по своим свойствам между этими двумя крайними полюсами.

Рассмотрим (без доказательств) два типичных преобразования, выполняемых над случайными потоками: суммирование потоков и раз­режение потоков,

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

1) Для суммарного потока существует предельная теорема: сум­ма независимых, ординарных и стационарных случайных потоков схо­дится к пуассоновскому потоку при неограниченном увеличении числа слагаемых [3]. Интенсивности суммируемых потоков должны при этом быть соизмеримы. Эта теорема аналогична центральной предельной теореме для случайных величин.

2) При сложении n как стационарных, так и нестационарных по­токов интенсивность суммарного потока равна сумме интенсивностей потоков-слагаемых и выражается соотношением

                                            (1.31)

 

Разреженным (редеющим) потоком называется поток, получающий­ся из исходного потока путем случайного удаления из него событий с постоянной вероятностью q. Иными словами, событие исходного по­тока остается в разреженном с вероятностью р = 1-q.

Следует различать операцию детерминированного "просеивания", с помощью которой получаются потоки Эрланга, и операцию случайно­го разрежения.

В качестве примера редеющего потока можно привести поток не­обслуженных заявок на выходе СМО с отказами (например, поток са­молетов, прорвавшихся через систему ПВО, которая сбивает случай­ное число этих самолетов). Отметим основные свойства редеющих по­токов [3].

1) Для редеющих потоков существует предельная теорема: если последовательно разрежать исходный стационарный ординарный поток Пальма с вероятностями р₁,р₂,…,р_n, то многократно разреженный поток стремится к пуассоновскому при n®¥.

2) Интенсивность разреженного потока l_p равна интенсивности исходного потока, умноженной на вероятность сохранения события в потоке, т.е. l_p = рl.

В заключение отметим, что марковские цепи являются математи­ческими моделями некоторых реальных систем, а потоки событий яв­ляются моделями внешних воздействий на эти системы. В дальнейшем будем считать, что переход системы из одного состояния i в другое j в соответствии с размеченным графом состояний происходит под действием потока событий с интенсивностью l_ij, равной соответс­твующей плотности вероятности перехода. Эта интенсивность определяется как среднее число переходов из состояния i в состояние j за единицу времени.

Если все потоки событий являются пуассоновскими, то процесс в системе будет марковским.