Элементы теории Марковских процессов

1. ЭЛЕМЕНТЫ ТЕОРИИ МАРКОВСКИХ ПРОЦЕССОВ

2.

Определим понятия:
Модель
Моделирование

3. Пример для мотивации применения моделирования

4. Глобальная сеть (Wide Area Networks )

5. Проблема: оценка показателей эффективности

Для отдельного узла (маршрутизатора) сети
Пропускная способность
Среднее число пакетов в узле
Среднее время ожидания пакета в узле
Вероятность потери пакетов в узле
Коэффициент использования узла
Для сети
Пропускная способность сети
Задержки в сети
Вероятность потери пакетов в сети
Прогноз показателей производительности сети
Поиск узких мест и их устранение

6. Что такое модель?

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

7. Что такое моделирование?

8. Классификация моделей

9.

10. Математические модели (аналитические и имитационные)

11. Аналитическое моделирование

1. Теория Марковских процессов
2. Теория систем массового
обслуживания (СМО)
3. Операционный анализ (частный
случай СМО)

12. ЭЛЕМЕНТЫ ТЕОРИИ МАРКОВСКИХ ПРОЦЕССОВ

13. Definition and classification of random process

Imagine an example of stochastic process from common stand.
Assume there is a physical system S, which consists of two
devices. Each device can fail at any instance of time. Thus, the
system continues to operate with second device. After
recovering the device is put into the system. The system
continues to operate with two devices. The states of system are
S1- two devices are in the working state; S2 - first device is
failed, second one is in the working state; S3 - first device is in
operation, second one is failed; S4 - two devices are failed.

14.

Let consider a function S(t) which values at some instants
of time t0, t1, t2, …, tk are correspondingly
S1 t0 , S3 t1 , S4 t2 , S5 t3 , ...
It is evident, this function describes a system behavior in
question. A sequence of states is named “trajectory o
process”.

15.

Graphical representation of system
behavior
S
Trajectory І
Trajectory ІІ
Sn
S1 t 0 , S 3 t1 , S 4 t 2 , S 5 t 3 , ...
Sn -1
S1 0 , S3 1 , S4 2 , S5 3 , ...
S5
S4
S3
S2
S1
t
0
1
2
3
4
5 . . . k -1
k
k+ 1

16.

If the system S changes the states (passes from one
state Si to another Sj) in a random way and a change
of states occurs at some instants of time t0, t1, t2, …,
tk, we say that operating of system is described by
the function S(t) which values are random values.
S1 t 0 , S 3 t1 , S 4 t 2 , S 5 t 3 , ...

17.

Definition of a stochastic process
Stochastic process is a function S(t) which values are random
values. In other words, stochastic process is a random function.
For example, the number of requests in the DB waiting line,
states of microprocessor, and so on.

18. Рассмотрим пример

Процессор компьютера в любой заданный момент
времени выполняет команды из: а) программы
пользователя
(состояние
S0);
б)
подпрограммы
операционной системы (ОС), явно вызываемой из
программы пользователя и выполняющей для нее
некоторую задачу (например, операцию по вводу –
выводу) (состояние S1); в) подпрограммы ОС,
выполняющей общесистемную задачу управления,
например, планирование, переключение, распределение
ресурсов или восстановление после сбоя системы
(состояние S2); г ) цикла ожидания (состояние S3).
Требуется
с
использованием
аналитического
моделирования: оценить показатели эффективности)
коэффициент использования процессора и ОС.

19. Графическая интерпретация поведения процессора Возможные траектории процесса

S
Траектория І
Траектория ІІ
Sn
S1 t 0 , S3 t1 , S 4 t 2 , S1 t3 , ...
Sn-1
S1 t0 , S1 t1 , S2 t2 , S5 t3 , ...
S5
S4
S3
S2
S1
t
0
1
2
3
4
5 . . . k -1
k
k+ 1

20. Определение случайных процессов

Рассмотрим пример случайного процесса с общих позиций. Пусть
имеется некоторая физическая система S, которая с течением времени
меняет свое состояние (переходит из одного состояния в другое )
случайным образом. Предположим, смена состояний происходит в
некоторые моменты времени t0, t1, t2, …, tk, …. В этом случае
последовательность состояний может рассматриваться как случайный
процесс. Тогда, случайный процесс, происходящий в системе S,
можно представить как некоторую последовательность состояний,
называемую еще траекторией процесса:
В общем случае, случайный процесс есть функция , значениями
которой являются случайные величины. Значение в конкретный
момент времени представляет собой состояние случайного процесса
в момент

21. Классификация состояний случайных процессов

22. Классификация случайных процессов по времени

23. Рассматриваемые случайные процессы

