55 1
2
( )
( ) ...
( ) ...
( ) 1
i
n
p k
p k
p k
p k
поскольку
( ),
1,
i
p k
i
n
, представляют собой вероятности появления полной группы событий.
Вероятности
( ),
1,
i
p k
i
n
называются вероятностями состояния.
Для любого шага (момента времени t
1
, t
2
, ... t
k
, ... или номера 1,
2, ... , k, ...) существуют некоторые вероятности перехода системы из любого состояния в любое другое (некоторые из них равны нулю, если непосредственный переход за один шаг невозможен), а также вероятность задержки системы в данном состоянии. Эти вероятности называются переходными вероятностями марковской цепи.
Если значения переходных вероятностей не зависят от номера шага, то марковская цепь называется однородной, или стационарной.
В противном случае марковская цепь является неоднородной, или
нестационарной.
Если из состояния S
i
не исходит ни одной стрелки (переход из него ни в какое другое состояние невозможен, например, S
3
графа рис. 8), соответствующая вероятность задержки Р
ii
равна единице.
Графу системы, содержащему n вершин, можно поставить в соответствие матрицу n×n, элементами которой являются вероятности переходов pij между вершинами графа, называемую матрицей
вероятностей переходов:
11 12 1
1 21 22 2
2 1
2 1
2
(
)
j
n
j
n
ij
i
i
ij
in
n
n
nj
nn
P
P
P
P
P
P
P
P
P
P
P
P
P
P
P
P
P
P
(1)
Элементы матрицы переходов, означающие вероятности переходов в системе за один шаг, удовлетворяют условиям:
0 1
ij
p
(2)
1 1
n
ij
j
p
(3)
Условие (2) выражает ограничение, накладываемое на значение вероятности, а условие (3) означает, что система S обязательно либо переходит из какого-то состояния Si в другое состояние, либо остается в
56 состоянии Si (иначе говоря, события
( )
( )
( )
( )
1 2
,
, ...
, ...
k
k
k
k
i
n
S
S
S
S
образуют
полную группу событий).
Обычно на графе вероятности перехода системы из одного состояния в то же самое не отмечаются, так как каждая из них дополняет до единицы сумму переходных вероятностей, соответствующих всем стрелкам, исходящим из данного состояния. Например, для графа рис. 8 б значения переходных вероятностей
ii
P будут равны:
11 12 13 1 (
)
P
P
P
22 23 24 25 1 (
)
P
P
P
P
33 1
P
44 45 1
P
P
55 53 1
P
P
При рассмотрении конкретных систем удобно сначала построить граф состояний, затем определить вероятность переходов системы из одного состояния в то же самое (исходя из требования равенства единице суммы элементов строк матрицы), а потом составить матрицу переходов системы.
Имея размеченный ГСП (или, что равносильно, матрицу переходных вероятностей) и зная начальное состояние системы, можно найти вероятности состояний р
1
(k), р
2
(k), ... , р
n
(k) после любого (k-го) шага. Они находятся с помощью следующих рекуррентных соотношений:
1
( )
(
1)
(
1,... )
n
i
j
ji
j
p k
p k
P
i
n
(4) или в матричной форме
(k)
(k-1)
p =p
×P ,
(5) где
(k)
p ,
(k-1)
p
- матрицы-строки вероятностей состояний после k-го и
(k-1)-го шагов соответственно;
P - матрица переходных вероятностей.
57
Предположим, что в начальный момент (перед первым шагом) система находится в каком-то определенном состоянии, например S
m
Тогда для начального момента (0) будем иметь:
р
1
(0) =0, р
2
(0) =0, ..., р
m
(0) = 1, ... , р
n
(0) = 0 ,
т. е. вероятности всех состояний равны нулю, кроме вероятности начального состояния S
m
, равной единице.
Найдем вероятности состояний после первого шага. Мы знаем, что перед первым шагом система заведомо находится в состоянии S
m
. Значит, за первый шаг она перейдет в состояния S
1
, S
2
, ... , S
m
, ... , S
n
с вероятностями
P
m1
, P
m2
, ... , P
mm
, ... , P
mn
,
находящимися в m-ой строке матрицы переходных вероятностей.
Таким образом, вероятности состояний после первого шага будут:
1 1
2 2
(1)
,
(1)
, ... ,
(1)
, ... ,
(1)
m
m
m
mm
n
mn
p
P
p
P
p
P
p
P
(6)
Найдем вероятности состояний после второго шага:
(2)
1 2
( (2),
(2), ... ,
(2), ... ,
(2))
i
n
p
p
p
p
p
Вычислим их по формуле полной вероятности с гипотезами:
после первого шага система была в состоянии S
1
;
после первого шага система была в состоянии S
2
;
после первого шага система была в состоянии S
i
;
после первого шага система была в состоянии Sn.
Вероятности гипотез известны (6), условные вероятности перехода в состояние S
i
- при каждой гипотезе тоже известны и записаны в матрице переходных вероятностей. По формуле полной вероятности получим:
58 1
1 11 2
21 1
2 1
12 2
22 2
1 1
2 2
1 1
2 2
(2)
(1)
(1)
(1)
(2)
(1)
(1)
(1)
(2)
(1)
(1)
(1)
(2)
(1)
(1)
(1)
n
n
n
n
i
i
i
n
ni
n
n
n
n
nn
p
p
P
p
P
p
P
p
p
P
p
P
p
P
p
p
P
p
P
p
P
p
p
P
p
P
p
P
(7) или n
i j
ji j=1
p (2)=
p (1)P , (
1, )
i
n
(8)
Данное выражение может быть записано в векторно-матричной форме:
(2)
(1)
p
p
P
(9)
В формулах (7) –
n i
j ji j=1
p (2)=
p (1)P , (
1, )
i
n
(8) суммирование распространяется формально на все состояния S
1
, S
2
, ... ,
S
m
, ... , S
n
; фактически учитывать надо только те из них, для которых переходные вероятности Pij отличны от нуля, т.е. те состояния, из которых может совершиться переход в состояние S
l
(или задержка в нем).
Таким образом, вероятности состояний после второго шага известны. Очевидно, после третьего шага они определяются аналогично:
1
(3)
(2)
(
1,... )
n
i
j
ji
j
p
p
P
i
n
(10)
И вообще после k-то шага:
1
( )
(
1)
(
1,... )
n
i
j
ji
j
p k
p k
P
i
n
(11)
Или в матричной форме
( )
( -1)
k
k
p
p
P
(12)
59
Таким образом, вероятности
( )
i
p k состояний после k-го шага определяются рекуррентной формулой
( )
( -1)
k
k
p
p
P
(12) через вероятности состояний после (к - 1)-го шага; последние, в свою очередь, — через вероятности состояний после (к - 2)-го шага, и т. д.
Например, пусть требуется найти вероятность перехода системы из состояния S1 в состояние S2 за 3 шага для графа на рис. 9.
Рис. 9. Пример ГСП
Из условия следует, что
1 2
3
(0) 1,
(0)
0,
(0)
0
p
p
p
. Находим вероятности состояния после первого шага:
1
(1)
0,7
p
2
(1)
0,1
p
3
(1)
0,2
p
Вероятности состояния после второго шага:
1 1
11 2
21 3
31
(2)
(1)
(1)
(1)
0,7 0,7 0,1 0,4 0,2 0,2 0,57
p
p
p
p
p
p
p
2 1
12 2
22 3
32
(2)
(1)
(1)
(1)
0,7 0,1 0,1 0,0 0,2 0,5 0,17
p
p
p
p
p
p
p
3 1
13 2
23 3
33
(2)
(1)
(1)
(1)
0,7 0,2 0,1 0,6 0,2 0,3 0,26
p
p
p
p
p
p
p
Вероятность состояния S2 после третьего шага
2
(3)
p
:
2 1
12 2
22 3
32
(3)
(2)
(2)
(2)
0, 57 0,1 0,17 0, 0 0, 26 0, 5 0,187
p
p
p
p
p
p
p
60
Если обозначить через
( )
m
P
матрицу, элементами которой являются вероятности переходов из Si в Sj за m шагов
(
)
m
ij
p
, то справедлива формула:
( )
m
m
P
P
,
(13) где матрица
m
P получается умножением матрицы P саму на себя m раз.
Пусть исходное состояние системы задается вектором
(0)
p
:
(0)
1 1
( ,
,...,
) ,
n
p
p p
p
где
pi, i=1, … n есть вероятность того, что в начальный момент система находится в состоянии Si.
Тогда для нахождения вектора вероятностей состояния системы после m шагов можно воспользоваться формулой:
( )
(0)
( )
m
m
p
p
P
(14)
Воспользуемся приведенными формулами для нахождения вектора состояния системы, изображенной рис. 9, после двух шагов, для случая, когда исходное состояние системы задается вектором
(0)
(0,7;0;0,3)
p
С помощью формулы
( )
( -1)
k
k
p
p
P
(12) находим сначала состояние системы после первого шага
(1)
p :
(1)
(0)
0,7 0,1 0, 2
p =p ×P=(0,7;0;0,3)
0, 4 0
0,6 0, 2 0,5 0,3
(0,7 0,7 0,0 0, 4 0,3 0, 2; 0,7 0,1 0,0 0,0 0,3 0,5; 0,7 0, 2 0,0 0,6 0,3 0,3)
(0,55;0, 22;0, 23)
61 и состояние системы после второго шага
(2)
p
:
(2)
(1)
0,7 0,1 0, 2
p =p ×P=(0,55;0,22;0,23)
0, 4 0
0,6
(0,519;0,17;0,311)
0, 2 0,5 0,3
Тот же результат получается с помощью формулы
( )
(0)
( )
m
m
p
p
P
(14).
Вычислив предварительно величину элементов матрицы
(2)
0,7 0,1 0, 2 0,7 0,1 0, 2 0,57 0,17 0, 26
P = 0, 4 0
0,6 × 0, 4 0
0,6 0, 4 0,34 0, 26 0, 2 0,5 0,3 0, 2 0,5 0,3 0, 4 0,17 0, 43
находим:
(2)
(0)
(2)
0,57 0,17 0, 26
p =p ×P =(0,7;0,0;0,3)
0, 4 0,34 0, 26
(0,519;0,17;0,311)
0, 4 0,17 0, 43
Вопрос 5. Предельные вероятности цепи Маркова.
Матрицы, суммы элементов всех строк которых равны единице, называются стохастическими. Если при некотором n все элементы матрицы Р не равны нулю, то такая матрица переходов называется
регулярной. Другими словами, регулярные матрицы переходов задают цепь Маркова, в которой каждое состояние может быть достигнуто через
n шагов из любого состояния. Такие цепи Маркова так же называются
регулярными.
Известно (теорема о предельных вероятностях), что для регулярной цепи Маркова с n состояниями и матрицей вероятностей перехода Р существует предел
( )
( )
lim
n
n
P
P
62 и матрица
( )
P
имеет вид:
1 2
n
1 2
n
( )
1 2
n p
p
... p p
p
... p
P
=
p p
... p
т.е. состоит из одинаковых строк.
Величины p1, p2, … , pn называются предельными
вероятностями. Эти вероятности не зависят от исходного состояния системы, и вектор вероятности полностью определяется из условий:
p
p P
(или
1
n
i
j
ji
j
p
p P
) и условия нормировки
1
i
p
Пусть требуется найти предельные вероятности для матрицы переходов
0,1 0,9 0,3 0,7
P
Так как
1 2
1
p
p
, получаем:
1 1
2 0,1 0,3
p
p
p
2 1
2 0,9 0,7
p
p
p
1 1
3 1
p
p
1 0,25
p
2 0,75
p
63 и матрица предельных вероятностей:
0, 25 0,75 0, 25 0,75
P
Выводы:
1. Решение многих задач, связанных с анализом процессов и создания систем, основано на рассмотрении протекающих процессов как стохастических. Для оценивания показателей этих процессов и систем применяются аналитические модели.
2. Важным классом случайных процессов является марковский процесс. Марковские процессы протекают в отсутствие предыстории, что значительно упрощает их математическое описание.
3. Для описания процесса с дискретным временем и дискретными состояниями используются граф переходов и состояний, а также связанная с ним матрица переходных вероятностей. На основе этих элементов можно найти вероятности нахождения процесса в каждом из своих состояний после любого шага, для чего применяются рекуррентные или матричные выражения, которые получены на основе формулы полной вероятности.
4. В случае регулярных цепей Маркова процесс обладает предельными вероятностями нахождения в каждом из своих состояний.
Эти вероятности не зависят от номера шага и могут быть найдены путем решения системы линейных уравнений, получаемой из выражения для предельных вероятностей и нормировочного условия.
Вопросы для самопроверки:
1. Что такое стохастическая система?
2. Какой процесс называется марковским?
3. Как классифицируются марковские процессы?
4. Дайте определение марковского процесса с непрерывным временем и дискретными состояниями.
5. Что такое однородный марковский процесс?
6. Что такое граф состояний и переходов (ГСП) Марковской цепи? Какие бывают ГСП?
7. Что понимается под матрицей переходных вероятностей?
8. Как можно найти вероятность нахождения процесса в определенном состоянии после определенного числа шагов?
9. Что такое нестационарная марковская цепь?
10. Что такое предельные вероятности марковского процесса?
11. Каков физический смысл предельных вероятностей?
12. При каких условиях существуют предельные вероятности состояний марковского процесса?
64 13. Как найти предельные вероятности системы, имеющей стационарный режим?
Литература по теме:
1. Емельянов А.А., Власова Е.А., Дума Р.В. Имитационное моделирование экономических процессов / Под ред. А.А. Емельянова. –
М.: Финансы и статистика, 2009. – 480 с.
2. Теория систем и системный анализ в управлении организациями: Справочник / Под ред. В.Н. Волковой и А.А.
Емельянова. – М.: Финансы.
3. Саати Т.Л. Элементы теории массового обслуживания и еѐ приложения. – М.: Радио и связь, 1965. – 512 с.
Практические задания:
Задание 1.
Постройте матрицу переходов и определите вероятности состояний через три шага процесса для системы, описываемой следующим ГСП:
Вероятности переходов равны Р12=0,3; Р13=0,4; Р13=0,1; Р23=0,1;
Р24=0,2; Р34=0,3.
Производятся три выстрела по цели, которая может находиться в четырех состояниях:
S1 —невредима;
S2 —незначительно повреждена;
S3 —получила существенные повреждения;
S4 —полностью поражена.