Основы марковских процессов.

Уравнения Колмогорова

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

Определение марковского процесса. Пусть имеется система S, состояние которой изменяется во времени случайным, непредсказуе­мым образом и представляет собой случайный процесс. Этот процесс называется марковским, если для каждого момента времени t₀ веро­ятность любого состояния при t > t₀ (в будущем) зависит только от вероятности, состояния в момент t₀ (в настоящем) и не зависит от вероятностей состояний при t < t₀ (в прошлом).

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

Марковская цепь называется дискретной, если переход из одного состояния в другое происходит в строго фиксированные промежут­ки времени, отделенные друг от друга равными интервалами. Если же эти переходы возможны в любой момент времени t, то соответствую­щая марковская цепь называется непрерывной. Переход из одного состояния в другое может быть отображен графом состояний, в кото­ром вершины представляют собой возможные состояния системы, а ду­ги графа отражают переходы из одного состояния в другое. Если две вершины i и j соединяются дугой (i,j), то это означает, что воз­можен непосредственный переход из состояния i в состояние j. Мар­ковская цепь может, таким образом, быть представлена как случай­ное блуждание на графе состояний системы.

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

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

 

 

Рис.1.1

Рассмотрим некоторую произвольную систему, граф состояний которой приведен на рис.1.1. Система имеет n состояний S₁,S₂,...,S_n. Процесс перехода из одного состояния в другое описывает­ся непрерывной цепью Маркова. Пусть P_i(t) - вероятность того, что в момент времени t система будет находиться в состоянии S_i (i=1,2,…,n). Поскольку система не может находиться одновременно в двух состояниях, то события, заключающиеся в нахождении системы в состояниях S₁,S₂,…,S_n, несовместны и образуют полную сис­тему событий. Отсюда следует

                     (1.1)

Это соотношение называется условием нормировки. Задача заключает­ся в определении вероятности любого состояния P_i(t) в любой мо­мент времени t.

Введем понятие вероятности перехода системы из состояния i, где она находилась в момент времени t, в состояние j за время Dt P_ij(t,Dt). Очевидно, что P_ij(t,Dt) представляет собой условную вероятность того, что в момент времени t + Dt система окажется в состоянии S_j при условии, что в момент времени t она находилась в состоянии S_i: p_ij(t,Dt)= p(S_j(t+Dt)/S_i(t)).

Предел отношения вероятности перехода p_ij(t,Dt) к длине интервала времени Dt назовем плотностью вероятности перехода

.             (1.2)

Плотность вероятности перехода определим только для случаев i¹j.

Если l_ij(t)=const, то марковская цепь называется однородной. В противном случае, когда l_ij(t) являются функциями времени, цепь называется неоднородной. При расчетах вероятностей состояний марковской цепи предполагается, что все эти плотности вероятнос­тей переходов l_ij известны. Если у каждой дуги графа состояний системы проставить плотность вероятности перехода по данной дуге, то полученный граф назовем размеченным графом состояний (см.рис.1.1). Уравнения Колмогорова составляются в соответствии с разме­ченным графом состояний. Рассмотрим фрагмент размеченного графа состояний (рис.1.1), обведенный штрихпунктирной линией. Отбро­сим вначале дуги, изображенные пунктиром, и определим вероятность нахождения системы в состоянии S_i в момент времени t+Dt. С уче­том того, что вершина S_i связана только с вершинами S_k и S_j, ука­занное событие будет иметь место в двух случаях:

- система находилась в состоянии S_i в момент времени t и за время Dt из этого состояния не вышла;

- система находилась в состояния s_k в момент времени t и за время Dt перешла из S_k в S_i.

Если отрезок Dt достаточно мал, то вероятность перехода p_ij(t,Dt) может быть определена приближенно с помощью (1.2)

         p_ij(t,Dt)» l_ij(t)Dt                              (1.3)

С учетом (1.3) и свойства марковости процесса вероятность первого случая (отсутствие перехода по дуге (S_i,S_j))

p_I = (1-l_ij(t)Dt)p_i(t).

Вероятность второго случая с учетом (1.3)

p_II» l_ki(t)p_k(t).

Тогда можно определить искомую вероятность как

p_i(t+Dt)= p_I + p_II = (1-l_ij(t)Dt)p_i(t) + l_ki(t)p_k(t)Dtp_k(t)

