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

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

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

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

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

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

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

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

S₁, S₂,..., S_n,

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

t₁, t₂,..., t_n, ….

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

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

S₁ ® S₃ ® S₅ ® S₄ ® S₂ ® S₁ ®...

или же

S₁ ® S₂ ® S₁ ® S₂ ® S₃ ® S₄ ® S₁ ®....

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

S₁ ® S₁ ® S₂ ® S₃ ® S₃ ® S₃ ® S₄ ® S₁ ®...

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

S₁^(k), S₂^(k),..., S_i^(k),..., S_n^(k)

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

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

S₁⁽⁰⁾, S₂⁽¹⁾, S₁⁽²⁾, S₂⁽³⁾, S₃⁽⁴⁾,...

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

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

S₁, S₂,..., S_n,

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

S₁^(k), S₂^(k),..., S_n^(k).

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

p₁(1) = P(S₁⁽¹⁾); p₂(1) = P(S₂⁽¹⁾); …; p_n(1) = P(S_n⁽¹⁾)

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

p₁(2) = P(S₁⁽²⁾); p₂(2) = P(S₂⁽²⁾); …; p_n(2) = P(S_n⁽²⁾) (1)

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

p₁(k) = P(S₁^(k)); p₂(k) = P(S₂^(k)); …; p_n(k) = P(S_n^(k)) (2)

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

p₁(k) + p₂(k) + … + p_n(k) = 1,

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

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

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

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

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

S₁ ® S₃ ® S₂ ® S₂ ® S₃ ® S₅ ® S₆ ® S₂

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

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

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

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

Рассмотрим сначала однородную марковскую цепь. Пусть система S имеет n возможных состояний S₁, S₂,..., S_n. Предположим, что для каждого состояния нам известна вероятность перехода в любое другое состояние за один шаг (в том числе и вероятность задержки в данном состоянии). Обозначим Р_ij вероятность перехода за один шаг из состоя­ния S_i в состояние S_j; Р_ii будет вероятность задержки системы в со­стоянии S_i. Запишем переходные вероятности Р_ij в виде прямоуголь­ной таблицы (матрицы):

(3)

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

Пользуясь введенными выше событиями S₁^(k), S₂^(k),..., S_n^(k), пере­ходные вероятности P_ij можно записать как условные вероятности:

P_ij = P(S_j^(k)/ S_i^(k-1)).

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

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

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

P₁₁ = l - (P₁₂ + P₁₃),

P₂₂ = l - (P₂₃ + P₂₄),

P₃₃ = l - (P₃₂ + P₃₅),

P₄₄ = l - (P₄₃ + P₄₅ + P₄₆),

P₅₅ = l - P₅₆,

P₆₆ = l - P₆₂ .

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

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

p₁(k), p₂(k),..., p_n(k)

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

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

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

p₁(0)=0; p₂(0)=0;...; p_m(0) = l; …; Р_n(0)=0,

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

Найдем вероятности состояний после первого шага. Мы знаем, что перед первым шагом система заведомо находится в состоянии S_m. Значит, за первый шаг она перейдет в состояния S₁, S₂,..., S_m,..., S_n с вероятностями

P_m1, P_m2, …, P_mm, …, P_mn,

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

p₁(1) = P_m1; p₂(1) = P_m2; …; p_m(1) = P_mm; …; p_n(1) = P_mn . (4)

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

p_l(2), р₂(2),..., р_i(2),…, р_n(2).

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

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

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

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

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

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

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

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

(5)

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

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

В формуле (6) суммирование распространяется формально на все состояния S₁,..., S_n; фактически учитывать надо только те из них, для которых переходные вероятности Р_ij отличны от нуля, то есть те состояния, из которых может совершиться переход в состоя­ние S_i (или задержка в нем).

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

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

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

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

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

Пример 1. По некоторой цели ведется стрельба четырьмя выстрелами в моменты времени t₁, t₂, t₃, t₄.

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

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

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

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

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

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

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

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

Р₁₂ = 0,4; Р₁₃ = 0,2; P₁₄ = 0,1 и Р₁₁ = 1 - (Р₁₂ + Р₁₃+ Р₁₄) =0,3.

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

Р₂₁ = 0; Р₂₂ = 0,4; Р₂₃ = 0,4; Р₂₄ = 0,2;