Дискретное время
Дискретные
состояния
+
дискретные случайные
процессы
Непрерывные
состояния
___
Непрерывное время
+
непрерывные
случайные процессы
___

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

t<t (прошлое)
t>t (будущее)
0
0
0
t (S )
0 0
t

25. Потоки событий. Простейший поток и его свойства

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

Потоком событий называется последовательность однородных
событий, следующих одно за другим в некоторые моменты времени.
T1
t0
T2
t1
t2
t'
t3
t4
t5
t'+
t
а)
T
0
t'+
t'
б)
t

27. Свойства потоков

28. Потоки событий, обладающие некоторыми простыми свойствами (1)

29. Потоки событий, обладающие некоторыми простыми свойствами (2)

30. Распределение Пуассона

распределением Пуассона.
.

31. Распределение Пуассона

32. Простейший поток. Распределения интервала времени Т между соседними событиями

33. Плотность и характеристики экспоненциального распределения

34.

Вероятность появления одного события на
элементарном участке

35. Коэффициент вариации простейшего потока

36. Основные свойства простейшего потока

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

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

38. Формальные средства описания (модель) марковского процесса с дискретными состояниями (Граф состояний)

39. Граф состояний дискретного марковского процесса

S1
S3
S2
S4
Практически, приведенный граф является моделью, которая
иллюстрирует процесс поведения рассматриваемой системы.

40. Формальные средства описания марковского процесса с дискретными состояниями. (Марковская цепь)

41. Графическая интерпретация поведения процессора Возможные траектории процесса

S1 t0 , S1 t1 , S2 t2 , S5 t3 , ...
S
Траектория І
Траектория ІІ
Sn
S1 0 , S1 1 , S 2 2 , S 5 3 , ...
Sn-1
S5
S1 t 0 , S3 t1 , S 4 t 2 , S1 t3 , ...
S4
S3
S2
S1
t
0
1
2
3
4
5 . . . k -1
k
k+ 1

42. Формальные средства описания марковского процесса с дискретными состояниями. Марковская цепь - продолжение

43. Переходная вероятность дискретного МП

44. Матрица переходных вероятностей неоднородного МП

P11 k
Pji k
P12 k P1n k
P21 k P22 k P2 n k
:
:
:
Pn1 k Pn 2 k Pnn k

45. Матрица переходных вероятностей однородного МП

Pji
P11
P12
P1n
P21
P22
P2 n
:
:
Pn1
Pn 2
:
Pnn

46. Свойства матрицы переходных вероятностей

1. переходные вероятности, соответствующие невозможным переходам,
равны нулю.
2. вероятности, расположенные на главной диагонали матрицы,
соответствуют тому факту, что система за один шаг своего состояния не
изменила.
3. сумма членов, стоящих в каждой строке матрицы, равна единице:
n
P
i 1
ji
1,
j 1, n .

47. Размеченный граф состояний

S1
P12
P1 4
P
13
S2
P23
S3
P24
P34
S4

48. Вычисление вероятностей состояний дискретного марковского процесса

49.

S
S1 t0 , S3 t1 , S 4 t2 , S1 t3 , ...
Траектория І
Траектория ІІ
Sn
P1 0 , P3 1 , P4 2 , P1 3 , ...
Sn-1
S1 t0 , S1 t1 , S2 t2 , S5 t3 , ...
S5
S4
S3
S2
S1
t
0
1
2
3
4
5 . . . k -1
k
k+ 1

50. Найдем Рi(1),

i 1, n
P1 1 P1 0 P11 P2 0 P21 ... Pn 0 Pn1 ,
P2 1 P1 0 P12 P2 0 P22 ... Pn 0 Pn 2 ,
.................................................
Pn 1 P1 0 P1n P2 0 P2 n ... Pn 0 Pnn .
или в общем виде для 1- го шага
n
Pi 1 P j 0 P ji
j 1
i 1, n

51. Геометрическая интерпретация определения вероятности состояний ДМП

S
Pn(0)
Pn(1)
Pn(2)
Pn(k)
Pj(2)
Pj(k)
P2(2)
P2(k)
P1(2)
P1(k)
P0(2)
P0(k)
Sn
.
.
.
.
Pj(0)
Pj(1)
Sj
.
.
.
.
Pn1
Pn1
Pj1
Pj1
P2(0)
P2(1)
S2
P11
P1(0)
P11
P1(1)
S1
P01
P0(0)
P01
P0(1)
S0
t
0(t0)
1(t1)
2(t2)
k(tk)

52. Найдем Рi(2),

