Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







СЛУЧАЙНЫЕ ПРОЦЕССЫ С ДИСКРЕТНЫМ





И НЕПРЕРЫВНЫМ ВРЕМЕНЕМ.

МАРКОВСКАЯ ЦЕПЬ

 

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

Случайный процесс называется процессом с дискрет­ным временем, если переходы системы из состояния в состояние возможны только в строго определенные, заранее фиксированные мо­менты времени: t1, t2,.... В промежутки времени между этими момен­тами система S сохраняет свое состояние.

Случайный процесс называется процессом с непрерыв­ным временем, если переход системы из состояния в состояние возможен в любой, наперед неизвестный, случайный момент t.

Рассмотрим прежде всего марковский случайный процесс с дискрет­ными состояниями и дискретным временем.

Пусть имеется физическая система S, которая может находиться в состояниях:

S1, S2,..., Sn,

причем переходы («перескоки») системы из состояния в состояние возможны только в моменты:

t1, t2,..., tn, ….

Будем называть эти моменты «шагами» или «этапами» процесса и рассматривать случайный процесс, происходящий в системе S, как функцию целочисленного аргумента: 1, 2,..., k,... (номера шага).

Случайный процесс, происходящий в системе, состоит в том, что и последовательные моменты времени t1, t2, t3,..., система S оказы­вается в тех или других состояниях, ведя себя, например, следую­щим образом:

S1 ® S3 ® S5 ® S4 ® S2 ® S1 ®...

или же

S1 ® S2 ® S1 ® S2 ® S3 ® S4 ® S1 ®....

В общем случае в моменты t1, t2,... система может не только ме­нять состояние, но и оставаться в прежнем, например:

S1 ® S1 ® S2 ® S3 ® S3 ® S3 ® S4 ® S1 ®...

Условимся обозначать Si(k) событие, состоящее в том, что после k шагов система находится в состоянии Si. При любом k события

S1(k), S2(k),..., Si(k),..., Sn(k)

образуют полную группу и несовместны.

Процесс, происходящий в системе, можно представить как после­довательность (цепочку) событий, например:

S1(0), S2(1), S1(2), S2(3), S3(4),...

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

 

 

Мы будем описывать марковскую цепь с помощью так называе­мых вероятностей состояний. Пусть в любой момент времени (после любого, k-ro шага) система S может быть в одном из со­стояний:

S1, S2,..., Sn,

т. е. осуществится одно из полной группы несовместных событий:

S1(k), S2(k),..., Sn(k).

Обозначим вероятности этих событий:

p1(1) = P(S1(1)); p2(1) = P(S2(1)); …; pn(1) = P(Sn(1))

— вероятности после первого шага,

p1(2) = P(S1(2)); p2(2) = P(S2(2)); …; pn(2) = P(Sn(2)) (1)

— вероятности после второго шага; и вообще после k -го шага:

p1(k) = P(S1(k)); p2(k) = P(S2(k)); …; pn(k) = P(Sn(k)) (2)

Легко видеть, что для каждого номера шага k

p1(k) + p2(k) + … + pn(k) = 1,

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

 

Будем называть вероятности

p1(k), p2(k), …, pn(k) вероятностями состояний; поставим задачу: найти ве­роятности состояний системы для любого k.

Изобразим состояния системы в виде графа (рис. 6), где стрелка­ми указаны возможные переходы системы из состояния в состояние за один шаг.

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

S1 ® S3 ® S2 ® S2 ® S3 ® S5 ® S6 ® S2

можно изобразить на графе состояний как последовательность различ­ных положений точки (см. пунктирные стрелки, изображающие пере­ходы из состояния в состояние на рис. 7). «Задержка» системы в со­стоянии S2 на третьем шаге изображена стрелкой, выходящей из со­стояния S2 и в него же возвращающейся.

Для любого шага (момента времени tl, t2,..., tk,... или номера 1, 2,..., k...) существуют какие-то вероятности перехода системы из любого состояния в любое другое (некоторые из них равны нулю, если непосредственный переход за один шаг невозможен), а также вероят­ность задержки системы в данном состоянии.

Будем называть эти вероятности переходными веро­ятностями марковской цепи.

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

 

Рассмотрим сначала однородную марковскую цепь. Пусть система S имеет n возможных состояний S1, S2,..., Sn. Предположим, что для каждого состояния нам известна вероятность перехода в любое другое состояние за один шаг (в том числе и вероятность задержки в данном состоянии). Обозначим Рij вероятность перехода за один шаг из состоя­ния Si в состояние Sj; Рii будет вероятность задержки системы в со­стоянии Si. Запишем переходные вероятности Рij в виде прямоуголь­ной таблицы (матрицы):

(3)

Некоторые из переходных вероятностей Рij могут быть равны ну­лю: это означает, что за один шаг переход системы из i-го состояния в j-е невозможен. По главной диагонали матрицы переходных вероятностей стоят вероятности Рii того, что система не выйдет из состояния Si, а останется в нем.

