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

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

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

Поясним понятие марковского случайного процесса.

Пусть имеется некоторая система S, состояние которой меняется с течением времени (под системой S может пониматься все что угодно: промышленное предприятие, техническое устройство, ремонтная мастерская и т. д.). Если состояние системы S меняется во времени случайным, заранее непредсказуемым образом, говорят, что в системе S протекает случайный процесс.

Примеры случайных процессов:

флуктуации цен на фондовом рынке;

обслуживание клиентов в парикмахерской или ремонтной мастерской;

выполнение плана снабжения группы предприятий и т. д.

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

поступление на фондовый рынок непредсказуемых известий о политических изменениях;

случайный характер потока заявок (требований), поступающих со стороны клиентов;

случайные перебои в выполнении плана снабжения и т. д.

ОПРЕДЕЛЕНИЕ. Случайный процесс, протекающий в системе, называется марковским (или процессом без последствия ), если он обладает следующим свойством: для каждого момента времени t 0 вероятность любого состояния системы в будущем (при t > t 0) зависит только от ее состояния в настоящем (при t = t 0) и не зависит от того, когда и каким образом система пришла в это состояние (т. е. как развивался процесс в прошлом).

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

Рассмотрим пример. Пусть система S представляет собой фондовый рынок, который уже существует какое-то время. Нас интересует, как будет работать система в будущем. Ясно, по крайней мере в первом приближении, что характеристики работы в будущем (вероятности падения цен конкретных акций через неделю) зависят от состояния системы в настоящий момент (здесь могут вмешаться самые различные факторы типа решений правительства или результатов выборов) и не зависят от того, когда и как система достигла своего настоящего состояния (не зависят от характера движения цен на эти акции в прошлом).

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

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

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

ОПРЕДЕЛЕНИЕ. Случайный процесс называется процессом с дискретными состояниями, если возможные состояния системы s x , s 2 , s v ... можно перечислить (пронумеровать) одно за другим, а сам процесс состоит в том, что время от времени система S скачком (мгновенно) перескакивает из одного состояния в другое.

Например, разработку проекта S осуществляют совместно два отдела, каждый из которых может совершить ошибку. Возможны следующие состояния системы:

5, - оба отдела работают нормально;

s 2 - первый отдел совершил ошибку, второй работает нормально;

s 3 - второй отдел совершил ошибку, первый работает нормально;

s 4 - оба отдела совершили ошибку.

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

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

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

При анализе случайных процессов с дискретными состояниями очень удобно пользоваться геометрической схемой - так называемым графом состояний. Граф состояний геометрически изображает возможные состояния системы и ее возможные переходы из состояния в состояние.

Пусть имеется система S с дискретными состояниями:

Каждое состояние будем изображать прямоугольником, а возможные переходы (“перескоки”) из состояния в состояние - стрелками, соединяющими эти прямоугольники. Пример графа состояния приведен на рис. 4.1.

Заметим, что стрелками отмечаются только непосредственные переходы из состояния в состояние; если система может перейти из состояния s 2 в 5 3 только через s y то стрелками отмечаются только переходы s 2 -> и л, 1 -> 5 3 , но не s 2 -» s y Рассмотрим несколько примеров:

1. Система S - фирма, которая может находиться в одном из пяти возможных состояний: s ] - работает с прибылью;

s 2 - утратила перспективу развития и перестала приносить прибыль;

5 3 - стала объектом для потенциального поглощения;

s 4 - находится под внешним управлением;

s 5 - имущество ликвидируемой фирмы продается на торгах.

Граф состояний фирмы показан на рис. 4.2.

Рис. 4.2

2. Система S - банк, имеющий два отделения. Возможны следующие состояния системы:
5, - оба отделения работают с прибылью;

s 2 - первое отделение работает без прибыли, второе работает с прибылью;

5 3 - второе отделение работает без прибыли, первое работает с прибылью;

s 4 - оба отделения работают без прибыли.

Предполагается, что улучшение состояния не происходит.

Граф состояний представлен на рис. 4.3. Отметим, что на графе не показан возможный переход из состояния s ] непосредственно в s 4 , который осуществится, если банк сразу будет работать в убыток. Возможностью такого события можно пренебречь, что и подтверждает практика.

Рис. 4.3

3. Система S - инвестиционная компания, состоящая из двух трейдеров (отделов): I и II; каждый из них может в какой-то момент времени начать работать в убыток. Если это происходит, то руководство компании немедленно принимает меры для восстановления прибыльной работы отдела.

Возможные состояния системы: s - деятельность обоих отделов прибыльна; s 2 - первый отдел восстанавливается, второй работает с прибылью;

s 3 - первый отдел работает с прибылью, второй восстанавливается;

s 4 - оба отдела восстанавливаются.

Граф состояний системы показан на рис. 4.4.

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