i 1, n
P1 2 P1 1 P11 P2 1 P21 ... Pn 1 Pn1 ,
P2 2 P1 1 P12 P2 1 P22 ... Pn 1 Pn 2 ,
.................................................
Pn 2 P1 1 P1n P2 1 P2 n ... Pn 1 Pnn .
или в общем виде для 2- го шага
Pi 2
n
P j 1 P ji
j 1
i 1, n

53. Формулу вычисления вероятностей состояния на к-ом шаге для общего случая

n
Pi k Pj k 1 Pji
j 1
i 1, n

54. Пример расчета ДМП

55. Формулы определения вероятностей состояний на 1-ом и 2-ом шаге

n
Pi k Pj k 1 Pji ,
j 1
i 1, n
1-й шаг
в общем виде для 1-го шага:
2
Pi 1 Pj 0 Pji
i 1,2
j 1
P1 1 P1 0 P11 P2 0 P21 ,
P2 1 P1 0 P12 P2 0 P22
2-й шаг
в общем виде для 2-го шага:
2
Pi 2 Pj 1 Pji , i 1,2
j 1
P1 2 P1 1 P11 P2 1 P21 ,
P2 2 P1 1 P12 P2 1 P22

56. Пример расчета ДМП (результат)

57. Предельные вероятности состояний ДМП

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

58. k → ∞

k→∞
K
∞
0
1
2
3
4
P1(К)
0.7
0.32
0.472
0.411
0.436
0.413
0.41
0.41
P2(К)
o.3
0.68
0.528
0.589
0.564
0.585
0.59
0.59
Pi

59.

Теорема Маркова:
Для
эргодических
марковских
процессов
справедлива
теорема Маркова: если в системе протекает эргодический
марковский процесс и число состояний процесса конечно, то
существует
lim P k P
k
i
i
i 1, n

60. Вычисление предельных вероятностей состояния ДМП

Приведенная система уравнений имеет одно линейно зависимое уравнение.
Эта вероятность представляет собой
пребывания системы в данном состоянии.
долю
времени

61. Предельных вероятности состояния

K
Pi
P1(К)
P2(К)
0
1
2
3
4
0.7
o.3
0.32
0.68
0.472
0.528
0.411
0.589
0.436
0.564
Следовательно:
P1 = 0.41
P2 = 0.59
∞
0.413
0.585
0.41
0.59
0.41
0.59

62. Непрерывные марковские процессы

63. Непрерывные марковские процессы

Т.к. для любого момента времени все состояния системы
образуют полную группу несовместных событий, то
n
Pi t 1
i 1

64.

Размеченный граф состояний непрерывного
марковского процесса
S1
12
31
23
24
S2
42
S3
34
S4

65. Уравнения Колмогорова для вероятностей состояний. Вычисление Pi(t)

66. Уравнения Колмогорова для вероятностей состояний (продолжение)

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

67. Правило составления ДУК

68. Пример 1

69. Пример 1 (продолжение)

70. Теорема Маркова для непрерывного марковского процесса.

lim Pi t Pi
Эти вероятности представляют собой долю времени
пребывания системы в соответствующем состоянии

71. Уравнения баланса потоков

Система ЛУ, полученная из системы
ДУК заменой левых частей на 0
Уравнения баланса потоков
Свойство уравнения баланса потоков. Суммарный вероятностный входной поток
состояния равен суммарному вероятностному выходному потоку соответствующего
состоянию

72. Правило составления уравнений баланса потоков

1. Число уравнений равно числу состояний.
2. Левая часть каждого уравнения содержит вероятностный
выходной поток соответствующего состояния, а правая часть
каждого уравнения содержит вероятностный входной поток
соответствующего состояния. Число членов уравнения равно
числу дуг инцидентных соответствующей вершине.
3.
Каждый
интенсивности
член
уравнения
перехода
равен
произведению
соответствующей
дуги
на
предельную вероятность состояния, из которого эта дуга
исходит

73. Вычисление предельных вероятностей состояний

Уравнения баланса потоков представляют собой систему
линейных уравнений. Эта система имеет одно линейно
зависимое
уравнение
множество
решений.
и,
поэтому,
Для
имеет
бесконечное
определения
предельных
вероятностей состояний Pi (i=1,..n) необходимо отбросить
одно
любое
уравнение
нормировочное уравнение:
и
вместо
него
использовать

74. Пример. Задан размеченный граф состояний непрерывного марковского процесса

Определить предельные вероятности
состояний Р0 и Р1

75. Решение

Уравнения баланса потоков:
Нормировочное уравнение:
P0 P1 1.
Решение: отбросим первое уравнение

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

77. Уравнения баланса потоков для схемы гибели и размножения

78. Вычисление предельных вероятностей состояний методом подстановки

Выразим все Pi через P0, для этого: