Основные понятия теории марковских процессов: случайный процесс, марковский процесс, граф состояний, поток событий

1.

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

2.

Случайный процесс
• Процесс работы СМО представляет собой
случайный процесс. Под случайным
(вероятностным или стохастическим)
процессом понимается процесс изменения
во времени какой-либо системы в
соответствии с вероятностными
закономерностями.

3.

Случайный процесс
• Процесс называется процессом с дискретными
состояниями, если его возможные состояния sl9 s2, ...
можно заранее перечислить, а переход системы из
состояния в состояние происходят мгновенно (скачком).
Процесс называется процессом с непрерывным
временем, если моменты возможных переходов
системы из состояния в состояние не фиксированы
заранее, а случайны.
• Процесс работы СМО представляет собой случайный
процесс с дискретными состояниями и непрерывным
временем. Это означает, что состояние СМО меняется
скачком в случайные моменты времени появления
каких-либо событий, например отключение участка
электрической сети при возникновении аварийной
ситуации.

4.

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

5.

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

6.

Марковские случайные процессы
• Примером марковского процесса может
служить работа счетчика электрической
энергии. Состояние системы учета
электроэнергии в момент t характеризуется
количеством потребленной электроэнергии в
кВт ч до данного момента. Пусть в момент
t0 счетчик имеет показание s0. Вероятность
того, что в момент t > t0 счетчик покажет то или
иное значение потребленной электроэнергии
st, зависящее от s0, но не зависящее от того, в
какие моменты времени изменялись показания
счетчика до момента t0. Многие процессы
можно приближенно считать марковскими.

7.

Марковские случайные процессы
Пусть имеется некоторая система S, дискретные состояния
которой меняется во времени по некоторому вероятностному
закону, т.е. в ней протекает случайный процесс.
В исследовании процессов и систем большое значение имеют
марковские процессы двух типов:
- процессы с дискретными состояниями и дискретным
временем;
- процессы с дискретными состояниями и непрерывным
временем.
Случайный процесс называется процессом с дискретным
временем, если переходы системы из состояния в состояние
возможны только в заранее фиксированные моменты
времени: t1,t2, …. Случайный процесс называется процессом с
непрерывным временем, если переходы системы из состояния
в состояние возможны в случайные моменты времени t.

8.

Граф состояний
При анализе случайных процессов с дискретными состояниями
удобно пользоваться геометрической схемой — так называемым
графом состояний. Обычно состояния системы изображаются
прямоугольником (кружком), а возможные переходы из состояния
в состояние — стрелками (ориентированными дугами),
соединяющими состояния.
Марковский случайный процесс с дискретными состояниями и
дискретным временем обычно называют марковской цепью. Для
такого процесса моменты времени tl512, ..., когда система S может
менять свое состояние, удобно рассматривать как
последовательные шаги процесса, а в качестве аргумента, от
которого зависит процесс, рассматривать не время t, а номер шага:
1, 2,..., к,.... Случайный процесс в этом случае характеризуется
последовательностью состояний S0,S1,S2,….Sk
• где s0 — начальное состояние системы (перед первым шагом);
• Sj — состояние системы непосредственно после первого шага;
• sk — состояние системы после k-го шага.

9.

Пример
Построить граф состояний для
следующего случайного
процесса. На электростанции
установлено два генератора,
каждый из которых в случайные
моменты времени может выйти
из строя, после чего начинается
его ремонт, выполняемый с
заранее неизвестным случайным
временем.
Решение. 1. Возможные
состояния системы: s0 — оба
генератора исправны;
Sj — первый генератор
ремонтируется, второй исправен;
s2 — второй генератор
ремонтируется, первый
исправен; s3 — оба генератора
ремонтируются.

10.

