Марковские процессы. Их математическое описание и область их применения

     Рассмотрим  параметры,  определяющие  непрерывную   марковскую цепь.

     Пусть система  в момент времени t находится  в состоянии  Si. Рассмотрим элементарный промежуток времени DELTAt,  примыкающий к моменту времени t.  За интервал  DELTAt  система  может перейти из состояния Si в состояние Sj с переходной вероятностью Pij(t,DELTAt). зависящей в общем случае как от t, так и от DELTAt.

Рассмотрим  предел  отношения  этой  переходной вероятности  к ширине   интервала  DELTAt  при  условии,   что DELTAt --> 0:

 

                      Pij(t,DELTAt)

            lim     ----------------   =   LAij(t)      (1)

         DELTAt->0      DELTAt

 

Эта характеристика называется интенсивностью  перехода  или плотностью вероятности   перехода и в общем случае зависит от t.

     Из формулы  (1) следует,  что при малом DELTAt вероятность перехода Pij(t,DELTAt) с точностью  до  бесконечно  малых  высших порядков равна

 

              Pij(t,DELTAt) ~= LAij(t)*DELTAt

 

     Если плотности  вероятностей переходов  представляют собой функции времени LAij(t), марковский процесс называется неоднородным.

     Если все   плотности  вероятностей переходов не зависят от t(т.е. от  начала  отсчета элементарного участка DELTAt),  то марковский процесс называется однородным (LAij(t) = LAij = const).

     Для непрерывных  марковских  цепей  интенсивности  переходов проставляются у соответствующих дуг графа. Такой граф называется размеченным.

     Кроме интенсивностей   переходов, для  описания  непрерывных марковских   цепей   должен  быть  задан   вектор   вероятностей состояний   системы   в  исходный   (нулевой)   момент   времени |P(0)| = (P1(0), P2(0), ..., Pn(0)).

     Зная множество   состояний системы,  значения  интенсивностей переходов LAij(t),  а также вектор  начальных вероятностей системы |P(0)|,  определим вероятности состояний Pi(t), i = 1, n системы, граф которой имеет вид:

                               +------+

                               |      |Pii(DELTAt)

                           +---+---+  |

         P1i(DELTAt)       |       |<-+   Pi,n(DELTAt)

         +---------------->| Pi(t) +------------------+

         | +---------------|       |<---------------+ |

         | |Pi1(DELTAt)    +--+---++    Pn,i(DELTAt)| |

         | |                ^ | ^ |                 | |

         | |                | | | |                 | |

         | |           +----+ | | +------+          | |

         | |           |  +---+ +-----+  |          | |

         | |        (1)|  |(2)     (3)|  |(4)       | |

         | V           |  V           |  V          | V

      +--+----+      +-+-----+     +--+----+     +--+----+

      |       |      |       |     |       |     |       |

      | P1(t) |------|Pi-1(t)|-----|Pi+1(t)|-----| Pn(t) |

      |       |      |       |     |       |     |       |

      +-------+      +-------+     +-------+     +-------+

 

     (1) - Pi-1,i(DELTAt)     (2) - Pi,i-1(DELTAt)

     (3) - Pi+1,i(DELTAt)     (4) - Pi,i+1(DELTAt)

Как следует из приведенного графа, марковская цепь однородна, так как вероятности перехода не зависят от t.

     Для момента  времени t+DELTAt справедливо соотношение

                            n

         Pi(t + DELTAt) = SUMMA Pj(t) * Pji(DELTAt) =

                          j = 1

                                 n

      = Pi(t) * Pii(DELTAt) + SUMMA Pj(t) * Pji(DELTAt)

                              j = 1

                              j <> i

     Из свойства матрицы переходных вероятностей (Ш-4)  следует, что

                         n

     Pii(DELTAt) = 1 - SUMMA Pij(DELTAt)

                       j = 1

                       j <> i

 

     Тогда  Pi(t + DELTAt) =

 

                   n                     n

    = Pi(t)*{1 - SUMMA Pij(DELTAt)} +  SUMMA Pj(t) * Pji(DELTAt)

                 j = 1                 j = 1

                 j <> i                j <> i

 

