Понятие о марковском процессе

До сих пор мы рассматривали главным образом детерминированные задачи исследования операций и методы оптимизации решений в этих задачах. Начиная с этой главы, и до конца книги мы будем заниматься задачами исследования операций в условиях неопределенности. В этой главе мы рассмотрим сравнительно благоприятный случай «доброкачественной» или «стохастической» неопределенности (см. § 5 гл. 2), когда неопределенные факторы, входящие в задачу, представляют собой случайные величины (или случайные функции), вероятностные характеристики которых либо известны, либо могут быть получены из опыта. Мы будем здесь заниматься, главным образом, прямыми задачами исследования операций, т. е. построением математических моделей некоторых случайных явлений, лишь бегло останавливаясь на обратных задачах (оптимизации решений), потому что они, как правило, сложны. В стохастических задачах исследования операций часто затруднительно даже построение математической модели, уже не говоря об оптимизации («не до жиру, быть бы живу»). В большинстве случаев не удается построить простую математическую модель, позволяющую в явном (аналитическом) виде найти интересующие нас величины (показатели эффективности) в зависимости от условий операции α и элементов решения х. Однако в некоторых особых случаях такую математическую модель удается построить. Это — когда исследуемая операция представляет собой (точно или приближенно) так называемый марковский случайный процесс.

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

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

Под «физической системой» можно понимать что угодно: техническое устройство, группу таких устройств, предприятие, отрасль промышленности, живой организм, популяцию и т.д. Большинству процессов, протекающих в реальных системах, свойственны, в той или иной мере, черты случайности, неопределенности.

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

Теперь спустимся из космоса в околоземную зону. Физическая система S — обыкновенный самолет, совершающий рейс на заданной высоте, по определенному маршруту. Является ли этот процесс случайным? Безусловно, да, так как он неизбежно (в силу турбулентности атмосферы и других факторов) сопровождается случайными возмущениями, колебаниями (в этом не усомнится никто, испытавший на себе так называемую «болтанку» или нарушение графика полетов).

Еще пример: система S — техническое устройство, состоящее из ряда узлов, которые время от времени выходят, из строя, заменяются или восстанавливаются. Процесс, протекающий в этой системе, безусловно, случаен. А столовая самообслуживания? В ней время от времени могут образовываться и рассасываться очереди, возникать задержки, нехватка подносов и т. д.

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

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

Теперь, когда нам ясно, что такое «случайный процесс», дадим определение «марковского случайного процесса». Случайный процесс, протекающий в системе, называется марковским, если для любого момента времени t_o вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент t_o u не зависят от того, когда и как система пришла в это состояние.

Это очень важное определение стоит того, чтобы его растолковать подробнее. Пусть в настоящий момент t₀ (см. рис. 15.1) система находится в определенном состоянии S_o. Мы наблюдаем, процесс со стороны и в момент t_o знаем состояние системы S_o и всю предысторию процесса, все, что было при t < t_o. Нас, естественно, интересует будущее (t > t_o). Можем ли мы его предугадать (предсказать)? В точности — нет, наш процесс случайный, значит — непредсказуемый. Но какие-то вероятностные характеристики процесса в будущем мы найти можем. Например, вероятность того, что через некоторое время т система S окажется в состоянии S_i или сохранит состояние S_o, и т. п.

Так вот, для марковского случайного процесса такое «вероятностное предсказание» оказывается гораздо проще, чем для немарковского. Если процесс — марковский, то предсказывать можно, только учитывая настоящее состояние системы S_o и забыв о его «предыстории» (поведении системы при t < t_o). Само состояние S_o, разумеется, зависит от прошлого, но как только оно достигнуто, о прошлом можно забыть. Иначе формулируя, в марковском процессе «будущее зависит от прошлого только через настоящее».

Пример марковского процесса: система S — счетчик Гейгера, на который время от времени попадают космические частицы; состояние системы в момент t характеризуется показанием счетчика — числом частиц, пришедших до данного момента. Пусть в момент t_o счетчик показывает S_o. Вероятность того, что в момент t > t_o счетчик покажет то или другое число частиц S₁ (или не менее S₁), разумеется, зависит от S₀, но не зависит от того, в какие именно моменты приходили частицы до момента t_o.