Состояния системы будем для удобства нумеровать не одним, а двумя индексами; первый будет означать состояния первого трейдера (1 - работает с прибылью, 2 - его деятельность изучается руководством, 3 - восстанавливает прибыльную деятельность отдела); второй - те же состояния для второго трейдера. Например, s 23 будет означать: деятельность первого трейдера изучается, второй - восстанавливает прибыльную работу.

Возможные состояния системы S:

s u - деятельность обоих трейдеров приносит прибыль;

s l2 - первый трейдер работает с прибылью, деятельность второго изучается руководством компании;

5 13 - первый трейдер работает с прибылью, второй восстанавливает прибыльную деятельность отдела;

s 2l - деятельность первого трейдера изучается руководством, второй работает с прибылью;

s 22 - деятельность обоих трейдеров изучается руководством;

5 23 - работа первого трейдера изучается, второй трейдер восстанавливает прибыльную деятельность отдела;
5 31 - первый трейдер восстанавливает прибыльную деятельность отдела, второй работает с прибылью;
5 32 - прибыльная деятельность отдела восстанавливается первым трейдером, работа второго трейдера изучается;
5 33 - оба трейдера восстанавливают прибыльную работу своего отдела.

Всего девять состояний. Граф состояний показан на рис. 4.5.

Лекция 9

Марковские процессы
Лекция 9
Марковские процессы

1

Марковские процессы

Марковские процессы
Случайный процесс, протекающий в системе, называется
марковским, если он обладает отсутствием последствия. Т.е.
если рассматривать текущее состояние процесса (t 0) - как
настоящее, совокупность возможных состояний { (s),s t} - как
прошлое, совокупность возможных состояний { (u),u t} - как
будущее, то для марковского процесса при фиксированном
настоящем будущее не зависит от прошлого, а определяется
лишь настоящим и не зависит от того, когда и как система
пришла в это состояние.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
2

Марковские процессы

Марковские процессы
Марковские случайные процессы названы по имени выдающегося русского математика А.А.Маркова, впервые начавшего изучение вероятностной связи случайных величин
и создавшего теорию, которую можно назвать "динамикой
вероятностей". В дальнейшем основы этой теории явились
исходной базой общей теории случайных процессов, а также таких важных прикладных наук, как теория диффузионных процессов, теория надежности, теория массового обслуживания и т.д.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
3

Марков Андрей Андреевич Марков Андрей Андреевич Марков Андрей Андреевич

Марковские процессы
Марков Андрей Андреевич
1856-1922
Русский математик.
Написал около 70 работ по
теории
чисел,
теории
приближения функций, теории
вероятностей. Существенно расширил сферу применения закона
больших чисел и центральной
предельной теоремы. Является
основоположником теории случайных процессов.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
4

Марковские процессы

Марковские процессы
На практике марковские процессы в чистом виде обычно
не встречаются. Но имеются процессы, для которых влиянием «предыстории» можно пренебречь, и при изучении
таких процессов можно применять марковские модели. В
настоящее время теория марковских процессов и ее приложения широко применяются в самых различных областях.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
5

Марковские процессы

Марковские процессы
Биология: процессы рождения и гибели - популяции, мутации,
эпидемии.
Физика:
радиоактивные
распады,
теория
счетчиков
элементарных частиц, процессы диффузии.
Химия:
теория
следов
в
ядерных
фотоэмульсиях,
вероятностные модели химической кинетики.
Images.jpg
Астрономия: теория флуктуационной
яркости млечного пути.
Теория массового обслуживания: телефонные станции,
ремонтные мастерские, билетные кассы, справочные бюро,
станочные и другие технологические системы, системы управления
гибких производственных систем, обработка информации серверами.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
6

Марковские процессы

Марковские процессы
Пусть в настоящий момент t0 система находится в
определенном состоянии S0. Мы знаем характеристики
состояния системы в настоящем и все, что было при t < t0
(предысторию процесса). Можем ли мы предсказать будущее,
т.е. что будет при t > t0?
В точности – нет, но какие-то вероятностные характеристики
процесса в будущем найти можно. Например, вероятность того,
что через некоторое время
система S окажется в состоянии
S1 или останется в состоянии S0 и т.д.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
7

Марковские процессы. Пример.

Марковские процессы
Марковские процессы. Пример.
Система S – группа самолетов, участвующих в воздушном бою. Пусть x – количество
«красных» самолетов, y – количество «синих» самолетов. К моменту времени t0 количество сохранившихся (не сбитых) самолетов
соответственно – x0, y0.
Нас интересует вероятность того, что в момент времени
t 0 численный перевес будет на стороне «красных». Эта вероятность зависит от того, в каком состоянии находилась система
в момент времени t0, а не от того, когда и в какой последовательности погибали сбитые до момента t0 самолеты.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
8

Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
Марковский процесс с конечным или счетным числом
состояний и моментов времени называется дискретной
цепью Маркова. Переходы из состояния в состояние возможны только в целочисленные моменты времени.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
9

