ЧАСТЬ 2. МОДЕЛИРОВАНИЕ ОПЕРАЦИЙ ПО СХЕМЕ МАРКОВСКИХ СЛУЧАЙНЫХ ПРОЦЕССОВ

ЧАСТЬ 2. МОДЕЛИРОВАНИЕ ОПЕРАЦИЙ ПО СХЕМЕ МАРКОВСКИХ СЛУЧАЙНЫХ ПРОЦЕССОВ

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

С ДИСКРЕТНЫМИ СОСТОЯНИЯМИ

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

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

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

Поясним понятие марковского случайного процесса.

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

Примерами случайных процессов могут быть:

— процесс функционирования ЭЦВМ;

— процесс наведения на цель управляемой ракеты или космического летательного аппарата;

— процесс обслуживания клиентов парикмахерской или ремен­ной мастерской;

— процесс выполнения плана снабжения группы предприятий и т. д.

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

— поступление заказов на ЭЦВМ и вид этих заказов; случайные выходы ЭЦВМ из строя;

— случайные возмущения (помехи) в системе управления ракетой;

— случайный характер потока заявок (требований), поступаю­щих со стороны клиентов;

— случайные перебои в выполнении плана снабжения и т. д.

Случайный процесс, протекающий в системе S, называется марковским процессом (или «процессом без последействия»), если он обладает следующим свойством:

Для каждого момента времена t₀ вероятность любого состояния системы в будущем (при t > t₀) зависит только от ее состояния в на­стоящем (при t = t₀) и не зависит от того, когда и каким образом систе­ма пришла в это состояние (т. е. как развивался процесс в прошлом).

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

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

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

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

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

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

S₁, S₂, S₃,...

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

Пример 1. Техническое устройство S состоит из двух узлов: I и II, каждый из которых может в ходе работы устройства отказать (выйти из строя). Воз­можны следующие состояния системы:

S₁ — оба узла работают;

S₂ — первый узел отказал, второй работает;

S₃ — второй узел отказал, первый работает;

S₄ — оба узла отказали.

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

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

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

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

Пусть имеется система S с дискретными состояниями:

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

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

Заметим, что стрелками отмечаются только непосредственные переходы из состояния в состояние; если система может перейти из состояния S₁ в S₃ только через S₂, то стрелками отмечаются только переходы S₁ ® S₂ и S₂ ® S₃, но не S₁ ® S₃.

Пример 2. Система S — автомашина, которая может находиться в одном из пяти возможных состояний:

S₁ — исправна, работает; |

S₂ — неисправна, ожидает осмотра;

S₃ — осматривается;

S₄ — ремонтируется;

S₅ — списана.

Граф состояний системы показан на рис. 2.

Пример 3. Построить граф состояний в условиях примера 1 (предпола­гается, что ремонт узлов в ходе процесса не производится).

Решение. Граф состояний представлен на рис. 3. Отметим, что на графе не показан возможный переход из состояния S₁, непосредственно в S₄, который осуществится, если строго одновременно выйдут из строя оба узла. Возможностью такого события мы пренебрегаем.

Пример 4. Система S, как и в примере 1, представляет собой техническое устройство, состоящее из двух узлов: I и II; каждый из них может в какой-то момент времени отказать. Отказавший узел немедленно начинает восстанавливаться. Возможные состояния системы:

S₁ — оба узла работают;

S₂ — первый узел восстанавливается, второй работает;

S₃ — первый узел работает, второй восстанавливается;

S₄ — оба узла восстанавливаются

Граф состояний системы показан на рис. 4

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

Состояния системы будем для удобства нумеровать не одним, а двумя ин­дексами; первый будет означать состояния первого узла:

1 — работает,

2 — осматривается,

3 — восстанавливается;

второй — те же состояния для второго узла, так что, например, S₂₃ будет озна­чать: первый узел осматривается, второй — восстанавливается, и т. д.

Возможные состояния системы S будут:

S₁₁ — оба узла работают,

S₁₂ — первый узел работает, второй осматривается,

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

S₃₃ — оба узла восстанавливаются (всего 9 состояний).

Граф состояний показан па рис. 5.

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

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

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

Случайный процесс называется процессом с дискрет­ным временем, если переходы системы из состояния в состояние возможны только в строго определенные, заранее фиксированные мо­менты времени: 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.