На практике часто встречаются процессы, которые если не в точности марковские, то могут быть в каком-то приближении рассмотрены как марковские. Пример: система S — группа самолетов, участвующих в воздушном бою. Состояние системы характеризуется числом самолетов «красных» — х и «синих» — у, сохранившихся (не сбитых) к какому-то моменту. В момент t_o нам известны численности сторон — x₀ и у_о. Нас интересует вероятность того, что в какой-то момент t _о + τ численный перевес будет на стороне «красных». Спросим себя, от чего зависит эта вероятность? В первую очередь от того, в каком состоянии находится система в данный момент to, а не от того, когда и в какой последовательности погибали сбитые до момента t_o самолеты.

Итак, более или менее ясно, что такое марковский случайный процесс. Теперь ошеломим читателя неожиданным парадоксом: в сущности, любой процесс можно рассматривать как марковский, если все параметры из «прошлого», от которых зависит «будущее», включить в «настоящее». Например, пусть речь идет о работе какого-то технического устройства; в какой-то момент to оно еще исправно, и нас интересует вероятность того, что оно проработает еще время т. Если за настоящее состояние системы считать просто «система исправна», то процесс, безусловно, не марковский, потому что вероятность того, что она не откажет за время т, зависит, в общем случае, от того, сколько времени она уже проработала и когда был последний ремонт. Если оба эти параметра (общее время работы и время после последнего ремонта) включить в настоящее состояние системы, то процесс уже можно будет, пожалуй, считать марковским. Однако такое «обогащение настоящего за счет предыстории» далеко не всегда бывает полезно, так как (если число параметров прошлого велико) оно зачастую приводит к «проклятию многомерности», о котором мы уже говорили. Поэтому в дальнейшем, говоря о марковском процессе, мы будем подразумевать его простым, «бесхитростным», с небольшим числом параметров, определяющих «настоящее».

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

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

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

S_o — оба узла исправны,

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

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

S₃ — оба узла ремонтируются.

Переходы системы S из состояния в состояние происходят практически мгновенно, в случайные моменты выхода из строя того или другого узла или окончания ремонта.

Рис. 15.2.

При анализе случайных процессов с дискретными состояниями удобно пользоваться геометрической схемой — так называемым графом состояний. Состояния системы изображаются прямоугольниками (или кругами, или даже точками), а возможные переходы из состояния в состояние — стрелками, соединяющими состояния. Мы будем изображать состояния прямоугольниками, в которых записаны обозначения состояний: S₁, S₂,... S_n.

Построим граф состояний для рассмотренного выше примера (см. рис. 15.2). Стрелка, направленная из S_o в S₁, означает переход в момент отказа первого узла; стрелка, направленная обратно, из S₁ в S_o,— переход в момент окончания ремонта этого узла. Остальные стрелки объясняются аналогично.

Внимательный читатель может спросить: а почему нет стрелки, ведущей непосредственно из S_o в S₃? Разве не может быть, что оба узла откажут одновременно, например, вследствие короткого замыкания? Вопрос законный. Ответим, что мы предполагаем узлы выходящими из строя независимо друг от друга, а вероятностью строго одновременного выхода их из строя пренебрегаем (ниже будет дано более точно обоснование этого допущения).

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

 

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

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

Поток событий можно наглядно изобразить рядом точек на оси времени Ot (рис. 16.1); не надо только забывать, что положение каждой из них случайно, и на рис. 16.1 изображена только какая-то одна реализация

потока.

 

рис. 16.1.

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

вероятностями обладают другие, производные от них события, например: «на участок времени τ (рис. 16.1) попадет ровно два события», или «на участок времени Δt попадет хотя бы одно событие», или «промежуток времени между двумя соседними событиями будет не меньше t».

Важной характеристикой потока событий является его интенсивность λ — среднее число событий, приходящееся на единицу времени. Интенсивность потока может быть как постоянной (λ = const.), так и переменной, зависящей от времени t. Например, поток автомашин, движущихся по улице, днем интенсивнее, чем ночью, в часы пик — интенсивнее, чем в другие часы.

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

Поток событий называется стационарным, если его вероятностные характеристики не зависят от времени. В частности, интенсивность \ стационарного потока должна быть постоянной. Это отнюдь не значит, что фактическое число событий, появляющееся в единицу времени, постоянно,— нет, поток неизбежно (если только он не регулярный) имеет какие-то случайные сгущения и разрежения, как, например, показано на рис. 16.1. Важно, что для стационарного потока эти сгущения и разрежения не носят закономерного характера: на один участок длины 1 может попасть больше, а на другой — меньше событий, но среднее число событий, приходящееся на единицу времени, постоянно и от времени не зависит.

Одна из типичных ошибок начинающих — это принимать случайные сгущения и разрежения потока за изменения его интенсивности. Предостережем читателя от этой ошибки!