Пользуясь введенными выше событиями S1(k), S2(k),..., Sn(k), пере­ходные вероятности Pij можно записать как условные вероятности:

Pij = P(Sj(k)/ Si(k-1)).

Отсюда следует, что сумма членов, стоящих в каждой строке мат­рицы (3), должна быть равна единице, так как, в каком бы состоянии система ни была перед k-м шагом, события S1(k), S2(k),..., Sn(k) несовмест­ны и образуют полную группу.

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

Заметим, что на рис. 4.8 проставлены не все переходные вероят­ности, а только те из них, которые не равны нулю и меняют состоя­ние системы, т. е. Рij при i ¹ j; «вероятности задержки» Р11, Р22,... проставлять на графе излишне, так как каждая из них допол­няет до единицы сумму переходных вероятностей, соот­ветствующих всем стрелкам, исходящим из данного состояния. Например, для графа рис. 8

P11 = l - (P12 + P13),

P22 = l - (P23 + P24),

P33 = l - (P32 + P35),

P44 = l - (P43 + P45 + P46),

P55 = l - P56,

P66 = l - P62 .

Если из состояния Si не исходит ни одной стрелки (переход из не­го ни в какое другое состояние невозможен), соответствующая вероят­ность задержки Рii равна единице.

Имея в распоряжении размеченный граф состояний (или, что рав­носильно, матрицу переходных вероятностей) и зная начальное состоя­ние системы, можно найти вероятности состояний

p1(k), p2(k),..., pn(k)

после любого (k - го) шага.

Покажем, как это делается.

Предположим, что в начальный момент (перед первым шагом) си­стема находится в каком-то определенном состоянии, например, Sm. Тогда, для начального момента (0) будем иметь:

p1(0)=0; p2(0)=0;...; pm(0) = l; …; Рn(0)=0,

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

Найдем вероятности состояний после первого шага. Мы знаем, что перед первым шагом система заведомо находится в состоянии Sm. Значит, за первый шаг она перейдет в состояния S1, S2,..., Sm,..., Sn с вероятностями

Pm1, Pm2, …, Pmm, …, Pmn,

записанными в m-й строке матрицы переходных вероятностей. Таким образом, вероятности состояний после первого шага будут:

p1(1) = Pm1; p2(1) = Pm2; …; pm(1) = Pmm; …; pn(1) = Pmn . (4)

Найдем вероятности состояний после второго шага:

pl(2), р2(2),..., рi(2),…, рn(2).

Будем вычислять их по формуле полной вероятности, с гипотезами:

— после первого шага система была в состоянии S1;

— после первого шага система была в состоянии S2;

......................

— после первого шага система была в состоянии Si;

......................

— после первого шага система была в состоянии Sn.

Вероятности гипотез известны (см. (4)); условные вероятности перехода в состояние Si при каждой гипотезе тоже известны и записаны в матрице переходных вероятностей. По формуле полной вероятности получим:

(5)

или, гораздо короче,

(i =1, …, n) (6)

В формуле (6) суммирование распространяется формально на все состояния S1,..., Sn; фактически учитывать надо только те из них, для которых переходные вероятности Рij отличны от нуля, то есть те состояния, из которых может совершиться переход в состоя­ние Si (или задержка в нем).

Таким образом, вероятности состояний после второго шага из­вестны. Очевидно, после третьего шага они определяются аналогично:

(i =1, …, n) (7)

и вообще после k-ro шага:

(i =1, …, n) (8)

Итак, вероятности состояний pi(k) после k-гo шага определяются рекуррентной формулой (8) через вероятности состояний после (k - 1)-го шага; те, в свою очередь - через вероятности состояний после (k - 2)-го шага, и т. д.

 

Пример 1. По некоторой цели ведется стрельба четырьмя выстрелами в моменты времени t1, t2, t3, t4.

Возможные состояния цели (системы S):

S1 - цель невредима;

S2 - цель незначительно повреждена;

S8 - цель получила существенные повреждения;

S4 - цель полностью поражена (не может функционировать).

Размеченный граф состояний системы показан на рис, 9.

 

В начальный момент цель находится в состоянии S1 (не повреждена). Оп­ределить вероятности состояний цели после четырех выстрелов.

Решение. Из графа состояний имеем:

Р12 = 0,4; Р13 = 0,2; P14 = 0,1 и Р11 = 1 - (Р12 + Р13+ Р14) =0,3.

Аналогично находим:

Р21 = 0; Р22 = 0,4; Р23 = 0,4; Р24 = 0,2;

Р31= 0; Р32 = 0; Р33 = 0,3; Р34 = 0,7;

Р41 = 0; Р42 = 0; Р43 = 0; Р44=1

Таким образом, матрица переходных вероятностей имеет вид;