УРАВНЕНИЯ КОЛМОГОРОВА

ДЛЯ ВЕРОЯТНОСТЕЙ СОСТОЯНИЙ

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

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

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

Покажем, как выражаются вероятности состояний для такого процесса.

Пусть имеется ряд дискретных состояний

S₁, S₂, …, S_n;

переход (перескок) системы S из состояния в состояние может осуществ­ляться в любой момент времени. Граф состояний системы представлен на рис. 10.

Обозначим р_i(t) — вероятность того, что в момент t система S будет находиться в состоянии S_i (i = 1,..., n). Очевидно, для любого мо­мента t сумма вероятностей состояний равна единице:

, (3.1)

так как события, состоящие в том, что в момент t система находится в состояниях S_l, S₂,..., S_n, несовместны и образуют полную группу.

Поставим задачу - определить для любого t вероятности состояний:

p₁(t), p₂(t), …, p_n(t)

Для того, чтобы найти эти вероятности, необходимо знать харак­теристики процесса, аналогичные переходным вероятностям для мар­ковской цепи. В случае процесса с непрерывным временем нам не при­дется задавать определенные, отличные от нуля, переходные вероят­ности P_ij; вероятность перехода (перескока) системы из состояния в со­стояние точно в момент t будет равна нулю (так же как вероятность
любого отдельного значения непрерывной случайной величины). Вмес­то переходных вероятностей P_ij мы введем в рассмотрение плот­ности вероятностей перехода l_ij.

Пусть система S в момент t находится в состоянии S_i. Рассмотрим элементарный промежуток времени Dt, примыкающий к моменту t (рис. 11).

Назовем плотностью вероятности перехода l_ij предел отношения вероятности перехода системы за время Dt из состояния S_i в состояние S_j к длине промежутка Dt:

, (3.2)

где P_ij(Dt) - вероятность того, что система, находившаяся в момент t в состоянии S_i, за время Dt перейдет из него в состояние Sj (плот­ность вероятностей перехода определяется только для i ≠ j)

Из формулы (3.2) следует, что при малом Dt вероятность перехода P_ij(Dt) (с точностью до бесконечно малых высших порядков) равна l_ijDt:

P_ij(Dt) ≈ l_ijDt.

Если все плотности вероятностей перехода l_ij не зависят от t (т. е. от того, в какой момент начинается элементарный участок Dt), мар­ковский процесс называется однородным; если эти плотности представляют собой какие-то функции времени l_ij (t)процесс назы­вается неоднородным. При пользовании сокращенным названием «непрерывная марковская цепь» мы также будем различать одно­родные и неоднородные цепи.

Предположим, что нам известны плотности вероятностей пере­хода l_ij для всех пар состояний S_i, S_j.

Построим граф состояний системы S и против каждой стрелки про­ставим соответствующую плотность вероятности перехода (рис 12).

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

Оказывается, зная размеченный граф состояний, можно определить вероятности
состояний:

p₁(t), p₁(t), … p_n(t) (3.3)

как функции времени. А именно, эти вероятности удовлетворяют определенного вида дифференциальным уравнениям, так называемым уравнениям Колмогорова. Решая эти уравнения, мы получим вероятности (3.3).

Продемонстрируем методику вывода уравнений Колмогорова для вероятностей состояний на конкретном примере.

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

S₁, S₂, S₃, S₄

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

Поставим себе задачу: найти одну из вероятностей состояний, например, p₁(t). Это есть вероятность того, что в момент t система будет находиться в состоянии S₁.

Придадим малое приращение Dt и найдем вероятность того, что в момент t+Dt система будет находиться в состоянии S₁.

Как это событие может произойти? Очевидно, двумя способами:

– в момент t система уже была в состоянии S₁ а за время Dt не вышла из этого состояния

или

– в момент tсистема была в состоянии S₃, а за время Dt перешла из него в S₁.

Вероятность первого варианта найдем как произведение вероят­ности p₁(t) того, что в момент t система была в состоянии S₁, на услов­ную вероятность того, что, будучи в состоянии S₁ система за время Dt не перейдет из него в S₂. Эта условная вероятность (с точностью до бесконечно малых высших порядков) равна 1 – l₁₂Dt.

Аналогично, вероятность второго варианта равна вероятности то­го, что в момент t система была в состоянии S₃, умноженной на услов­ную вероятность перехода за время Dt в состояние S₁:

p₃(t)l₃₁Dt.

Применяя правило сложения вероятностей, получим:

p₁(t+Dt) = p₁(t)(1 – l₁₂Dt) + p₃(t)l₃₁Dt.

Раскроем скобки в правой части, перенесем p₁(t) в левую и разде­лим обе части равенства на Dt; получим:

Теперь устремим Dt к нулю и перейдем к пределу:

.

Левая часть есть не что иное, как производная функции p₁(t):

(3.4)

Таким образом, выведено дифференциальное урав­нение, которому должна удовлетворять функция p₁(t). Аналогич­ные дифференциальные уравнения могут быть выведены и для осталь­ных вероятностей состояния: р₂(t), р₃(t), р₄(t).

Рассмотрим второе состояние S₂ и найдем р₂(t + Dt) – вероят­ность того, что в момент (t+Dt) система S будет находиться в состоя­нии S₂. Это событие может произойти следующими способами:

– в момент t система уже была в состоянии S₂, а за время Dt не перешла из него ни в S₃, ни в S₄; или

– в момент t система была в состоянии S₃ а за время Dt перешла из него в S₂; или

– в момент t система была в состоянии S₄, а за время Dt перешла из него в S₂.

Вероятность первого варианта вычисляется так: р₂(t) умножается на условную вероятность того, что система за Dt не перейдет ни в S₃, ни в S₄. Так как события, состоящие в переходе за время Dt из S₂ в S₃ и из S₂ в S₄, несовместны, то вероятность того, что осуществится один из этих переходов равна сумме их вероятностей, т. е. l₂₃Dt + l₂₄Dt (с точностью до бесконечно малых высших порядков). Вероятность то­го, что не осуществится ни один их этих переходов, равна 1 – l₂₃Dt – l₂₄Dt. Отсюда вероятность первого варианта:

p₂(t)(1 – l₂₃Dt – l₂₄Dt).

Прибавляя сюда вероятности второго и третьего вариантов, по­лучим:

p₂(t+Dt) = p₂(t)(1 – l₂₃Dt – l₂₄Dt) + p₁(t)l₁₂Dt + p₄(t)l₄₂Dt

Перенося р₂(t) в левую часть, деля на Dt и переходя к пределу, получим дифференциальное уравнение для p₂(t):

(3.5)

Рассуждая аналогично для состояний S₃, S₄, получим в результа­те систему дифференциальных уравнений, составленных по типу (3.4) и (3.5). Отбросим в них для краткости аргумент t у функций р₁, р₂, р₃, р₄ и перепишем эту систему в виде:

(3.6)

Эти уравнения для вероятностей состояний и называются уравнения­ми Колмогорова.

Интегрирование этой системы уравнений даст нам искомые вероят­ности состояний как функции времени. Начальные условия берутся в зависимости от того, каково было начальное состояние системы S. Например, если в начальный момент времени (при t = 0) система S находилась в состоянии S_` то надо принять начальные условия:

при t=0 p₁ = 1, р₂ = р₃ = р₄ = 0.

Заметим, что всех четырех уравнений для р₁, р₂, р₃, p₄ можно было бы и не писать; действительно, р₁ + р₂ + р₃ + p₄ = 1 для всех t и любую из вероятностей р₁, р₂, р₃, p₄ можно выразить через три ос­тальные. Например р₄ можно выразить через р₁, р₂, р₃ в виде

p₄ = l – (р₁ + р₂ + р₃)

и подставить в остальные уравнения. Тогда специального уравнения для вероятности р₄ можно и не писать. Однако в дальнейшем нам будет удобнее пользоваться полной системой уравнений типа (3.6).

Обратим внимание на структуру уравнений (3.6). Все они построе­ны по вполне определенному правилу, которое можно сформулировать следующим образом.

В левой части каждого уравнения стоит производная вероятности состояния, а правая часть содержит столько членов, сколько стрелок связано с данным состоянием. Если стрелка, направлена из состояния, соответствующий член имеет знак «минус»; если в состояние – знак «плюс». Каждый член равен произведению плотности вероятности перехода, соответствующей данной стрелке, умноженной на вероятность того состояния, из которого исходит стр

12345678Следующая ⇒

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

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

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

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

---

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