10. Дискретные цепи Маркова. Пример

Марковские процессы

Предположим,
что
речь
идет
о
последовательных бросаниях монеты при
игре "в орлянку"; монета бросается в
условные моменты времени t =0, 1, ... и на
каждом шаге игрок может выиграть ±1 с
одинаковой
вероятностью
1/2,
таким
образом в момент t его суммарный выигрыш есть случайная величина ξ(t) с возможными значениями j = 0, ±1, ... .
При условии, что ξ(t) = k, на следующем шаге выигрыш будет
уже равен ξ(t+1) = k ± 1, принимая значения j = k ± 1 c одинаковой вероятностью 1/2. Можно сказать, что здесь с соответствующей вероятностью происходит переход из состояния ξ(t) = k в состояние ξ(t+1) = k ± 1.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
10

11. Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
Обобщая этот пример, можно представить себе систему со
счетным числом возможных состояний, которая с течением
дискретного времени t = 0, 1, ... случайно переходит из состояния в состояние.
Пусть ξ(t) есть ее положение в момент t в результате цепочки случайных переходов
ξ(0) -> ξ(1) -> ... -> ξ(t) -> ξ(t+1) ->...-> ... .
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
11

12. Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
При анализе случайных процессов с дискретными состояниями удобно пользоваться геометрической схемой – графом
состояний. Вершины графа – состояния системы. Дуги графа
– возможные переходы из состояния в состояние.
Игра «в орлянку».
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
12

13. Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
Обозначим все возможные состояния целыми i = 0, ±1, ...
Предположим, что при известном состоянии ξ(t) =i на следующем шаге система переходит в состояние ξ(t+1) = j с условной вероятностью
P{ (t 1) j (t) i}
независимо от ее поведения в прошлом, точнее, независимо
от цепочки переходов до момента t:
P{ (t 1) j (t) i; (t 1) it 1;...; (0) i0 }
P{ (t 1) j (t) i}
Это свойство называется марковским.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
13

14. Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
Число
pij P{ (t 1) j (t) i}
называется вероятностью
перехода системы из состояния i в состояние j за один шаг в
момент времени t 1.
Если переходная вероятность не зависит от t , то цепь
Маркова называется однородной.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
14

15. Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
Матрица P , элементами которой являются вероятности
перехода pij , называется переходной матрицей:
p11 ... p1n
P p 21 ... p 2n
p
n1 ... p nn
Она является стохастической, т.е.
pij 1 ;
i
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
p ij 0 .
15

16. Дискретные цепи Маркова. Пример

Марковские процессы
Дискретные цепи Маркова. Пример
Матрица переходов для игры «в орлянку»
...
k 2
k 2
0
k 1
1/ 2
k
0
k 1
k
k 1
k 2
0
1/ 2
0
0
1/ 2
0
1/ 2
0
1/ 2
0
0
0
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
...
k 1 k 2
0
0
0
1/ 2
0
1/ 2
...
0
0
1/ 2
0
16

17. Дискретные цепи Маркова. Пример

Марковские процессы
Дискретные цепи Маркова. Пример
Садовник в результате химического анализа почвы оценивает
ее состояние одним из трех чисел - хорошее (1), удовлетворительное (2) или плохое (3). В результате наблюдений на протяжении многих лет садовник заметил,
что продуктивность почвы в текущем
году зависит только от ее состояния в
предыдущем году. Поэтому вероятности
перехода почвы из одного состояния в
другое можно представить следующей
цепью Маркова с матрицей P1:
0.20 0.50 0.30
0.00 0.50 0.50
0.00 0.00 1.00
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
17

18. Дискретные цепи Маркова. Пример

Марковские процессы
Дискретные цепи Маркова. Пример
Однако в результате агротехнических мероприятий садовник может изменить переходные вероятности в матрице P1.
Тогда матрица P1 заменится
на матрицу P2:
0.30 0.60 0.10
0.10 0.60 0.30
0.05 0.40 0.55
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
18

19. Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
Рассмотрим, как изменяются состояния процесса с течением времени. Будем рассматривать процесс в последовательные моменты времени, начиная с момента 0. Зададим начальное распределение вероятностей p(0) { p1 (0),..., pm (0)} , где m число состояний процесса, pi (0) - вероятность нахождения
процесса в состоянии i в начальный момент времени. Вероятность pi (n) называется безусловной вероятностью состояния
i в момент времени n 1.
Компоненты вектора p (n) показывают, какие из возможных состояний цепи в момент времени n являются наиболее
вероятными.
m
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
pk (n) 1
k 1
19

20. Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
Знание последовательности { p (n)} при n 1,... позволяет составить представление о поведении системы во времени.
В системе с 3-мя состояниями
p11 p12 p13
P p21
p
31
p22
p32
p23
p33
p2 (1) p1 (0) p12 p2 (0) p22 p3 (0) p32
p2 (n 1) p1 (n) p12 p2 (n) p22 p3 (n) p32
В общем случае:
p j (1) pk (0) pkj
p j (n 1) pk (n) pkj
k
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
k
p(n 1) p(n) P
20

21. Дискретные цепи Маркова. Пример

Марковские процессы
Дискретные цепи Маркова. Пример
Матрица
0.20 0.50 0.30
0.00 0.50 0.50
0.00 0.00 1.00
Шаг
{ p (n)}
n
0
1, 0, 0
n
1
0.2 , 0.5 , 0.3
n
2
0.04 , 0.35 , 0.61
n
3
0.008 , 0.195 , 0.797
n
4
0.0016 , 0.1015 , 0.8969
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
21

22. Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
n
Матрица перехода за n шагов P(n) P .
0.20 0.50 0.30
0.00 0.50 0.50
0.00 0.00 1.00
p(2) p(0) P
2
p (2)
P(2) P 2
1, 0, 0
0.0016
0.
0.
0.0016
0.
0.
0.1015
0.0625
0.
0.1015
0.0625
0.
0.8969
0.9375
1.
0.8969
0.9375
1.
0.04 , 0.35 , 0.61
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
22

23. Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
Как ведут себя марковские цепи при n ?
Для однородной марковской цепи при определенных условиях выполняется следующее свойство: p (n) при n .
Вероятности 0 не зависят от начального распределения
p(0) , а определяются только матрицей P . В этом случае называется стационарным распределением, а сама цепь – эргодической. Свойство эргодичности означает, что по мере увеличения n
вероятность состояний практически перестаёт изменяться, а система переходит в стабильный режим функционирования.
i
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
23

24. Дискретные цепи Маркова. Пример

Марковские процессы
Дискретные цепи Маркова. Пример
0.20 0.50 0.30
0.00 0.50 0.50
0.00 0.00 1.00
0 0 1
P() 0 0 1
0 0 1
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
p () (0,0,1)
24

25. Дискретные цепи Маркова. Пример

Марковские процессы
Дискретные цепи Маркова. Пример
0.30 0.60 0.10
0.10 0.60 0.30
0.05 0.40 0.55
0.1017 0.5254 0.3729
P() 0.1017 0.5254 0.3729
0.1017 0.5254 0.3729
p () (0.1017,0.5254,0.3729)
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
25

26. Марковские процессы с непрерывным временем

Марковские процессы

Процесс называется процессом с непрерывным временем, если
моменты возможных переходов из состояния в состояние не фиксированы заранее, а неопределенны, случайны и могут произойти
в любой момент.
Пример. Технологическая система S состоит из двух устройств,
каждое из которых в случайный момент времени может выйти из
строя, после чего мгновенно начинается ремонт узла, тоже продолжающийся заранее неизвестное, случайное время.
Возможны следующие состояния системы:
S0 - оба устройства исправны;
S1 - первое устройство ремонтируется, второе исправно;
S2 - второе устройство ремонтируется, первое исправно;
S3 - оба устройства ремонтируются.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
26

27. Марковские процессы с непрерывным временем

Марковские процессы
Марковские процессы с непрерывным временем
Переходы системы S из состояния в состояние происходят
практически мгновенно, в случайные моменты выхода из строя
того или иного устройства или
окончания ремонта.
Вероятностью одновременного
выхода из строя обоих устройств
можно пренебречь.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
27

28. Потоки событий

Марковские процессы
Потоки событий
Поток событий – последовательность однородных событий, следующих одно за другим в какие-то случайные моменты времени.
– это среднее число событий,
Интенсивность потока событий
приходящееся на единицу времени.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
28

29. Потоки событий

Марковские процессы
Потоки событий
Поток событий называется стационарным, если его вероятностные характеристики не зависят от времени.
В частности, интенсивность
стационарного потока постоянна. Поток событий неизбежно имеет сгущения или разрежения, но они не носят закономерного характера, и среднее число событий, приходящееся на единицу времени, постоянно и от времени не зависит.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
29

30. Потоки событий

Марковские процессы
Потоки событий
Поток событий называется потоком без последствий, если для
любых двух непересекающихся участков времени и число событий, попадающих на один из них, не зависит от того, сколько событий попало на другой. Другими словами, это означает, что события, образующие поток, появляются в те или иные моменты
времени независимо друг от друга и вызваны каждое своими собственными причинами.
Поток событий называется ординарным, если вероятность появления на элементарном участке t двух и более событий пренебрежимо мала по сравнению с вероятностью появления одного
события, т.е. события в нем появляются поодиночке, а не группами по нескольку сразу
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
30

