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

Аналогичные дифференциальные уравнения могут быть выведены и  для остальных вероятностей состояния p₂(t), p₃(t), p₄(t):

      (1.1)

 

Эти уравнения для вероятностей состояний называются уравнениями  Колмогорова.

Интегрирование этой системы  уравнений дает искомые вероятности  состояний как функции времени. Начальные условия берутся в  зависимости от того, каково было начальное  состояние системы S. Например, если в начальный момент времени (при t = 0) система S находилась в состоянии S₁, то надо принять начальные условия:

 p(0)=(1,0,0,0)

Заметим, что всех четырех  уравнений (1.1) можно было бы и не писать, поскольку p₁+ p₂+ p₃+ p₄=1 для всех t и любую из вероятностей p₁(t), p₂(t), p₃(t), p₄(t) можно выразить через три остальные и подставить в остальные уравнения. Однако в дальнейшем нам будет удобнее пользоваться полной системой уравнений типа (1.1).

Обратим внимание на структуру  уравнений (1.1). Все они построены по вполне определенному правилу, которое можно сформулировать следующим образом.

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

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

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

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

Поток событий называется стационарным, если вероятность попадания n событий  на интервале времени (t,t+ ) зависит от и не зависит от t. Это означает, что интенсивность потока событий не зависит от времени. Такие потоки событий часто встречаются на практике, об их стационарности строго можно говорить только на ограниченном интервале времени. Распространение этого участка до бесконечности - удобный прием.

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

Поток событий называется ординарным, если вероятность осуществления на бесконечно малом отрезке времени t двух и более событий i=1,2,3,... пренебрежимо малы по сравнению с вероятностью P(1,Δt) одного события.

Поток событий называется простейшим, если он стационарен, однороден и  не имеет последействия. Для такого потока вероятность появления на интервале m событий определяется формулой Пуассона P(m,Δt)=((λΔt)^m/m!)e^-λΔt λ-средняя интенсивность потока.

Для простейшего потока интервал t между соседними событиями имеет  показательное распределение: f(t)=λe^-λt. Если рассматривать бесконечно малый временной интервал, то с учетом ординарности пуассоновского потока  P(0,Δt)+P(1,Δt)≈1,aP(1,Δt)≈λΔt. 
           Поток событий называется рекуррентным или потоком "Пальма", если он стационарен, ординарен, а интервалы времени между событиями представляют собой независимые случайные величины с одинаковым произвольным распределением. 
Из определения следует:

1. Рекуррентный поток есть Марковский процесс.
2. Простейший поток это частный случай рекуррентного при показательном распределении интервалов между событиями.

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

Простейший поток, является потоком  Эрланга первого порядка. Можно  показать, что плотность вероятности  между событиями в потоке Эрланга k-ого порядка , (t > 0), -средняя интенсивность порождающего потока, <t>=k/λ, D(t)=k/λ².

 

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

Вероятностью i-го состояния p_i(t) – называется вероятность того, что в момент времени t система будет находиться в состоянии S_i. Очевидно, что для любого момента времени t_i    (1.7). Рассмотрим систему в момент t, и задав малый промежуток времени Dt, находим вероятность p₀(t+Dt), т.е. вероятность того, что в момент времени t+Dt система будет находиться в состоянии S₀. Достичь того, чтобы система находилась в состоянии S₀ можно двумя путями:

система в момент t c вероятностью p₀(t) находилась в состоянии S₀ и за время Dt не вышла из этого состояния. Вывести систему из состояния S₀ можно суммарным потоком интенсивности (l₀₁+l₀₂)*Dt. Вероятность того, что система будет находиться в состоянии S_0, в соответствии с первой возможностью, равна следующему:

 (1.8)

 cистема в момент времени t с вероятностями p₁(t)  или p₂(t) находится в состоянии S₁ или S₂ и за промежуток времени Dt переходит в состояние S₀:

 

