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

Лекция 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
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»

Марковские случайные процессы названы по имени выдающегося русского математика А.А. Маркова (1856-1922), впервые начавшего изучение вероятностной связи случайных величин и создавшего теорию, которую можно назвать “динамикой вероятностей”. В дальнейшем основы этой теории явились исходной базой общей теории случайных процессов, а также таких важных прикладных наук, как теория диффузионных процессов, теория надежности, теория массового обслуживания и т.д. В настоящее время теория Марковских процессов и ее приложения широко применяются в самых различных областях таких наук, как механика, физика, химия и др.

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

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

Как указывалось, Марковские случайные процессы относятся к частным случаям случайных процессов (СП). В свою очередь, случайные процессы основаны на понятии случайной функции (СФ).

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

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

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

Нетрудно заметить, что если обозначить состояние и изобразить зависимость, то такая зависимость и будет случайной функцией.

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

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

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

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

С другой стороны, если в случайном процессе состояния дискретны, время непрерывно и свойство последействия сохраняется, то такой случайный процесс называется Марковским процессом с непрерывным временем.

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

Цепь Маркова считается заданной, если заданы два условия.

1. Имеется совокупность переходных вероятностей в виде матрицы:

2. Имеется вектор начальных вероятностей

описывающий начальное состояние системы.

Кроме матричной формы модель Марковской цепи может быть представлена в виде ориентированного взвешенного графа (рис. 1).

Рис. 1

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

1. Невозвратное множество (рис. 2).

Рис.2.

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

2. Возвратное множество (рис. 3).

Рис. 3.

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

3. Эргодическое множество (рис. 4).

Рис. 4.

В случае эргодического множества возможны любые переходы внутри множества, но исключены переходы из множества и в него.

4. Поглощающее множество (рис. 5)

Рис. 5.

При попадании системы в это множество процесс заканчивается.

В некоторых случаях, несмотря на случайность процесса, имеется возможность до определенной степени управлять законами распределения или параметрами переходных вероятностей. Такие Марковские цепи называются управляемыми. Очевидно, что с помощью управляемых цепей Маркова (УЦМ) особенно эффективным становится процесс принятия решений, о чем будет сказано впоследствии.

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

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

Структура и классификация систем массового обслуживания

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

Нередко возникает необходимость в решении вероятностных задач, связанных с системами массового обслуживания (СМО), примерами которых могут быть:

Билетные кассы;

Ремонтные мастерские;

Торговые, транспортные, энергетические системы;

Системы связи;

Общность таких систем выявляется в единстве математических методов и моделей, применяемых при исследовании их деятельности.

Рис. 4.1. Основные сферы применения ТМО

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

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

1. Входящий поток требований.

2. Накопитель (очередь).

3. Приборы (каналы обслуживания).

4. Выходящий поток.

Рис. 4.2. Общая схема систем массового обслуживания

Рис. 4.3. Модель работы системы

(стрелками показаны моменты поступления требований в

систему, прямоугольниками – время обслуживания)

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

В зависимости от правил образования очереди различают следующие СМО:

1) системы с отказами , в которых при занятости всех каналов обслуживания заявка покидает систему необслуженной;

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

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

Рассмотрим характеристики входящего потока требований.

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

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

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

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

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

Для стационарного потока интенсивность постоянна. Если τ – среднее значение интервала времени между двумя соседними заявками, то В случае пуассоновского потока вероятность поступления на обслуживание m заявок за промежуток времени t определяется по закону Пуассона:

Время между соседними заявками распределено по экспоненциальному закону с плотностью вероятности

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

Отношение интенсивности входящего потока к интенсивности потока обслуживания называется загрузкой системы

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

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

Такие процессы бывают двух типов: с дискретным или непрерывным временем.

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

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

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

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

Переходы системы из состояния в состояние происходит под действием каких-то потоков (поток заявок, поток отказов). Если все потоки событий, приводящие систему в новое состояние, – простейшие пуассоновские, то процесс, протекающий в системе, будет марковским, так как простейший поток не обладает последствием: в нем будущее не зависит от прошлого.

Эволюция к-рого после любого заданного значения временного параметра tне зависит от эволюции, предшествовавшей t, при условии, что значение процесса в этот момент фиксировано (короче: "будущее" н "прошлое" процесса не зависят друг от друга при известном "настоящем").