Как правило, отклонения от стационарности могут быть объяснены какими-то физическими причинами. Например, совершенно естественно, интенсивность потока вызовов, поступающих на АТС, ночью меньше, чем днем (ночью люди имеют обыкновение спать). Увеличение интенсивности потока покупателей, приходящих в магазин, в часы после окончания рабочего дня тоже имеет физическое объяснение. Если поток событий имеет тенденцию к явно выраженным сгущениям и разрежением (особенно периодическим), нужно всегда заподозрить физическую причину и постараться ее выявить.

На практике часто встречаются потоки событий, которые (по крайней мере, на ограниченном участке времени) могут считаться стационарными. Например, поток вызовов, поступающих на АТС между 13 и 14 часами, практически стационарен; тот же поток в течение суток уже не стационарен¹).

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

(хотя бы потому, что интервал по времени между отдельными покупателями не может быть меньше, чем минимальное время to обслуживания каждого из них). Так же обстоит дело и с потоком поездов, подходящих к станции (между ними всегда существует какой-то минимальный интервал to, выбираемый из соображений безопасности). Впрочем, если минимальный интервал между событиями много меньше среднего интервала между ними t = 1А, иногда наличием последействия можно пренебречь.

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

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

 

 

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

Легко доказать (см., например, [l2] или любой учеб-пик по теории вероятностей),что для простейшего потока с интенсивностью , интервал Т между соседними событиями имеет так называемое показательное распределение с плотностью

 

f(t) = (t > 0) (16.1)

 

(см. рис. 16.3). Величина в формуле (16.1) называется параметром показательного закона. Для случайной величины Т, имеющей показательное распределение, математическое ожидание т_Т есть величина, обратная параметру, а среднее квадратическое отклонение равно математическому ожиданию:

 

. (16.2)

 

В теории вероятностей в качестве «меры случайности» неотрицательной случайной величины нередко рассматривают так называемый коэффициент вариации:

 

. (16.3)

 

Из формул (16.2), (16.3) следует, что для показательного распределения v_Т = 1, т. е. для простейшего потока событий коэффициент вариации интервалов между событиями равен единице.

Очевидно, что для регулярного потока событий, у которого интервал между событиями вообще не случаен ( = 0), коэффициент вариации равен нулю. Для большинства потоков событий, встречающихся на практике, коэффициент вариации интервалов между событиями заключен между нулем и единицей и может служить некоторой мерой «степени регулярности» потока: чем v _Т ближе к нулю, тем «регулярнее» поток. Простейший поток — это «наименее регулярный» из встречающихся на практике потоков¹).

В расчетах, связанных с потоками событий, очень удобно пользоваться понятием «элемента вероятности». Рассмотрим на оси Ot простейший поток с интенсивностью и произвольно расположенный элементарный (очень маленький!) участок времени . Элементом вероятности называется вероятность попадания на этот участок хотя бы одного события потока. Легко доказать (мы этого делать не будем), что элемент вероятности (с точностью до малых величин более высокого порядка по сравнению с ) равен

 

, (16.4)

 

т. е. для простейшего потока элемент вероятности равен интенсивности потока, умноженной на длину элементарного участка. Заметим, что элемент вероятности, в силу отсутствия последействия, совершенно не зависит 'от того, сколько событий и когда появлялись ранее.

Заметим также, что с точностью до величин высшего порядка малости вероятность появления хотя бы одного события на элементарном участке At равна вероятности появления ровно одного события па этом участке. Это вытекает из ординарности простейшего потока²).

Поток событий называется рекуррентным (иначе—«потоком Пальма»), если он стационарен, ординарен, а интервалы времени между событиями Т₁, Т₂, Т₃,... (см. рис. 16.4) представляют собой независимые случайные величины с одинаковым произвольным распределением (например, с плотностью, показанной на рис. 16.5).

 

¹) Можно придумать искусственные примеры потоков, для которых v _Т > 1, но природа таких фокусов обычно не устраивает.

²) Вспомним, как мы не проставили стрелок из состояния S₀ в S₃ и обратно на рис. 15.2. Это объясняется тем, что как потоки отказов. так и потоки восстановлении узлов мы считали ординарными.

 

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

О t Рис. 16.4.

«поток замен» или «восстановлении») будет рекуррентным.

Другой пример. Продавец в магазине непрерывно занят обслуживанием покупателей (как это бывает в часы максимальной нагрузки). Обслуживание покупателя продолжается случайное время Т. Тогда поток обслуженных покупателей будет рекуррентным (если считать, что времена обслуживания отдельных покупателей независимы и, например, ссора между продавцом и покупателем не скажется на времени обслуживания других).