(t+)=+*(1-

=+*-t)*(

 

(

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

 

1.5 Процессы гибели и размножений            

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

 

         

 

                                              Рис. 1.1  

 Т.е. каждое из состояний  системы связано с двумя соседними  состояниями прямой и обратной  связью, крайние состояния имеют  только по одному соседнему.  Здесь l_ij – плотность вероятности перехода системы из состояния S_i в состояние S_j в момент времени t.

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

 

                      S₁        S₂         S₃          S_k          S_n-1           S_n

Рис. 1.2

 

то можно сразу найти предельные вероятности состояний для каждого  из графов в отдельности, достаточно составить и решить в буквенном  виде уравнения для одного из них, а затем подставить вместо соответствующие  значения. Для многих часто встречающихся форм графов линейные уравнения легко решаются в буквенном виде. Марковская непрерывная цепь называется «процессом гибели и размножения», если ее граф состояний имеет вид, представленный на рис. 1.2, т. е. все состояния можно вытянуть в одну цепочку, в которой каждое из средних состояний (S₂, ..., S_n-1) связано прямой и обратной связью с каждым из соседних состояний, а крайние состояния (S₁, S_n) — только с одним соседним состоянием.  

 

 

 

2. Практическая часть

 

2.1 Постановка задачи

Найти предельные вероятности для процесса гибели и размножения, размеченный  граф состояний которого имеет следующий  вид:

 

                           

 

При λ₁₂ = 0,4, λ ₂₃ = 0,7, λ ₃₄ = 0,1, λ ₂₁ = 0,3, λ ₃₂ = 0,1, λ ₄₃ = 0,4.

 

2.2 Составление математической  модели

 Пусть Р₀-начальное состояние, которое рассчитывается по формуле

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

J=

N-максимальная вероятность, являющееся произвольным целым числом

i-количество шагов, которое зависит от максимальной вероятности

P_i+1-расчитанное значение вероятности, равна произведению транспортированной матрицы и i-ой вероятностью

 

2.3 Решение задачи с помощью уравнения Колмогорова в прикладной программе Mathcad

Представим задачу в матричной  форме

Тогда матрица перехода для данного  процесса и его начальное состояние  имеют вид

 

      

 

 

Каждая сторона в этой матрице в сумме равна единице и отражает вероятности перехода из состояния строки в состояния столбца.

                 

 

 

Вывод: примерно через 50 шагов по времени  распределение вероятностей стабилизируется, и 7,1% будет находиться в состоянии  S₁, 9,5% будет находиться в состоянии S₂, 66,7% будет находиться в состоянии S₃, и 16,7% будет находиться в состоянии S₄

Переходя к пределу, получаем дифференциальное уравнение Колмогорова для условных вероятностей а,

, P(0)=P_o

Рис.2.1 Интегрирование уравнений Колмогорова

Вероятности нахождения системы в  момент времени i в состояниях 1, 2, 3 ,4 соответственно.

Уравнение Колмогорова, соответственно этому графу, составляется следующим образом. Для каждого состояния вероятность P_i повышается из состояния E_i пропорционально g_ij P_i (дуга графа имеет направление от узла j к узлу i) и меняется пропорционально g_ij P_i (дуга графа имеет направление от узла i к узлу k). Так для состояния E_i уравнение будет следующим (все дуги выходят из этого состояния):

 

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

 

Исключив из этой систему Р₄, окончательно получим

 

 

2.4 Выбор программной среды

Для написания программы  выбран объектно-ориентированный язык программирования – Delphi 7. Он более удобный и понятный для восприятия приложений пользователем. Данный язык программирования позволяет вычислить и решить задачу с помощью уравнения Колмогорова.

Delphi может работать в ОС от Windows 98 до windows 7. Требования к программе: процессор должен быть типа Pentium с частотой не ниже 166 Гц, оперативной памятью 128 Мбайт, свободное место на жестком диске.

 

2.5 Основные блоки программы

Блок ввода данных:

begin

  data[1,1]:=strtofloat(edit1.Text);

  data[2,1]:=strtofloat(edit5.Text);

  data[3,1]:=strtofloat(edit9.Text);

  data[4,1]:=strtofloat(edit13.Text);

  data[1,2]:=strtofloat(edit2.Text);

  data[2,2]:=strtofloat(edit6.Text);

  data[3,2]:=strtofloat(edit10.Text);

  data[4,2]:=strtofloat(edit14.Text);

  data[1,3]:=strtofloat(edit3.Text);

  data[2,3]:=strtofloat(edit7.Text);

  data[3,3]:=strtofloat(edit11.Text);

  data[4,3]:=strtofloat(edit15.Text);

  data[1,4]:=strtofloat(edit4.Text);

  data[2,4]:=strtofloat(edit8.Text);

  data[3,4]:=strtofloat(edit12.Text);

  data[4,4]:=strtofloat(edit16.Text);

 

   p[1]:=strtofloat(edit17.Text);

   p[2]:=strtofloat(edit18.Text);

   p[3]:=strtofloat(edit19.Text);

   p[4]:=strtofloat(edit20.Text);

 

блок расчетов:

   for i:=1 to strtoint(edit21.Text) do

   begin

     for y:=1 to 4 do

       begin

         p1[y]:=0;

         for x:=1 to 4 do

         begin

           p1[y]:=p1[y]+p[x]*data[x,y];

         end;

       end;

       for y:=1 to 4 do

         begin

           p[y]:=p1[y];

         end;

 

блок вывода данных:

  label4.Caption:=floattostr(p[1]);

  label5.Caption:=floattostr(p[2]);

  label6.Caption:=floattostr(p[3]);

  label7.Caption:=floattostr(p[4]);