31. Потоки событий

Марковские процессы
Потоки событий
Поток событий называется простейшим (или стационарным пуассоновским), если он обладает сразу тремя свойствами: 1) стационарен, 2) ординарен, 3) не имеет последствий.
Простейший поток имеет наиболее простое математическое описание. Он играет среди потоков такую же особую
роль, как и закон нормального распределения среди других
законов распределения. А именно, при наложении достаточно большого числа независимых, стационарных и ординарных
потоков (сравнимых между собой по интенсивности) получается поток, близкий к простейшему.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
31

32. Потоки событий

Марковские процессы
Потоки событий
Для простейшего потока с интенсивностью
интервал
времени T между соседними событиями имеет показательное
распределение с плотностью
p(x) e x , x 0 .
Для случайной величины T, имеющей показательное распределение, математическое ожидание есть величина, обратная параметру.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
32

33. Марковские процессы с непрерывным временем

Марковские процессы
Марковские процессы с непрерывным временем
Рассматривая процессы с дискретными состояниями и непрерывным временем, можно считать, что все переходы системы S из состояния в состояние происходят под действием
простейших потоков событий (потоков вызовов, потоков отказов, потоков восстановлений и т.д.).
Если все потоки событий, переводящие систему S из состояния в состояние простейшие, то процесс, протекающий в
системе, будет марковским.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
33

34. Марковские процессы с непрерывным временем

Марковские процессы
Марковские процессы с непрерывным временем
Пусть на систему, находящуюся в состоянии, действует
простейший поток событий. Как только появится первое событие этого потока, происходит «перескок» системы из состояния
в состояние.
- интенсивность потока событий, переводящий систему
из состояния
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
в
.
34

35. Марковские процессы с непрерывным временем

Марковские процессы
Марковские процессы с непрерывным временем
Пусть рассматриваемая система S имеет
возможных состояний
. Вероятность p ij (t) является вероятностью перехода из состояния i в состояние j за время t.
Вероятность i - го состояния
- это вероятность того,
что в момент времени t система будет находиться в состоянии
. Очевидно, что для любого момента времени сумма
всех вероятностей состояний равна единице:
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
35

36. Марковские процессы с непрерывным временем

Марковские процессы
Марковские процессы с непрерывным временем
Для нахождения всех вероятностей состояний
как
функций времени составляются и решаются дифференциальные уравнения Колмогорова – особого вида уравнения, в которых неизвестными функциями являются вероятности состояний.
Для переходных вероятностей:
p ij (t) p ik (t) kj
k
Для безусловных вероятностей:
p j (t) p k (t) kj
k
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
36

37. Колмогоров Андрей Николаевич

Марковские процессы
Колмогоров Андрей Николаевич
1903-1987
Великий русский
математик.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
37

38. Марковские процессы с непрерывным временем

Марковские процессы
Марковские процессы с непрерывным временем
- интенсивности потока отказов;
- интенсивности потока восстановлений.
Пусть система находится в состоянии
S0. В состояние S1 ее переводит поток
отказов первого устройства. Его интенсивность равна
где
- среднее время безотказной работы устройства.
Из состояния S1 в S0 систему переводит поток восстановлений
первого устройства. Его интенсивность равна
где
- среднее время ремонта первого станка.
Аналогично вычисляются интенсивности потоков событий, переводящих систему по всем дугам графа.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
38

39. Системы массового обслуживания

Марковские процессы

Примеры систем массового обслуживания (СМО): телефонные станции, ремонтные мастерские,
билетные
кассы,
справочные
бюро,
станочные и другие технологические системы,
системы
управления
гибких
производственных систем,
обработка информации серверами и т.д.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
39

40. Системы массового обслуживания

Марковские процессы
Системы массового обслуживания
СМО состоит из какого – то количества обслуживающих
единиц, которые называются каналами обслуживания (это
станки, роботы, линии связи, кассиры и т.д.). Всякая СМО
предназначена для обслуживания потока заявок (требований), поступающих в случайные моменты времени.
Обслуживание заявки продолжается случайное время, после чего канал освобождается и готов к приему следующей
заявки.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
40

41. Системы массового обслуживания

Марковские процессы
Системы массового обслуживания
Процесс работы СМО – случайный процесс с дискретными
состояниями и непрерывным временем. Состояние СМО меняется скачком в моменты появления каких - то событий
(прихода новой заявки, окончания обслуживания, момента,
когда заявка, которой надоело ждать, покидает очередь).
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
41

42. Системы массового обслуживания