Очевидно, простейший поток представляет собой частный случай рекуррентного потока, когда интервалы между событиями имеют показательное распределение (16.1). Другим частным (вырожденным) случаем рекуррентного потока является регулярный поток событий, где интервалы вообще не случайны, постоянны.

 

 

Целую гамму рекуррентных потоков событий, обладающих разной степенью упорядоченности, можно получить «просеиванием» простейшего потока. Пусть, например, в какое-то учреждение поступает простейший поток посетителей, а у входа стоит «страж», направляющий первого посетителя — к первому столу, второго — ко второму столу и т. д. Если столов n, то на каждый из них поступает так называемый «поток Эрланга п-го порядка». Такой поток получается из простейшего, если сохранять в потоке каждое n -е событие, а промежуточные — выбрасывать. Простейший поток есть не что иное, как поток Эрланга первого порядка. Можно показать, что при таком просеивании простейшего потока коэффициент вариации интервалов уменьшается, и при увеличении порядка п поток Эрланга приближается к регулярному. Коэффициент вариации интервалов между событиями потока Эрланга n -го порядка равен . Потоки Эрланга образуют целую гамму потоков с различной степенью упорядоченности — от «полного беспорядка» (простейший поток) до полной упорядоченности (регулярный поток).

 

§ 17. Уравнения Колмогорова для вероятностей состояний. Финальные вероятности состояний

Рассматривая марковские процессы с дискретными состояниями и непрерывным временем, нам удобно будет представлять себе, что все переходы системы S из состояния в состояние происходят под действием каких-то потоков событий (поток вызовов, поток отказов, поток восстановлении и т. д.). Если все потоки событий, переводящие систему S из состояния в состояние,— простейшие, то процесс протекающий в системе, будет марковским¹). Это и естественно, так как простейший ноток не обладает последействием: в нем «будущее» не зависит от «прошлого».

Если система S находится в каком-то состоянии S_i, из которого есть непосредственный переход в другое состояние S_j (стрелка, ведущая из S_i, в S_j на графе состояний), то мы себе это будем представлять так, как будто па систему, пока она находится в состоянии S_i действует простейший поток событий, переводящий её по стрелке S_i S_j. Как только появится первое событие этого потока, происходит «перескок» системы из S_i в S_j.

Для наглядности очень удобно на графе состояний у каждой стрелки проставлять интенсивность того потока событий, который переводит систему по данной стрелке. Обозначим интенсивность потока событий, переводящего систему из состояния S_i в S_j. На рис. 17.1 дан граф состояний с проставленными у стрелок интенсивностями (мы будем называть такой граф размеченным).

 

 

¹) Простейший характер потоков — достаточное, но не необходимое условие для того, чтобы процесс был марковским.

 

Построим размеченный граф состояний для примера, данного в § 15 (техническое устройство из двух узлов). Напомним состояния системы:

S₀ — оба узла исправны,

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

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

S₃ — оба узла ремонтируются.

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

от того, ремонтируется ли один узел или оба сразу. Это будет именно так, если ремонтом каждого узла занят отдельный специалист. Найдем все интенсивности потоков событий, переводящих систему из состояния в состояние. Пусть система находится в состоянии S₀. Какой поток событий переводит ее в состояние S₁? Очевидно, поток отказов первого узла. Его интенсивность равна единице, деленной па среднее время безотказной работы первого узла. Какой поток событий переводит систему обратно из S₁ в S₀? Очевидно, поток «окончаний ремонтов» первого узла. Его интенсивность равна единице, деленной на среднее время ремонта первого узла. Аналогично вычисляются интенсивности потоков событий, переводящих систему по всем стрелкам графа рис. 17.2.

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

В самом деле, пусть рассматривается система S, имеющая п возможных состояний S₁, S₂,..., S_n. Назовем вероятностью i -го состояния вероятность p_i (t) того, что в момент t система будет находиться в состоянии S_i. Очевидно, что для любого момента сумма всех вероятностей состояний равна единице:

 

(17.1)

 

 

Имея в своем распоряжении размеченный граф состояний, можно найти все вероятности состояний p_i (t) как функции времени. Для этого составляются и решаются так называемые уравнения Колмогорова — особого вида дифференциальные уравнения, в которых неизвестными функциями являются вероятности состояний.