Р₃₁= 0; Р₃₂ = 0; Р₃₃ = 0,3; Р₃₄ = 0,7;

Р₄₁ = 0; Р₄₂ = 0; Р₄₃ = 0; Р₄₄=1

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

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

p₁(0) = 1.

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

p₁(1) = 0,3; р₂(1) = 0,4; р₃(1) = 0,2; р₄(1) = 0,1

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

p₁(2) = p₁(1)P₁₁ = 0,3×0,3 = 0,09;

р₂(2) = р₁(1)Р₁₂ + р₂(1)Р₂₂ = 0,3×0,4 + 0,4×0,4 = 0,28;

Рз(2) = р₁(1)Р₁₃ + p₂(1)Р₂₃ + p₃(1)P₃₃ = 0,3×0,2+ 0,4×0,4+0,2×0,3 = 0,28;

Р₄(2) = Р₁(1)Р₁₄ +p₂(1) Р₂₄ + p₃(1)P₃₄ + p₄(1)P₄₄= 0,3×0,1+0,4×0,2+ 0,2×0,7+ 0,1×1= 0,35.

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

p₁(3) = p₁(2)Р₁₁ = 0,09×0,3 = 0,027;

p₂(3) = p₁(2)P₂₂ + p₂(2) P₂₂ = 0,09×0,4+ 0,28×0,4 = 0,148;

p₃(3) = p₁(2)P₁₃ + p₂(2)P₂₃ + p₃(2) P₃₃ =0,09×0,2 + 0,28×0,4 + 0,28×0,3 = 0,214;

p₄(3) = p₁(2) P₁₄ + p₂(2)P₂₄ + p₃(2)P₃₄ + p₄(2) P₄₄ = 0,09×0,1+0,28×0,2 + 0,28×0,7 + 0,35×1 = 0,611.

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

p₁(4) = p₁(3)P₁₁ = 0,0081;

p₂(4) = p₁(3)P_l2 + p₂(3) Р₂₂ = 0,27×0,4+0,148×0,4 = 0,0700;

p₃(4) = p₁(3)Р₁₃ + р₂(3)Р₂₃ + р₃(3)P₃₃ = 0,027×0,2 + 0,148×0,4 + 0,214×0,3 = 0,1288;

p₄(4) = p₁(3)Р₁₄ + р₂(3)Р₂₄ + p₃(3)Р₃₄ + р₄(3) Р₄₄ = 0,027×0,1 +0,148×0,2 + 0,214×0,7 + 0,611×1 = 0,7931. I

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

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

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

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

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

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

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

.

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

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

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

Пример 2. Производится три выстрела по цели, которая может быть в тех же четырех состояниях S₁, S₂, S₃, S₄, что и в предыдущем примере, но вероят­ности перехода для трех последовательных выстрелов различны и заданы тремя матрицами:

;

;

.

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

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

p_l(l) = 0,3; p₂(l) = 0,4; p₃(1) = 0,2; Р₄(1) = 0,1;

p_l (2) = p₁(1)P = 0,3×0,1= 0,03;

p₂(2) = p₁(l)P +p₂(1)P =0,3×0,4 + 0,4×0,2 = 0,20;

p₃(2) = р₁(1) P + p₂(1)P + p₃(1)P = 0,3×0,3 + 0,4×0,5 + 0,2×0,2 = 0,33;

p₄(2) = р₁(1) P + p₂(1)P + p₃(1)P + p₄(1)P = 0,3×0,2 + 0,4×0,3 + 0,2×0,8 + 0,1×1= 0,44;

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

p₂(3) = p₁(2)P + p₂(2)P = 0,03×0,3 + 0,20×0,1 = 0,029;

p₃(3) = p₁(2)Р + p₂(2)Р + p₃(2)Р = 0,3×0,4 + 0,20×0,6 + 0,33×0,1 = 0,165;

р₄(3) = p_l(2) Р + p₂(2) Р + p₃(2) Р + p₄(2) Р = 0,03×0,25 + 0,20×0,3 + 0,33×0,9 + 0,44×1» 0,804.

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

p_l(3)» 0,002; р₂(3) = 0,029; р₃(3) = 0,165; p₄ (3)» 0,804.

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

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

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

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