Марковские процессы
Системы массового обслуживания
Классификация систем массового обслуживания
1. СМО с отказами;
2. СМО с очередью.
В СМО с отказами заявка, поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем не
обслуживается.
В СМО с очередью заявка, пришедшая в момент, когда все каналы заняты, не уходит, а становится в очередь и ожидает возможности быть обслуженной.
СМО с очередями подразделяются на разные виды в зависимости
от того, как организована очередь – ограничена или не ограничена. Ограничения могут касаться как длины очереди, так и времени
ожидания, «дисциплины обслуживания».
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
42

43. Системы массового обслуживания

Марковские процессы
Системы массового обслуживания
Предмет теории массового обслуживания – построение
математических моделей, связывающих заданные условия
работы СМО (число каналов, их производительность, правила
работы, характер потока заявок) с интересующими нас характеристиками – показателями эффективности СМО. Эти показатели описывают способность СМО справляться с потоком
заявок. Ими могут быть: среднее число заявок, обслуживаемых СМО в единицу времени; среднее число занятых каналов; среднее число заявок в очереди; среднее время ожидания обслуживания и т.д.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
43

44.

СПАСИБО
ЗА ВНИМАНИЕ!!!
44

45. Построить граф переходов

Марковские процессы
Построить граф переходов
0.30
0.70
0.0
0.10
0.60
0.30
0.50
0.50
0.0
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»

Эволюция которого после любого заданного значения временно́го параметра t {\displaystyle t} не зависит от эволюции, предшествовавшей t {\displaystyle t} , при условии, что значение процесса в этот момент фиксировано («будущее» процесса не зависит от «прошлого» при известном «настоящем»; другая трактовка (Вентцель): «будущее» процесса зависит от «прошлого» лишь через «настоящее»).

Энциклопедичный YouTube

1 / 3

✪ Лекция 15: Марковские случайные процессы

✪ Происхождение марковских цепей

✪ Обобщенная модель марковского процесса

Субтитры

История

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

Основы общей теории марковских процессов с непрерывным временем были заложены Колмогоровым .

Марковское свойство

Общий случай