Определяющее М. п. свойство принято наз. марковским; впервые оно было сформулировано А. А. Марковым . Однако уже в работе Л. Башелье можно усмотреть попытку трактовать броуновское движение как М. п., попытку, получившую обоснование после исследований Н. Винера (N. Wiener, 1923). Основы общей теории М. п. с непрерывным временем были заложены А. Н. Колмогоровым .

Марковское свойство. Имеются существенно отличающиеся друг от друга определения М. п. Одним из наиболее распространенных является следующее. Пусть на вероятностном пространстве задан случайный процесс со значениями из измеримого пространства где Т - подмножество действительной оси Пусть N t (соответственно N t ).есть s-алгебра в порожденная величинами X(s).при где Другими словами, N t (соответственно N t ) - это совокупность событий, связанных с эволюцией процесса до момента t(начиная с t). Процесс X(t).наз. марковским процессом, если (почти наверное) для всех выполняется марковское свойство:

или, что то же самое, если для любых

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

В дальнейшем для определенности речь будет идти только о случае Формулы (1) и (2) дают ясную интерпретацию принципа независимости "прошлого" и "будущего" при известном "настоящем", но основанное на них определение М. п. оказалось недостаточно гибким в тех многочисленных ситуациях, когда приходится рассматривать не одно, а набор условий типа (1) или (2), отвечающих различным, хотя и согласованным определенным образом, мерам Такого рода соображения привели к принятию следующего определения (см. , ).

Пусть заданы:

а) измеримое пространство где s-алгебра содержит все одноточечные множества в Е;

б) измеримое пространство снабженное семейством s-алгебр таких, что если

в) функция ("траектория") x t =x t (w), определяющая при любых измеримое отображение

г) для каждых и вероятностная мера на s-алгебре такая, что функция измерима относительно если и

Набор наз. (необрывающимся) марковским процессом, заданным в если -почти наверное

каковы бы ни были Здесь - пространство элементарных событий, - фазовое пространство или пространство состояний, Р(s, x, t, В ) - переходная функция или вероятность перехода процесса X(t). Если Енаделено топологией, а - совокупность борелевских множеств в Е, то принято говорить, что М. п. задан в Е. Обычно в определение М. п. включают требование, чтобы и тогда истолковывается как вероятность при условии, что x s =x.

Возникает вопрос: всякую ли марковскую переходную функцию Р(s, x ; t, В ), заданную в измеримом пространстве можно рассматривать как переходную функцию нек-рого М. п. Ответ положителен, если, напр., Еявляется сепарабельным локально компактным пространством, а - совокупностью борелевских множеств в Е. Более того, пусть Е - полное метрич. пространство и пусть

для любого где

А - дополнение e-окрестности точки х. Тогда соответствующий М. п. можно считать непрерывным справа и имеющим пределы слева (т. е. таковыми можно выбрать его траектории). Существование же непрерывного М. п. обеспечивается условием при (см. , ). В теории М. п. основное внимание уделяется однородным (по времени) процессам. Соответствующее определение предполагает заданной систему объектов а) - г) с той разницей, что для фигурировавших в ее описании параметров sи u теперь допускается лишь значение 0. Упрощаются и обозначения:

Далее, постулируется однородность пространства W, т. е. требуется, чтобы для любых существовало такое что (w) при Благодаря этому на s-алгебре N, наименьшей из s-алгебр в W, содержащих любое событие вида задаются операторы временного сдвига q t , к-рые сохраняют операции объединения, пересечения и вычитания множеств и для к-рых

Набор наз. (необрывающимся) однородным марковским процессом, заданным в если -почти наверное

для Переходной функцией процесса X(t).считается Р(t, x, В ), причем, если нет специальных оговорок, дополнительно требуют, чтобы Полезно иметь в виду, что при проверке (4) достаточно рассматривать лишь множества вида где и что в (4) всегда F t можно заменить s-алгеброй , равной пересечению пополнений F t по всевозможным мерам Нередко в фиксируют вероятностную меру m ("начальное распределение") и рассматривают марковскую случайную функцию где - мера на заданная равенством

М. п. наз. прогрессивно измеримым, если при каждом t>0 функция индуцирует измеримое отображение в где есть s-алгебра

борелевских подмножеств в . Непрерывные справа М. п. прогрессивно измеримы. Существует способ сводить неоднородный случай к однородному (см. ), и в дальнейшем речь будет идти об однородных М. п.

Строго марковское свойство. Пусть в измеримом пространстве задан М. п.