или   Pi(t + DELTAt) -  Pi(t) =

 

               n                    n

= - Pi(t) * SUMMA Pij(DELTAt) + SUMMA Pj(t) * Pji(DELTAt)

             j = 1                j = 1

             j <> i               j <> i

 

     Разделим обе   части равенства на DELTAt и устремим DELTAt к нулю

                       Pi(t + DELTAt) -  Pi(t)

             lim   =  -------------------------- =

         DELTAt->0           DELTAt

 

                      n                Pij(DELTAt)

        = - Pi(t) * SUMMA    lim     -------------- +

                    j = 1  DELTAt->0    DELTAt

                    j <> i

 

                 n                   Pji(DELTAt)

             + SUMMA Pj(t) * lim    --------------

               j = 1      DELTAt->0    DELTAt

               j <> i

 

     В результате получим   систему   дифференциальных  уравнений для вероятностей состояний непрерывной марковской цепи, носящую имя ее автора  -  советского математика Колмогорова А. Н.

 

dPi(t)    ,                  n                n

------- = Pi(t) = - Pi(t) * SUMMA LAij + SUMMA Pj(t) * LAij

  dt                        j = 1            j = 1

                            j <> i           j <> i

 

     Pi(0) = Pi0  - вектор начальных  условий.

         ----

     i = 1, n

 

     Интегрирование этой  системы  по времени позволяет получить вероятности состояний как функции времени Pi(t).

     Существенно,  что в системе Колмогорова можно  ограничиться n - 1 уравнением. Дополнительно используется условие нормировки

 

                           n

                         SUMMA Pj = 1.

                          j=1

 

     Анализируя дифференциальные уравнения Колмогорова,  можно сформулировать формальное правило для их написания непосредственно по размеченному графу системы.

     В левой  части уравнения стоит  производная  от  вероятности рассматриваемого состояния  по  времени,  а  в  правой  части  - столько слагаемых,  сколько дуг графа связано с  рассматриваемым состоянием. Каждое   слагаемое   равно   произведению  плотности вероятности перехода,  соответствующей  данной  дуге  графа,  на вероятность того состояния, из которого исходит дуга графа. Если стрелка направлена      из      рассматриваемого  состояния, соответствующее произведение  имеет  знак  минус.  Если  стрелка направлена в состояние, то произведение имеет знак плюс.

     Это правило    составления    дифференциальных    уравнений Колмогорова для  вероятностей   состояний   является   общим   и справедливо для любой непрерывной марковской цепи.

     Для эргодических  однородных марковских цепей  существует стационарный режим   при t --> БЕСКОНЕЧНОСТЬ. При стационарном  режиме вероятности    состояний    стремятся     к     некоторым установившимся значениям  -  предельным вероятностям

 

                    lim          Pi(t) =  Pi,

              t -> БЕСКОНЕЧНОСТЬ

 

которые постоянны и не зависят от начального состояния  системы.

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

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

 

 

 

Потоки событий.

 

     Переход системы   в  некоторое   состояние   Si   называется событием. В   процессе   работы   система   неоднократно   может возвращаться в   состояние    Si.    Последовательность    таких однородных событий образует поток событий Si', Si", ... .

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

         T1  T2     Ti

     --+----+--+---+--+-----+---------> t

       0

 

     Поток называется ординарным, если события в нем происходят поодиночке.

     Если интервалы  являются неслучайными, то поток  называется регулярным или детерминированным и полностью характеризуется законом изменения длины интервалов в потоке. В противном случае поток называется случайным и характеризуется совместным законом распределения системы случайных величин (Т1, Т2, ....., Тn).

     На практике  наиболее  часто  приходится   иметь   дело   с потоками, в  которых  интервалы  времени  между  двумя соседними событиями Ti (i = 1, n) - непрерывные случайные величины. Такой случайный поток характеризуется многомерной плотностью вероятности f(TAU1, TAU2,......,TAUn), где TAUi - конкретные значения