или 

       (1.4)

Переходя в (1.4) к пределу при Dt ® 0, получим

 .                (1.5)

 

Теперь добавим к вершине S_i дуги, обозначенные на рис.1.1 пункти­ром. Тогда при вычислении p_i(t+Dt) необходимо учитывать возможный переход из S_i в S_j и S_r и переходы из S_k и S_l в S_i. В этом случае

P_I = [1-(l_ij(t)+l_ir)Dt]p₁(t),

P_II = l_k1(t)Dtp_k(t)+l_l1(t)Dtp₁(t).

Повторяя вышеописанные рассуждения, получим

 . (1.6)

 

На основании (1.5) и (1.6) можно сформулировать правила сос­тавления уравнений Колмогорова по размеченному графу состояний непрерывной марковской цепи:

1. Система дифференциальных уравнений Колмогорова имеет форму Коши. Каждое уравнение составляется с помощью рассмотрения ве­роятности состояния, представленного соответствующей вершиной в размеченном графе. Число уравнений системы равно числу вершин графа.

2. Число слагаемых правой части каждого уравнения равно чис­лу дуг, инцидентных соответствующей вершине.

3. Дугам с положительной инциденцией соответствуют отрица­тельные слагаемые, а дугам с отрицательной инциденцией - положи­тельные.

4. Каждое слагаемое правой части равно произведению вероят­ности состояния, соответствующего началу рассматриваемой дуги, на плотность вероятности перехода по данной дуге.

Начальные условия для системы уравнений Колмогорова опреде­ляются начальным состоянием системы. Например, если начальное состояние было S₂, то начальные условия имеют вид: p₁(0)=0; р₂(0)=1; р₃(0)=0;…;р_n(0)=0. Уравнения (1.5) и (1.6) были вы­ведены для общего случая неоднородной марковской цепи. Для одно­родной марковской цепи все l_ij(i,j=l,…,n) постоянны.

Рассмотрим одно важное свойство уравнений Колмогорова (1.5), которое может быть представлено в виде

,                           (1.7)

 

где  - n-мерный вектор вероятностей состояний системы; р = {p₁(t),…,p_n(t)}; L - n´n-матрица плотностей перехода.

В соответствии с вышеописанными правилами составления урав­нений Колмогорова одна и та же плотность вероятности перехода l_ij будет входить в одно из уравнений со знаком "+", а в другое - со знаком "-", поскольку для двух смежных вершин дуга, соединяющая их, будет обладать положительной инциденцией по отношению к одной вершине и отрицательной по отношению к другой. Это приведет к то­му, что сумма всех элементов в каждом столбце матрицы будет равна нулю. Тогда любая строка матрицы L будет равна сумме остальных строк. Следовательно, матрица L является всегда вырожденной. Бо­лее строго это свойство доказывается в [7].

Рассмотрим систему с размеченным графом состояний, изобра­женным на рис. 1.2. Система уравнений Колмогорова и матрица L для этого случая в соответствии с правилами 1-4 будут иметь вид:

dp₁/dt=-(l₁₂+l₁₃)p₁+l₄₁p_4,

dp₂/dt=l₁₂p₁-l₂₅p₂+l₃₂p_3,

dp₃/dt=l₁₃p₃-(l₃₂+l₃₄)p₃+l₅₃p_5,

dp₄/dt=l₃₄p₁-(l₄₁+l₄₅)p_4,

dp₅/dt=l₂₅p₂+l₄₅p₄-l₅₃p_5.

Исключение любого уравнения из этой системы нарушает указанное соотношение для строк матрицы L, следовательно, ранг матрицы L будет равен n-1. Для того чтобы система уравнений Колмогорова имела единственное решение при заданных начальных условиях, не­обходимо исключить любое из уравнений системы (1.7) и заме­нить его условием нормировки (1.1).

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

 

Рис.1.2

 

Получить это решение можно с помощью любых численных методов (например, Рунге-Кутта, Эйлера-Коши и т.д.), реализуемых на ЭВМ. Только в самых простых случаях система уравнений Колмогорова мо­жет быть проинтегрирована в квадратурах. В большинстве практичес­ких случаев для расчета вероятностей состояний используются не решения систем уравнений Колмогорова в любой момент времени, а асимптотические оценки этих решений при t®¥.