Функция наз. марковским моментом, если для всех При этом множество относят к семейству F t , если при (чаще всего F t интерпретируют как совокупность событий, связанных с эволюцией X(t).до момента т). Для полагают

Прогрессивно измеримый М. п. Xназ. строго марковским процессом (с. м. п.), если для любого марковского момента т и всех и соотношение

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

непрерывна всякий раз, когда f непрерывна и ограничена.

В классе с. м. п. выделяются те или иные подклассы. Пусть марковская переходная функция Р(t, x, В ), заданная в метрическом локально компактном пространстве Е, стохастически непрерывна:

для любой окрестности Uкаждой точки Тогда если операторы переводят в себя класс непрерывных и обращающихся в 0 в бесконечности функций, то функции Р(t, х, В ).отвечает стандартный М. п. X, т. е. непрерывный справа с. м. п., для к-рого

и - почти наверное на множестве а - неубывающие с ростом пмарковские моменты.

Обрывающийся марковский процесс. Нередко физич. системы целесообразно описывать с помощью необрывающегося М. п., но лишь на временном интервале случайной длины. Кроме того, даже простые преобразования М. п. могут привести к процессу с траекториями, заданными на случайном интервале (см. "Функционал" от марковского процесса). Руководствуясь этими соображениями, вводят понятие обрывающегося М. п.

Пусть - однородный М. п. в фазовом пространстве имеющий переходную функцию и пусть существуют точка и функция такие, что при и в противном случае (если нет специальных оговорок, считают ). Новая траектория x t (w) задается лишь для ) посредством равенства a F t определяется как след в множестве

Набор где наз. обрывающимся марковским процессом (о. м. п.), полученным из с помощью обрыва (или убивания) в момент z. Величина z наз. моментом обрыва, или временем жизни, о. м. п. Фазовым пространством нового процесса служит где есть след s-алгебры в Е. Переходная функция о. м. п.- это сужение на множество Процесс X(t).наз. строго марковским процессом, или стандартным марковским процессом, если соответствующим свойством обладает Необрывающийся М. п. можно рассматривать как о. м. п. с моментом обрыва Неоднородный о. м. п. определяется аналогичным образом. М.

Марковские процессы и дифференциальные уравнения. М. п. типа броуновского движения тесно связаны с дифференциальными уравнениями параболич. типа. Переходная плотность р(s, x, t, у ).диффузионного процесса удовлетворяет при нек-рых дополнительных предположениях обратному и прямому дифференциальным уравнениям Колмогорова:

Функция р(s, x, t, у ).есть функция Грина уравнений (6) - (7), и первые известные способы построения диффузионных процессов были основаны на теоремах существования этой функции для дифференциальных уравнений (6) - (7). Для однородного по времени процесса оператор L(s, x ) = L (x).на гладких функциях совпадает с характеристич. оператором М. п. (см. "Переходных операторов полугруппа" ).

Математич. ожидания различных функционалов от диффузионных процессов служат решениями соответствующих краевых задач для дифференциального уравнения (1). Пусть - математич. ожидание по мере Тогда функция удовлетворяет при s уравнению (6) и условию

Аналогично, функция

удовлетворяет при s уравнению

и условию и 2 ( Т, x ) = 0.

Пусть тt - момент первого достижения границы дD области траекторией процесса Тогда при нек-рых условиях функция

удовлетворяет уравнению

и принимает значения ср на множестве

Решение 1-й краевой задачи для общего линейного параболич. уравнения 2-го порядка

при довольно общих предположениях может быть записано в виде

В случае, когда оператор Lи функции с, f не зависят от s, аналогичное (9) представление возможно и для решения линейного эллиптич. уравнения. Точнее, функция

при нек-рых предположениях есть решение задачи

В случае, когдгг оператор Lвырождается (del b(s, х ) = 0 ).или граница дD недостаточно "хорошая", граничные значения могут и не приниматься функциями (9), (10) в отдельных точках или на целых множествах. Понятие регулярной граничной точки для оператора L имеет вероятностную интерпретацию. В регулярных точках границы граничные значения достигаются функциями (9), (10). Решение задач (8), (11) позволяет изучать свойства соответствующих диффузионных процессов и функционалов от них.

Существуют методы построения М. п., не опирающиеся на построение решений уравнений (6), (7), напр. метод стохастических дифференциальных уравнений, абсолютно непрерывная замена меры и др. Это обстоятельство вместе с формулами (9), (10) позволяет вероятностным путем строить и изучать свойства краевых задач для уравнения (8), а также свойства решении соответствующего эллиптич. уравнения.