случайных величин Тi.

     Поток называется стационарным, если его характеристики не изменяются во времени. Вероятность попадания того или иного числа m событий на участок оси времени t,t+TAU зависит только от TAU и не зависит от t. Интенсивность или плотность потока событий, то есть среднее число событий в единицу времени, постоянна:LA = const.

     В узком  смысле стационарность означает независимость плотности вероятности f(TAU1, TAU2,......,TAUn) от выбора начала отсчета.

     Если случайные   величины  Ti  являются  зависимыми,  поток называется потоком с  последействием,  ибо  для  любого  момента времени последующее  течение  потока  находится  в вероятностной зависимости от предыдущего.

     Если случайные   величины   Ti  являются  независимыми,  то случайный поток    называется     потоком     с     ограниченным последействием и для него справедливо:

 f(TAU1, TAU2,......,TAUn) = f1(TAU1)*f2(TAU2)*.......*fn(TAUn).

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

последействия означает,  что   события   наступают   в   системе независимо друг от друга. Для такого потока справедливо:

         fi(TAUi) = f(TAUi), i=1,2,....,n

     Поток называется  пуассоновским, если число m событий  потока, попадающих на участок TAU, распределено по закону Пуассона

                   m         -a

            pm = (a / m!) * e

где а - среднее число событий, попадающих на участок TAU, равное для стационарного потока a = LA*TAU.

     Определим  функцию распределения длины интервала T в стационарном пуассоновском потоке

                  F(TAU) = P(T < TAU)

     Выразим F(TAU) через вероятность P(T >= TAU)= F0(TAU) того, что в интервал TAU не попадает ни одно из событий:

                                         0       -a        -a

    F(TAU) = 1 - F0(TAU) = 1 - p0 = 1 - a /0! * e   = 1 - e

    Для стационарного  пуассоновского потока справедливо:

                    -LA*TAU                    -LA*TAU

      F(TAU) = 1 - e           ,  f(TAU) = LA*e           ,

то есть интервал времени  подчинен экспоненциальному (показательному) закону распределения с параметрами

                          1

     M(Ti) = SIGMA(Ti) = ------ .

                         LA

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

            1

     LA = -------  -  величина,  обратная  среднему  времени между событиями.

            M(Ti)

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

 

                    -LA*TAU1

     f1(TAU1) = LA*e        = f(TAU1) = f(TAUi) = f(TAU),

что является признаком отсутствия последействия.

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

     Если процесс   переходов  в системе происходит под воздействием простейшего   потока,  то  такой  процесс  является марковским, причем плотность вероятности перехода в соответствующей НМЦ совпвдает с интенсивностью потока переходов LA.

 

     Пример.

 

     Двухпроцессорная  вычислительная система  предназначена   для обработки простейшего потока задач, поступающих с интенсивностью LA. Производительность процесоров,  соответственно, равны B1 и B2,  причем B1 > B2. Трудоемкость задач представляет случайную величину со средним значением teta.

     Задача в   первую   очередь   принимается   на  обслуживание процессором, имеющим  большую   производительность.   Если оба процессора заняты, пользователь получает отказ.

     Определить  в установившемся режиме вероятность  отказа Ротк, коэффициенты загрузки процессоров KSI1, KSI2.

     Рассмотрим  возможные     состояния     системы,     которые определяются состояниями процессоров:

     S00 - оба процессора  простаивают;

     S10 -   первый   процессор  занят  решением  задач,  второй простаивает;

     S01 - второй  процессор занят, первый простаивает;

     S11 - оба процессора  заняты решением задач.

 

 

 

 

 

 

 

 

     Граф функционирования  системы имеет вид:

 

                           +-----+       LA

                  MU2      | S00 +-------------+

                 +-------->|     |<----------+ |

                 |         +-----+       MU1 | |

                 |                           | V

              +--+--+                      +-+---+

              | S01 |                      | S10 |

              |     |                      |     |

              +---+-+                      +-+---+

                ^ |                          | ^

                | | LA      +-----+   LA     | |

                | +-------->| S11 |<---------+ |

                +-----------|     +------------+

                 MU1        +-----+         MU2