Пример
Стрелка, направленная, например, из s0 в s(, означает
переход системы в момент отказа первого генератора, а из
Sj в s0 — переход в момент окончания ремонта этого
генератора. На графе отсутствуют стрелки из s0 в s3 и из s3 в
s0. Это объясняется тем обстоятельством, что выходы из
строя предполагаются не зависимыми друг от друга и,
например, вероятность одновременного выхода из строя
двух генераторов (переход из s0 в s3) или одновременное
окончание ремонта двух генераторов (переход из s3 в s0)
мало вероятно.
Вероятность того, что система S, находящаяся в состоянии
sn, за элементарный промежуток времени (t + At) перейдет
в состояние Sj, есть вероятность того, что за это время At
появится хотя бы одно событие, переводящее систему S из
Sj в Sj.

11.

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

12.

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

13.

Поток событий
1.Поток событий называется стационарным, если вероятность
попадания того или иного числа событий на участок времени длиной
зависит только от длины участка и не зависит от того, где именно на оси
ot расположен этот участок (однородность по времени) - вероятностные
характеристики такого потока не должны меняться от времени. В
частности, так называемая интенсивность (или плотность) потока
событий (среднее число событий в единицу времени) постоянна.
2.Поток событий называется потоком без последствия, если для любых
непересекающихся участков времени число событий, попадающих на
один из них, не зависит от того, сколько событий попало на другой (или
другие, если рассматривается больше двух участков). Отсутствие
последствия в потоке означает, что события, образующие поток,
появляются в последовательные моменты времени независимо друг от
друга.
3. Поток событий называется ординарным, если вероятность попадания
на элементарный участок двух или более событий пренебрежительно
мала по сравнению с вероятностью попадания одного события (события
в потоке приходят поодиночке, а не парами, тройками и т.д.).

14.

Поток событий
• Поток событий, обладающий всеми тремя
свойствами, называется простейшим (или
стационарным пуассоновским).
Нестационарный пуассоновский поток
обладает только свойствами 2 и 3.
Пуассоновский поток событий (как
стационарный, так и нестационарный) тесно
связан с известным распределением Пуассона.
А именно, число событий потока, попадающих
на любой участок, распределено по закону
Пуассона.

15.

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

16.

Вероятность событий
• Вероятностью i-го состояния называется
вероятность pi(t) того, что в момент t
система будет находиться в состоянии Si.
Очевидно, что для любого момента t сумма
вероятностей всех состояний равна
единице:

17.

Уравнение Колмагорова
• Уравнения Колмогорова - уравнения для переходной
функции марковского случайного процесса.
• Исчерпывающей количественной характеристикой
Марковского процесса является совокупность
вероятностей состояний, т.е. вероятностей pi(t) того, что
в момент t процесс будет находиться в
состоянии si(i =1…n).

18.

Уравнение Колмагорова
Рассмотрим, как определяются вероятности состояний по приведенному
графу состояний, считая все потоки простейшими. В случайный момент
времени t система может находиться в одном из состояний si с вероятностью
pi(t). Придадим t малое приращение ∆t и найдем, например, p2(t+∆t) вероятность того, что в момент t+∆t система будет в с состоянии s2. Это
может произойти, во-первых, если система в момент была в состоянии s2 и
за время t не вышла из него; во-вторых, если в момент t система была в
состоянии s1 или s5 и за время ∆t перешла в состояние s2.
В первом случае надо вероятность p2(t) умножить на вероятность того, что за
время ∆t система не перейдет в состояние s1, s3 или s4. Суммарный поток
событий, выводящий систему из состояния s2, имеет интенсивность λ21+
λ23+ λ24. Значит, вероятность того, что за время ∆t система выйдет из
состояния s2, равна (λ21+ λ23+ λ24)∆t. Отсюда вероятность первого варианта
p2.1(t+∆t)= p2(t)[1-(λ21+ λ23+ λ24)∆t].
Найдем вероятность перехода в состояние s2. Если в момент t система
находилась в состоянии s1 с вероятностью pi(t), то вероятность перехода в
состояние s1 за время ∆t равна p2.2(t+∆t)= p1(t)λ12∆t.
Аналогично для состояния s5. p2.3(t+∆t)= p1(t)λ52∆t.
Складывая вероятности p2.1(t+∆t) + p2.2(t+∆t) + p2.2(t+∆t), получим.

19.

Вывод уравнения Колмагорова
Складывая вероятности p2.1(t+∆t) + p2.2(t+∆t) + p2.2(t+∆t),
получим.
Раскроем квадратные скобки, перенесем p2(t) в левую часть и разделим обе части
на ∆t:
Если устремить ∆t к нулю, то слева получим производную
функции p2(t):
Аналогичные уравнения можно вывести для всех остальных состояний.
Получается система дифференциальных уравнений:

20.

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

21.

Уравнение Колмагорова
Тоже самое, что
и на
предыдущем
слайде
• правило составления уравнений Колмогорова. В левой части
каждого из них стоит производная вероятности i-го
состояния. В правой части — сумма произведений
вероятностей всех состояний (из которых идут стрелки в
данное состояние) на интенсивности соответствующих
потоков событий, минус суммарная интенсивность всех
потоков, выводящих систему из данного состояния,
умноженная на вероятность данного (i-го состояния).