Загрузка...

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


Марковским процессом называется такой случайный процесс, который обладает следующим свойством: для каждого момента времени t0 вероятность любого состояния в будущем (t > t0) зависит только от его состояния в настоящем (t = t0) и не зависит от того, когда и каким образом система пришла в это состояние. Другими словами, в Марковском случайном процессе будущее его развитие зависит только от настоящего состояния и не зависит от ?предыстории? процесса.

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

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

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

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

Рассмотрим некоторую систему S с дискретными состояниями Х1 , Х2, … , Хn ,которая переходит из состояния в состояние под влиянием некоторых потоков событий. Будем считать, что эти потоки простейшие. Тогда вероятность Рij перехода из состояния Хi в состояние Хj , за малый промежуток времени Dt равна lijDt , т.е. Рij = lijDt , где Рij называется переходной вероятностью, а lij — плотностью потока, переводящего систему из состояния Хi в состояние Хj . Предполагая, что известны плотности вероятностей перехода lij , построим граф состояний системы и над дугами напишем соответствующие плотности lij . Такой граф называется размеченным графом состояний. Оказывается, что, зная этот размеченный граф, можно определить вероятности состояний P1(t) , P2(t), … , Pn(t), как функция времени.

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

Рассмотрим однородный процесс, т.е. процесс, в котором lij не зависит от t .

Пусть система в некоторый момент времени t находится в состоянии Хm с вероятностью Pm(t) . Придадим величине t малое приращение Dt и найдем вероятность того, что в момент времени t + Dt система будет находиться в том же состоянии Хm . Это событие может произойти следующим образом: 1) в момент t система уже была в состоянии Хm и за время Dt не вышла из этого состояния или: 2) в момент t система была в состоянии Хi clip_image002, а за время Dt перешла в состояние Хm . Вероятность первого варианта вычисляется так: Pm(t) умножается на условную вероятность того, что система за Dt не перейдет ни в какое другое состояние Хi (i?m) . Так как события, состоящие в переходе за время Dt из Хm в Хi , несовместны, то вероятность того, что осуществится один из этих переходов, равна сумме их вероятностей, т.е.

clip_image004

(с точностью до бесконечно малых высших порядков).

Вероятность того, что не осуществится ни один из этих переходов, равна

clip_image006

Отсюда вероятность первого варианта

Pm(t) ( clip_image008) .

Аналогично, вероятность второго варианта равна вероятности того, что в момент t система была в состоянии Хi (i?m), умноженной на условную вероятность перехода за время Dt в состояние Хm :

Pi (t) *lim*Dt clip_image010

Применяя правило сложения вероятностей, получим:

Pm(t+Dt) = Pm(t) ( clip_image012) + clip_image014=

Pm(t) (1 — lm1Dt — lm2Dt — … — lmnDt) + P1(t) l1mDt +

+ P2(t)l2mDt + … + Pn(t)l nmDt ;

Pm(t+Dt) — Pm(t) = P1(t) l1mDt + P2(t)l2mDt + … + Pn(t)l nmDt —

— Pm(t) lm1Dt — Pm(t) lm2Dt — … — Pm(t) lmnDt .

Последнее равенство делим на Dt , получим

clip_image016 P1(t) l1m + P2(t)l2m + … + Pn(t)l nm

-Pm(t) lm1 — Pm(t) lm2 -…- Pm(t) lmn ;

Перейдем к пределу при Dt ® 0

clip_image018

При этом правая часть уравнения не изменится, поскольку она не зависит от Dt .

Таким образом, дифференциальное уравнение имеет вид:

clip_image020

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

Интегрирование этой системы с учетом условий

clip_image024 дает все вероятности состояний.

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

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

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

Пример: Составим систему уравнений Колмогорова для случая, когда граф состояний имеет вид, представленный на рис.1.4.

clip_image026

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

clip_image028

К этим уравнениям надо добавить еще начальные условия.

Например, если при t = 0 система S находится в состоянии Х1 , то начальные условия имеют вид:

P1 (0) = 1; P2 (0) = P3 (0) = P4 (0) = 0 .

Далее поставим вопрос следующим образом: что будет происходить в системе S при t ® ? ? Будут ли функции P1 (t) , P2 (t) , … , Pn (t) стремиться к каким-то пределам ?

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

clip_image030

Предельные вероятности состояний в сумме должны давать единицу.

clip_image032

Таким образом, при t ® ? каждое состояние системы осуществляется с постоянной вероятностью, т.е. в системе устанавливается так называемый стационарный режим .

Для вычисления предельных вероятностей состояний P1 , P2 , … , Pn , необходимо в системе уравнений Колмогорова положить все левые части равными нулю, так как в стационарном режиме все вероятности состояний постоянны, а это значит, что их производные равны нулю. Система уравнений Колмогорова превращается в систему линейных алгебраических уравнений, решив которую, найдем P1 , P2 , … , Pn .

Пример. 1.2. Система имеет возможные состояния Х1 , Х2 , Х3 , размеченный граф которой дан на рис.1.5.

Запишем уравнения Колмогорова для вероятностей состояний:

clip_image034

clip_image036

Полагая левые части первых трех уравнений равными нулю, получим

clip_image038

Поскольку одно уравнение можно опустить, рассмотрим систему из 2-х первых уравнений и, учитывая, что P1 + P2 + P3 = I , получаем систему

clip_image040

Из первых 2-х уравнений имеем

clip_image042

Из уравнения -2Р1 + 2 Р3 = 0 Р3 = Р1 . Подставим в уравнение Р1 + Р2 + Р3 = 1

Р3 + 2Р3 + Р3 = 1; 4Р3 = 1 ; Р3 = clip_image044 ; Р1 = clip_image045 , Р2 = clip_image047 .

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

Р1 = clip_image045[1] ; Р2 = clip_image047[1] ; Р3 = clip_image045[2] . Это означает, что в стационарном режиме система S будет проводить в состоянии Х1 в среднем clip_image045[3] часть времени, в состоянии Х2 – половину времени и в состоянии Х3clip_image045[4] часть времени.

Процесс “гибели и размножения”.

Формулы нахождения вероятностей состояний.

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

Загрузка...