Покажем на конкретном примере, как эти уравнения составляются. Пусть система S имеет четыре состояния: S₁, S₂, S₃, S₄, размеченный граф которых показан на рис. 17.3. Рассмотрим одну из вероятностей состояний, например p_i (t). Это—вероятность того, что в момент t система будет в состоянии S ₁. Придадим t малое приращение и найдем р ₁ (t + ) — вероятность того, что в момент t + система будет в состоянии S ₁. Как это может произойти? Очевидно, двумя способами: либо 1) в момент t система уже была в состоянии S ₁, а за время не вышла из него; либо 2) в момент t система была в состоянии S ₂, а за время перешла из него в S ₁.

Найдем вероятность первого варианта. Вероятность того, что в момент t система была в состоянии S ₁, равна p ₁(t). Эту вероятность нужно умножить на вероятность того, что, находившись в момент t в состоянии S ₁, система за время не перейдет из него ни в S ₂, ни в S ₃. Суммарный поток событий, выводящий систему из состояния S ₁, тоже будет простейшим, с интенсивностью (при наложении — суперпозиции — двух простейших потоков получается опять простейший поток, так как свойства стационарности, ординарности и отсутствия последействия сохраняются). Значит, вероятность того, что за время система выйдет из состояния S ₁, равна () ; вероятность того, что не выйдет: 1 - ( Отсюда вероятность первого варианта равна p ₁(t) [1 - ( ].

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

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

 

.

 

Раскроем квадратные скобки, перенесем pi(t) в левую часть и разделим обе части на :

 

 

Устремим, как и полагается в подобных случаях, к нулю; слева получим в пределе производную функции p ₁(t). Таким образом, запишем дифференциальное уравнение для p ₁(t):

 

 

или, короче, отбрасывая аргумент t у функций p ₁, p ₂(теперь он нам больше уже не нужен):

 

. (17.2)

 

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

 

(17.3)

 

 

Это — система четырех линейных дифференциальных уравнений с четырьмя неизвестными функциями p ₁, р ₂, р ₃, р ₄. Заметим, что одно из них (любое) можно отбросить, пользуясь тем, что p ₁ + p ₂ + р ₃ + р ₄ = 1: выразить любую из вероятностей p_i через другие, это выражение подставить в (17.3), а соответствующее уравнение с производной отбросить.

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

Пользуясь этим правилом, запишем уравнения Колмогорова для системы S, размеченный граф состояний которой дан на рис. 17.2:

 

(17.4)

 

Чтобы решить уравнения Колмогорова и найти вероятности состояний, прежде всего надо задать начальные условия. Если мы точно знаем начальное состояние системы S_i, то в начальный момент (при t = 0) p_i (0) = 1, а все остальные начальные вероятности равны пулю. Так, например, уравнения (17.4) естественно решать при начальных условиях p ₀(0) = 1, p ₁(0) = p ₂(0) = p ₃(0) = 0 (в начальный момент оба узла исправны).

Как решать подобные уравнения? Вообще говоря, линейные дифференциальные уравнения с постоянными коэффициентами можно решать аналитически, но это удобно только когда число уравнений не превосходит двух (иногда — трех). Если уравнений больше, обычно их решают численно — вручную или на ЭВМ.

Таким образом, уравнения Колмогорова дают возможность найти все вероятности состояний как функции времени.

Поставим теперь вопрос: что будет происходить с вероятностями состояний при t ? Будут ли p ₁(t), p ₂(t), ... стремиться к каким-то пределам? Если эти пределы существуют и не зависят от начального состояния системы, то они называются финальными вероятностями состояний. В теории случайных процессов доказывается, что если число п состояний системы конечно и из каждого из них можно (за конечное число шагов) перейти в любое другое, то финальные вероятности существуют').

Предположим, что это условие выполнено и финальные вероятности существуют:

 

. (17.5)

 

Финальные вероятности мы будем обозначать теми же буквами р ₁, р ₂ ,..., что и сами вероятности состояний, но разумея под ними уже не переменные величины (функции времени), а постоянные числа. Очевидно, они тоже образуют в сумме единицу:

 

(17.6)

 

Как понимать эти финальные вероятности? При t в системе S устанавливается предельный стационарный режим, в ходе которого система случайным образом меняет свои состояния, но их вероятности уже не зависят от времени. Финальную вероятность состояния S, можно истолковать как среднее относительное время пребывания системы в этом состоянии. Например, если система S имеет три состояния S ₁, S ₂, S ₃ и их финальные вероятности равны 0,2, 0,3 и 0,5, это значит, что в предельном, стационарном режиме система в среднем две десятых времени проводит в состоянии S ₁, три десятых — в состоянии S ₂ и половину времени — в состоянии S ₃.

 

¹) Это условие достаточно, но не необходимо для существования фина