Так как решение стохастического дифференциального уравнения нечувствительно к вырождению матрицы b(s, x ), то вероятностные методы применялись для построения решений вырождающихся эллиптических и параболических дифференциальных уравнений. Распространение принципа усреднения Н. М. Крылова и Н. Н. Боголюбова на стохастические дифференциальные уравнения позволило с помощью (9) получить соответствующие результаты для эллиптических и параболических дифференциальных уравнений. Нек-рые трудные задачи исследования свойств решений уравнений такого типа с малым параметром при старшей производной оказалось возможным решить с помощью вероятностных соображений. Вероятностный смысл имеет и решение 2-й краевой задачи для уравнения (6). Постановка краевых задач для неограниченной области тесно связана с возвратностью соответствующего диффузионного процесса.

В случае однородного по времени процесса (Lне зависит от s) положительное решение уравнения с точностью до мультипликативной постоянной совпадает при нек-рых предположениях со стационарной плотностью распределения М. п. Вероятностные соображения оказываются полезными и при рассмотрении краевых задач для нелинейных параболич. уравнений. Р. 3. Хасьминский.

Лит. : Марков А. А., "Изв. физ.-мат. об-ва Казан. ун-та", 1906, т. 15, №4, с. 135-56; В а с h e l i е r L., "Ann. scient. Ecole norm, super.", 1900, v. 17, p. 21-86; Колмогоров А. Н., "Math. Ann.", 1931, Bd 104, S. 415- 458; рус. пер.-"Успехи матем. наук", 1938, в. 5, с. 5-41; Ч ж у н К а й - л а й, Однородные цепи Маркова, пер. с англ., М., 1964; Р е 1 1 е r W., "Ann. Math.", 1954, v. 60, p. 417-36; Д ы н к и н Е. Б., Ю ш к е в и ч А. А., "Теория вероятн. и ее примен.", 1956, т. 1, в. 1, с. 149-55; X а н т Дж.-А., Марковские процессы и потенциалы, пер. с англ., М., 1962; Д е л л а ш е р и К., Емкости и случайные процессы, пер. с франц., М., 1975; Д ы н к и н Е. В., Основания теории марковских процессов, М., 1959; его же, Марковские процессы, М., 1963; Г и х м а н И. И., С к о р о х о д А. В., Теория случайных процессов, т. 2, М., 1973; Фрейдлин М. И., в кн.: Итоги науки. Теория вероятностей, математическая статистика. - Теоретическая кибернетика. 1966, М., 1967, с. 7-58; X а с ь м и н с к и й Р. 3., "Теория вероятн. и ее примен.", 1963, т. 8, в . 1, с. 3-25; Вентцель А. Д., Фрейдлин М. И., Флуктуации в динамических системах под действием малых случайных возмущений, М., 1979; Blumenthal R. М., G e t о о r R. К., Markov processes and potential theory, N.Y.- L., 1968; Getоor R. K., Markov processes: Ray processes and right processes, В., 1975; Кузнецов С. Е., "Теория вероятн. и ее примен.", 1980, т. 25, в. 2, с. 389-93.

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

Случайные процессы находят широкое применение при изучении сложных стохастических систем как адекватные математические модели процесса функционирования таких систем.

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

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

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

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

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

Обозначим через g (t ) случайный процесс с дискретными состояниями, а возможные значенияg (t ), т.е. возможные состояния цепи, - через символыE 0 , E 1 , E 2 , … . Иногда для обозначения дискретных состояний используют числа 0, 1, 2,... из натурального ряда.

Случайный процесс g (t ) называетсяпроцессом с дискретным временем , если переходы процесса из состояния в состояние возможны только в строго определенные, заранее фиксированные моменты времениt 0 , t 1 , t 2 , … . Если переход процесса из состояния в состояние возможен в любой, заранее неизвестный момент времени, то случайный процесс называетсяпроцессом с непрерывным временем . В первом случае, очевидно, что интервалы времени между переходами являются детерминированными, а во втором - случайными величинами.

Процесс с дискретным временем имеет место либо, когда структура системы, которая описывается этим процессом, такова, что ее состояния могут изменяться только в заранее определенные моменты времени, либо когда предполагается, что для описания процесса (системы) достаточно знать состояния в определенные моменты времени. Тогда эти моменты можно пронумеровать и говорить о состоянии E i в момент времени t i .

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