Пусть (Ω , F , P) {\displaystyle (\Omega ,{\mathcal {F}},\mathbb {P})} - вероятностное пространство с фильтрацией (F t , t ∈ T) {\displaystyle ({\mathcal {F}}_{t},\ t\in T)} по некоторому (частично упорядоченному) множеству T {\displaystyle T} ; и пусть (S , S) {\displaystyle (S,{\mathcal {S}})} - измеримое пространство . Случайный процесс X = (X t , t ∈ T) {\displaystyle X=(X_{t},\ t\in T)} , определённый на фильтрованном вероятностном пространстве, считается удовлетворяющим марковскому свойству , если для каждого A ∈ S {\displaystyle A\in {\mathcal {S}}} и s , t ∈ T: s < t {\displaystyle s,t\in T:s,

P (X t ∈ A | F s) = P (X t ∈ A | X s) . {\displaystyle \mathbb {P} (X_{t}\in A|{\mathcal {F}}_{s})=\mathbb {P} (X_{t}\in A|X_{s}).}

Марковский процесс - это случайный процесс, удовлетворяющий марковскому свойству с естественной фильтрацией .

Для марковских цепей с дискретным временем

В случае, если S {\displaystyle S} является дискретным множеством и T = N {\displaystyle T=\mathbb {N} } , определение может быть переформулировано:

P (X n = x n | X n − 1 = x n − 1 , X n − 2 = x n − 2 , … , X 0 = x 0) = P (X n = x n | X n − 1 = x n − 1) {\displaystyle \mathbb {P} (X_{n}=x_{n}|X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{0}=x_{0})=\mathbb {P} (X_{n}=x_{n}|X_{n-1}=x_{n-1})} .

Пример марковского процесса

Рассмотрим простой пример марковского случайного процесса. По оси абсцисс случайным образом перемещается точка. В момент времени ноль точка находится в начале координат и остается там в течение одной секунды. Через секунду бросается монета - если выпал герб, то точка X перемещается на одну единицу длины вправо, если цифра - влево. Через секунду снова бросается монета и производится такое же случайное перемещение, и так далее. Процесс изменения положения точки («блуждания ») представляет собой случайный процесс с дискретным временем (t=0, 1, 2, …) и счетным множеством состояний. Такой случайный процесс называется марковским, так как следующее состояние точки зависит только от настоящего (текущего) состояния и не зависит от прошлых состояний (неважно, каким путём и за какое время точка попала в текущую координату).

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

Функция X(t) называется случайной, если ее значение при любом аргументе t является случайной величиной.

Случайная функция X(t) , аргументом которой является время, называетсяслучайным процессом .

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

Определение. Случайный процесс, протекающий в какой-либо системе S , называется марковским (или процессом без последействия), если он обладает следующим свойством: для любою момента времени t 0 вероятность любого состояния системы в будущем (при t > t 0 ) зависит только от ее состояния в настоящем (при t = t 0 ) и не зависит от того, когда и каким образом система S пришла в это состояние. То есть в марковском случайном процессе будущее развитие процесса не зависит от его предыстории.

Классификация марковских процессов. Классификация марковских случайных процессов производится в зависимости от непрерывности или дискретности множества значений функции X(t) и параметра t . Различают следующие основные виды марковских случайных процессов:

· с дискретными состояниями и дискретным временем (цепь Маркова);

· с непрерывными состояниями и дискретным временем (марковские последовательности);

· с дискретными состояниями и непрерывным временем (непрерывная цепь Маркова);

· с непрерывным состоянием и непрерывным временем.

Здесь будут рассматриваться только марковские процессы с дискретными состояниями S 1 , S 2 ,…, S n . То есть эти состояния можно перенумеровать одно за другим, а сам процесс состоит в том, что система случайным образом скачком меняет свое состояние.

Граф состояний. Марковские процессы с дискретными состояниями удобно иллюстрировать с помощью так называемого графа состояний (рис. 1.1.), где квадратиками обозначены состояния S 1 , S 2 , ... системы S , а стрелками - возможные переходы из состояния в состояние. На графе отмечаются только непосредственные переходы, а не переходы через другие состояния. Возможные задержки в прежнем состоянии изображают «петлей», т. е. стрелкой, направленной из данного состояния в него же. Число состояний системы может быть как конечным, так и бесконечным (но счетным).

Рис. 3.1. Граф состояний системы S

Задача 1. Система S – автомобиль, которая может находиться в одном из пяти состояний.

S 1 – исправна, работает;

S 2 – неисправна, ожидает осмотра;

S 3 –осматривается;

S 4 – ремонтируется;

S 5 – списана.

Построить граф состояний системы.

Задача 2. Техническое устройство S состоит из 2-х узлов: 1 и 2, каждый из которых может в любой момент времени отказать. У каждого узла может быть только 2 состояния. 1 – исправен, 2 – неисправен. Построить граф состояний системы.

Задача 3. Построить граф состояний в условиях предыдущей задачи, предполагая, что ремонт узлов в ходе процесса не производится.

Задача 4. Техническое устройство S состоит из 2-х узлов: 1 и 2, каждый из которых может в любой момент времени отказать. Каждый узел, перед тем как начать восстанавливаться подвергается осмотру с целью локализации неисправности. Состояния системы нумеруются 2-мя индексами: S ij (i – состояния первого узла, j – состояния второго узла). У каждого узла три состояния (работает, осматривается, восстанавливается).

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

Случайный процесс протекающий в системе называется Марковским – если для любого момента времени ,вероятностные характеристики процесса в будущем (t > ) зависят только от его состояния в данный момент времени (в настоящем ) и не зависят от того, когда и как система пришла в это состояние в прошлом .(Например, счетчик Гейгера, регистрирующий число космических частиц).

Марковские процессы принято делить на 3 вида:

1. Марковская цепь – процесс, состояния которого дискретны (т.е. их можно перенумеровать), и время, по которому он рассматривается, также дискретно (т.е. процесс может менять свои состояния только в определенные моменты времени). Такой процесс идет (изменяется) по шагам (иначе - по тактам).

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

3. Непрерывный марковский процесс – множество состояний и время -непрерывные.

На практике Марковские процессы в чистом виде встречаются не часто. Однако нередко приходится иметь место с процессами, для которых влиянием предыстории можно пренебречь. Кроме того, если все параметры из «прошлого»,от которых зависит «будущее» включить в состоянии системы в «настоящем», то ее также можно рассматривать как Марковскую. Однако это часто приводит к значительному росту числа учитываемых переменных и невозможности получить решение задачи.

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

Процесс называется процессом с дискретными состояниями , если все его возможные состояния , ,... можно заранее перечислить (перенумеровать). Переход системы из состояния в состояние переходит практически мгновенно –скачком.

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

Например : Техническое устройство S состоит из двух узлов , каждый из которых в случайный момент времени может выйти из строя (отказать ). После этого мгновенно начинается ремонт узла (восстановление ),который продолжается случайное время.

Возможны следующие состояния системы:

Оба узла исправны;

Первый узел ремонтируется,второй исправен.

– второй узел ремонтируется,первый исправен

Оба узла ремонтируются.

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

Состояния

Переходы

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

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

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

Используя размеченный граф состояний системы можно построить математическую модель данного процесса.

Рассмотрим переходы системы из некоторого состояния в предыдущее или последующее . Фрагмент графа состояний в этом случае будет выглядеть следующим образом:

Пусть система в момент времени t находится в состоянии .

Обозначим (t)- вероятность i-ого состояния системы – вероятность того, что система в момент времени t находится в состоянии . Для любого момента времени t справедливо =1.

Определим вероятность того, что и в момент времени t+∆t система будет находиться в состоянии . Это может быть в следующих случаях:

1) и за время ∆ t из него не вышла. Это означает, что за время ∆t не возникло события, переводящего систему в состояние (поток с интенсивностью ) или события, переводящего её в состояние (поток с интенсивностью ). Определим вероятность этого при малых ∆t.