Так как в начальный момент цель S находится в состоянии S1, то

p1(0) = 1.

Вероятности состояний после первого шага (выстрела) берутся из первой строки матрицы:

p1(1) = 0,3; р2(1) = 0,4; р3(1) = 0,2; р4(1) = 0,1

Вероятности состояний после второго шага:

p1(2) = p1(1)P11 = 0,3×0,3 = 0,09;

р2(2) = р1(1)Р12 + р2(1)Р22 = 0,3×0,4 + 0,4×0,4 = 0,28;

Рз(2) = р1(1)Р13 + p2(1)Р23 + p3(1)P33 = 0,3×0,2+ 0,4×0,4+0,2×0,3 = 0,28;

Р4(2) = Р1(1)Р14 +p2(1) Р24 + p3(1)P34 + p4(1)P44= 0,3×0,1+0,4×0,2+ 0,2×0,7+ 0,1×1= 0,35.

Вероятности состоянии после третьего шага:

p1(3) = p1(2)Р11 = 0,09×0,3 = 0,027;

p2(3) = p1(2)P22 + p2(2) P22 = 0,09×0,4+ 0,28×0,4 = 0,148;

p3(3) = p1(2)P13 + p2(2)P23 + p3(2) P33 =0,09×0,2 + 0,28×0,4 + 0,28×0,3 = 0,214;

p4(3) = p1(2) P14 + p2(2)P24 + p3(2)P34 + p4(2) P44 = 0,09×0,1+0,28×0,2 + 0,28×0,7 + 0,35×1 = 0,611.

Вероятности состояний после четвертого шага:

p1(4) = p1(3)P11 = 0,0081;

p2(4) = p1(3)Pl2 + p2(3) Р22 = 0,27×0,4+0,148×0,4 = 0,0700;

p3(4) = p1(3)Р13 + р2(3)Р23 + р3(3)P33 = 0,027×0,2 + 0,148×0,4 + 0,214×0,3 = 0,1288;

p4(4) = p1(3)Р14 + р2(3)Р24 + p3(3)Р34 + р4(3) Р44 = 0,027×0,1 +0,148×0,2 + 0,214×0,7 + 0,611×1 = 0,7931. I

Таким образом, нами получены вероятности всех исходов обстрела цели (четырех выстрелов):

— цель не повреждена: р1(4)» 0,008;

— цель получила незначительные повреждения: р2(4)» 0,070;

— цель получила существенные повреждения: р3(4)» 0,129;

— цель поражена полностью: р4(4)» 0,793.

 

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

Рассмотрим теперь общий случай - неоднородную мар­ковскую цепь, для которой вероятности перехода Рij меняются от шага к шагу. Обозначим Р - вероятность перехода системы из состояния Si в состояние Sj на k -м шаге, то есть условную вероятность

.

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

(i = 1,..., n), (9)

которая отличается от аналогичной формулы (8) для однородной цепи Маркова только тем, что в ней фигурируют вероятности перехода, за­висящие от номера шага k. Вычисления по формуле (9) ничуть не сложнее, чем в случае однородной цепи.

 

Пример 2. Производится три выстрела по цели, которая может быть в тех же четырех состояниях S1, S2, S3, S4, что и в предыдущем примере, но вероят­ности перехода для трех последовательных выстрелов различны и заданы тремя матрицами:

;

;

.

 

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

Решение. Имеем:

pl(l) = 0,3; p2(l) = 0,4; p3(1) = 0,2; Р4(1) = 0,1;

pl (2) = p1(1)P = 0,3×0,1= 0,03;

p2(2) = p1(l)P +p2(1)P =0,3×0,4 + 0,4×0,2 = 0,20;

p3(2) = р1(1) P + p2(1)P + p3(1)P = 0,3×0,3 + 0,4×0,5 + 0,2×0,2 = 0,33;

p4(2) = р1(1) P + p2(1)P + p3(1)P + p4(1)P = 0,3×0,2 + 0,4×0,3 + 0,2×0,8 + 0,1×1= 0,44;

pl(3) = pl(2)P = 0,03×0,05» 0,002;

p2(3) = p1(2)P + p2(2)P = 0,03×0,3 + 0,20×0,1 = 0,029;

p3(3) = p1(2)Р + p2(2)Р + p3(2)Р = 0,3×0,4 + 0,20×0,6 + 0,33×0,1 = 0,165;

р4(3) = pl(2) Р + p2(2) Р + p3(2) Р + p4(2) Р = 0,03×0,25 + 0,20×0,3 + 0,33×0,9 + 0,44×1» 0,804.

Итак, вероятности состояний после трех выстрелов:

pl(3)» 0,002; р2(3) = 0,029; р3(3) = 0,165; p4 (3)» 0,804.

 

 







Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...





Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2024 zdamsam.ru Размещенные материалы защищены законодательством РФ.