Введение в теорию дискретных марковских процессов с непрерывным временем
Пусть моделируемый процесс 9[t) может принимать значения ..9, ,к = \,К. причем смена состояний происходит в случайные моменты времени.
Дискретный марковский процесс с непрерывным временем
Если ввести вероятности перехода процесса из состояние і в состояние j как условные вероятности того, что в момент времени t процесс будет в состоянии если в момент времени t0 он был в состоянии, то есть, во-первых, справедливы соотношения К (5.21) (5.22) и, во-вторых, имеет место следующее уравнение Колмогорова-Чепмена:
Лij (t0>t + АО = Yun<k КО• я# К + А0’t > *о> At > 0 • (5.23)
Для малых временных интервалов вероятности переходов в первом приближении имеют вид:
^(М + Д0~1+Л*(0-АП (524)
то есть прямо пропорциональны размеру этого временного интервала, где параметр (О имеет смысл интенсивности переходов.
Так как выполняется условие (5.24), то из (5.23) следует, что
(5-25)
j(j*k)
и уравнение Колмогорова-Чепмена путем предельного перехода при At О преобразуется к виду:
т-*А‘о>і) = 'Еяч‘7Г*(іоА (5-26)
01 k=1
Аналогичному уравнению удовлетворяют не только вероятности переходов, но и абсолютные вероятности состояний:
= (5-2?)
аТ k= 1
Дискретный марковский процесс с непрерывным временем считается однородным, если вероятности перехода
7r,jM = ^u(T),T=t-t0> (5.28)
зависят только от разности времен между началом и завершением переходов из состояния / в состояние j, а не от абсолютных значений времени.
Для однородных марковских процессов интенсивность А,- {f) = \ не
зависит от времени и уравнение Колмогорова-Чепмена (5.26) преобразуется к виду:
7= ат fr=i (5.29)
Если для однородного марковского процесса существует предельное значение вероятностей переходов
р = lim 7г (г)
г—*оо J (5.30)
которые не зависят от начального состояния, то такие процессы относят к эргодическим, для которых существует однозначно определенное стационарное состояние, при этом вероятности стационарных состояний находятся путем решения системы алгебраических уравнений:
ЕѴа=0’ Ел=1-
*=1 Jt=l
При моделировании того или иного процесса с использованием рассматриваемого аппарата этот процесс представляют в виде ориентированного графа, вершины которого соответствуют дискретным состояниям процесса, и дуги указывают на пути перехода процесса между состояниями во времени. Пример такого графа приведен.
Пример ориентированного графа для марковского процесса с дискретным множеством состояний и непрерывным временем
После построения такого графа достаточно просто написать систему уравнений Колмогорова-Чепмена для вероятностей нахождения моделируемой системы в каждом из состояний, соблюдая следующие мнемонические правила:
1) в левой части каждого уравнения указывается производная вероятности нахождения системы в данном состоянии;
2) в правой части каждого уравнения указываются произведения вероятностей нахождения системы в состояниях, смежных с данным состоянием, переход в которые или из которых в данное состояние указан на графе дугами с ненулевыми интенсивностями, при этом интенсивность берется со знаком «минус», если дуга является исходящей из рассматриваемого состояния и со знаком «плюс», если дуга является входящей в рассматриваемое состояние.
Так, для указанного на рисунке 5.4 графа система дифференциальных уравнений, описывающих динамику изменения состояний рассматриваемой системы, с начальными условиями имеет вид:
Ра (0 = “Ля • Ра (0 + 4о • Рі (0 + ^п'Рг (Оі
• д(0 = Ѵд>(0-Ао'А(0-42-а(0; (5'32)
р2( 0= Ли-МО-АгМО,
при начальных условиях р0 (0) = 1, р1 (0) = р2 (0) = 0, р0 + р{ + р2 = 1.
Наиболее широко на практике для решения таких систем дифференциальных уравнений применяется метод преобразования Лапласа, что позволяет свести всё к решению системы алгебраических уравнений с последующим обратным его преобразованием Лапласа. Например, для системы уравнений (5.32) его преобразование Лапласа записывается следующим образом:
S Xg (s) Ag j • Xg (f) + Agg * Xj (f) + Ag j ' X, (.S ), 5 ' Х1 (Л1) — /Igj * Xg (Л1) — Alg * Xj (S) — ' Xj (5),
s x2(s)
Аз'*!*»
где x. (s) = je f] (t) dt, i = 0,2 преобразование Лапласа от вероятности или о ее производной для і -го состояния.
Решение данной системы уравнений относительно вероятности перехода системы в конечное состояние 2 имеет вид
Из приведенного видно, что уже при трех состояниях решение системы уравнений имеет весьма громоздкий вид, а при количестве состояние более 4 в общем случае не имеет аналитического решения и, как правило, решается численными методами. Это приводит к существенным ограничениям в применении теории марковских процессов в практике моделирования. Кроме того, имеются и другие существенные недостатки, к которым относятся следующие:
1) для определения интенсивностей переходов, зачастую, необходимо дополнительно разрабатывать соответствующие модели;
2) в связи с необходимостью сокращения количества учитываемых состояний процесса (чаще всего, за счет их агрегирования) возникают трудности в интерпретации состояний процесса;
3) невозможно моделировать параллельные взаимосвязанные процессы;
4) невозможно вводить в систему дифференциальных уравнений логические условия, которые часто обусловливают протекание моделируемого процесса.
Все это привело к применению и других подходов к моделированию динамики реализации процессов.