При экспоненциальном законе распределения времени между двумя соседними требованиями, соответствующему простейшему потоку событий вероятность того, что на интервале времени ∆t не возникнет ни одного требования в потоке с интенсивностью λ 1 будет равна

Разлагая функцию f(t) в ряд Тейлора (t>0) получим (для t=∆t)

f(∆t)=f(0)+ (0)* ∆t + *∆ + *∆ +…=

= +(-l) *∆t+ (∆ + *(∆ +…»1-l*∆t при ∆t®0

Аналогично для потока с интенсивностью λ 2 получим .

Вероятность, что на интервале времени ∆t (при ∆t®0) не возникнет ни одного требования будет равна

(∆t)/ = (∆t/ * (∆t/ = (1- *∆t)(1- *∆t) =

1 - - *∆t + 1 - ( + )*∆t + б.м.

Таким образом, вероятность того, что система за время ∆t не вышла из состояния , при малых ∆t будет равна

P( / )=1 – ( + )* ∆t

2) Система находилась в состоянии S i -1 и за время перешла в состояние S i . То есть в потоке с интенсивностью возникло хотя бы одно событие. Вероятность этого равна для простейшего потока с интенсивностью λ будет

Для нашего случая вероятность такого перехода будет равна

3)Система находилась в состоянии и за время ∆tперешла в состояние . Вероятность этого будет

Тогда вероятность, что система в момент времени (t+∆t) будет в состоянии S i равна

Вычтем из обеих частей P i (t), разделим на ∆tи, перейдя к пределу, при ∆t→0, получим

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

Данные уравнения называются уравнениями Колмогорова-Чепмена для дискретного марковского процесса.

Задав начальные условия (например, P 0 (t=0)=1,P i (t=0)=0 i≠0) и решив их, получим выражения для вероятностей состояния системы как функций времени. Аналитические решения достаточно просто получить, если число уравнений ≤ 2,3. Если их больше, то обычно решают уравнения численно- на ЭВМ (например методом Рунге-Кутта).

В теории случайных процессов доказано , что если число n состояний системы конечно и из каждого из них можно (за конечное число шагов) перейти в любое другое, то существует предел , к которому стремятся вероятности при t→ . Такие вероятности называются финальными вероятностями состояний, а установившийся режим - стационарным режимом функционирования системы.

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

Пример. Пусть в нашей системе интенсивности отказов и восстановления элементов следующие

Отказы 1эл:

2эл:

Ремонт 1эл:

2эл:

P 0 +P 1 +P 2 +P 3 =1

0=-(1+2)P 0 +2P 1 +3 P 2

0=-(2+2)P 1 +1P 0 +3P 3

0=-(1+3)P 2 +2P 0 +2P 3

0=-(2+3)P 3 +2P 1 +1P 2

Решив данную систему, получим

P 0 =6/15=0.4; P 1 =3/15=0.2; P 2 =4/15=0.27; P 3 =2/15≈0.13.

Т.е. в стационарном состоянии система в среднем

40% находится в состоянии S 0 (оба узла исправны),

20%- в состоянии S 1 (1-й эл-т ремонтируется, 2-й исправен),

27%- в состоянии S 2 (2-й эл-тремонтируется, 1исправен),

13%- в состоянии S 3 – оба эл-та в ремонте.

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

Пусть система в состоянии S 0 приносит доход 8 усл.ед. в единицу времени; в состоянии S 1 -доход 3 усл.ед.; в состоянии S 2 - доход 5;в состоянии S 3 -доход=0

Стоимость ремонта в единицу времени для эл-та 1- 1(S 1, S 3) усл.ед., эл-та 2- (S 2, S 3) 2 усл.ед. Тогда в стационарном режиме:

Доход системы в единицу времени будет:

W дох =8P 0 +3P 1 +5P 2 +0P 3 =8·0.4+3·0.2+5·0.27+0·0.13=5.15 усл.ед.

Стоимость ремонта в ед. времени:

W рем =0P 0 +1P 1 +2P 2 +(1+2)P 3 =0·0.4+1·0.2+2·0.27+3·0.13=1.39 усл.ед.

Прибыль в единицу времени

W= W дох -W рем =5.15-1.39=3.76 усл.ед

Проведя определённые расходы можно изменить интенсивности λи μ и, соответственно, эффективность системы. Целесообразность таких расходов можно оценить, проведя пересчёт P i . и показателей эффективности системы.