Имея размеченный граф состояний, можно написать уравнения Колмогорова для вероятностей состояний, а также написать и решить алгебраические уравнения для финальных вероятностей. Для некоторых случаев удается последние уравнения решить заранее, в буквенном виде. В частности, это удается сделать, если граф состояний системы представляет собой так называемую «схему гибели и размножения».

Граф состояний для схемы гибели и размножения имеет вид, показанный на рисунке 19.1.

л01 л12 л23 лk-1,k лk,k-1 лn-1,n

л10 л21 л32 лk,k-1 лk+1,k лn,n-1

Рисунок 19.1

Особенность этого графа в том, что все состояния системы можно вытянуть в одну цепочку, в которой каждое из средних состояний (S1, S2, ..., Sn-1) связано прямой и обратной стрелкой с каждым из соседних состояний -- правым и левым, а крайние состояния (S0, Sn) -- только с одним соседним состоянием. Термин «схема гибели и размножения» ведет начало от биологических задач, где подобной схемой описывается изменение численности популяции.

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

Предположим, что все потоки событий, переводящие систему по стрелкам графа,-- простейшие.

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

Для первого состояния S0 имеем:

01p0=10p1. (19.1)

Для второго состояния S1:

(12 + 10)p1 = 01p0 + 21P2.

В силу (19.1) последнее равенство приводится к виду

23Р2 = 32p3

k -1,kpk-1=k,k-1pk,

где k принимает все значения от 0 до n. Итак, финальные вероятности р0, p1,..., pn удовлетворяют уравнениям

…………………. (19.2)

k-1,kpk-1=k,k-1pk

………………….

n-1,npn-1=n,n-1pn

кроме того, надо учесть нормировочное условие

p 0 +p1+p2+ ... +рn =1. (19.3)

Решим эту систему уравнений. Из первого уравнения (19.2) выразим р1 через р0:

p 1 = (01/10)p0. (19.4)

Из второго, с учетом (19.4), получим:

p 2=(12/21)p1=(1201)/(2110)p0; (19.5)

из третьего, с учетом (19.5),

p3=(231201)/(322110)p0 (19.6)

и вообще, для любого k (от 1 до n):

pk=(k-1,k... 1201)/(k,k-1... 2110)p0 (19.7)

Обратим внимание на формулу (19.7). В числителе стоит произведение всех интенсивностей, стоящих у стрелок, ведущих слева направо (с начала и до данного состояния Sk,), а в знаменателе -- произведение всех интенсивностей, стоящих у стрелок, ведущих справа налево (с начала и до Sk).

Таким образом, все вероятности состояний р0, р1, ..., рn выражены через одну из них (р0). Подставим эти выражения в нормировочное условие (19.3). Получим, вынося за скобку p0:

отсюда получим выражение для р0:

Все остальные вероятности выражены через р0 (см. формулы (19.4) - (19.7)). Коэффициенты при р0 в каждой из них представляют собой последовательные члены ряда, стоящего после единицы в формуле (19.8). Значит, вычисляя р0, мы уже нашли все эти коэффициенты.

Полученные формулы применяются при решении простейших задач теории массового обслуживания.

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

Граф состояний процесса гибели и размножения имеет вид, показанный на рис. 15.4.

Рис. 15.4

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

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

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

В соответствии с правилом составления таких уравнений (см. 15.10) получим: для состояния S 0

для состояния S,

Которое с учетом (15.12) приводится к виду

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

(15.14)

к которой добавляется нормировочное условие

Решая систему (15.14), (15.15), можно получить

(15.16)

Легко заметить, что в формулах (15.17) для коэффициенты при есть слагаемые, стоящие после единицы в формуле (15.16). Числители этих коэффициентов представляют произведение всех интенсивностей, стоящих у стрелок, ведущих слева направо до данного состояния , а знаменатели – произведение всех интенсивностей,стоящих у стрелок, ведущих справа налево из состояниядо.

15.4. Процесс гибели и размножения представлен графом (рис. 15.5). Найти предельные вероятности состояний.

Рис. 15.5

Решение. По формуле (15.16) найдем

по (15.17) т.е. в установившемся, стационарном режиме в среднем 70,6% времени система будет находиться в состоянии 5(), 17,6% – в состоянии 5, и 11,8% – в состоянии S2.

СМО с отказами

В качестве показателей эффективности СМО с отказами будем рассматривать:

А – абсолютную пропускную способность СМО, т.е. среднее число заявок, обслуживаемых в единицу времени;

Q – относительную пропускную способность, т.е. среднюю долю пришедших заявок, обслуживаемых системой;

Р тк – вероятность отказа, т.е. того, что заявка покинет СМО необслуженной;

k – среднее число запятых каналов (для многоканальной системы).

Одноканальная система с отказами. Рассмотрим задачу.

Имеется один канал, на который поступает поток заявок с интенсивностью λ. Поток обслуживаний имеет интенсивность μ . Найти предельные вероятности состояний системы и показатели ее эффективности.

Система 5 (СМО) имеет два состояния: 50 – канал свободен, 5, – канал занят. Размеченный граф состояний представлен на рис. 15.6.

При установлении в СМО предельного, стационарного режима процесса система алгебраических уравнений для вероятностей состояний имеет вид (см. правило составления таких уравнений на с. 370):

т.е. система вырождается в одно уравнение. Учитывая нормировочное условие р 0+р х = 1, найдем из (15.18) предельные вероятности состояний

(15.19)

которые выражают среднее относительное время пребывания системы в состоянии 50 (когда канал свободен) и 5, (когда канал занят), т.е. определяют соответственно относительную пропускную способность Q системы и вероятность отказа:

Абсолютную пропускную способность найдем, умножив относительную пропускную способность Q на интенсивность потока заявок

15.5. Известно, что заявки на телефонные переговоры в телевизионном ателье поступают с интенсивностью λ, равной 90 заявок в час, а средняя продолжительность разговора по телефонумин. Определить показатели эффективности работы СМО (телефонной связи) при наличии одного телефонного номера.

Решение. Имеем λ = 90 (1 /ч),мин. Интенсивность потока обслуживании μ = 1/ίο6 = 1/2 = 0,5 (1/мин) = = 30 (1/ч). По (15.20) относительная пропускная способность СМО Q = 30/(90 + 30) = 0,25, т.е. в среднем только 25% поступающих заявок составят переговоры по телефону. Соответственно, вероятность отказа в обслуживании составит Р тк = 0,75 (см. (15.21)). Абсолютная пропускная способность СМО но (15.22) А = 90 ∙ 0,25 = 22,5, т.е. в среднем в час будут обслужены 22,5 заявки на переговоры. Очевидно, что при наличии только одного телефонного номера СМО будет плохо справляться с потоком заявок.

Многоканальная система с отказами. Рассмотрим классическую задачу Эрланга.

Имеется п каналов, на которые поступает поток заявок с интенсивностью λ. Поток обслуживаний каждого канала имеет интенсивность μ. Найти предельные вероятности состояний системы и показатели ее эффективности.

Система S (СМО) имеет следующие состояния (нумеруем их по числу заявок, находящихся в системе):

где– состояние системы, когда в ней находится k заявок, т.е. занято k каналов.

Граф состояний СМО соответствует процессу гибели и размножения и показан на рис. 15.7.

Рис. 15.7

Поток заявок последовательно переводит систему из любого левого состояния в соседнее правое с одной и той же интенсивностью λ. Интенсивность же потока обслуживаний, переводящих систему из любого правого состояния в соседнее левое, постоянно меняется в зависимости от состояния. Действительно, если СМО находится в состоянии S., (два канала заняты), то она может перейти в состояние 5, (один канал занят), когда закончит обслуживание либо первый, либо второй канал, т.е. суммарная интенсивность их потоков обслуживаний будет 2μ. Аналогично суммарный поток обслуживаний, переводящий СМО из состояния 53 (три канала заняты) в 52, будет иметь интенсивность 3μ, т.е. может освободиться любой из трех каналов и т.д.

В формуле (15.16) для схемы гибели и размножения получим для предельной вероятности состояния

(15.23)

где члены разложениябудут представлять собой коэффициенты при р а в вы́ражениях для предельных вероятностейВеличина

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

(15.25)

Формулы (15.25) и (15.26) для предельных вероятностей получили названия формул Эрланга в честь основателя теории массового обслуживания.

Вероятность отказа СМО есть предельная вероятность того, что все п каналов системы будут заняты, т.е.

Относительная пропускная способность – вероятность того, что заявка будет обслужена:

(15.28)

Абсолютная пропускная способность:

(15.29)

Среднее число (математическое ожидание числа) занятых каналов:

где/;, – предельные вероятности состояний, определяемых но формулам (15.25), (15.26).

Однако среднее число занятых каналов можно найти проще, если учесть, что абсолютная пропускная способность системы А есть не что иное, как интенсивность потока обслуженных системой заявок (в единицу времени). Так как каждый занятый канал обслуживает в среднем μ заявок (в единицу времени), то среднее число занятых каналов

или, учитывая (15.29), (15.24):

15.6. В условиях задачи 15.5 определить оптимальное число телефонных номеров в телевизионном ателье, если условием оптимальности считать удовлетворение в среднем из каждых 100 заявок нс менее 90 заявок на переговоры.

Решение. Интенсивность нагрузки канала по формуле (15.24) р = 90/30 = 3, т.е. за время среднего (по продолжительности) телефонного разговора 7об = 2 мин поступает в среднем 3 заявки на переговоры.

Будем постепенно увеличивать число каналов (телефонных номеров) п = 2, 3, 4, ... и определим по формулам (15.25–15.29) для получаемой и-канальной СМО характеристики обслуживания. Например, при п = 2 р 0 = = (1 + 3 + 32/2!)“" =0,118 ≈ 0,12; Q = 1 – (з2/2l) – 0,118 = 0,47. А = 90 ∙ 0,47 = 42,3 и т.д. Значения характеристик СМО сведем в табл. 15.1.

Таблица 15.1

По условию оптимальности Q > 0,9, следовательно, в телевизионном ателье необходимо установить 5 телефонных номеров (в этом случае Q = 0,90 – см. табл. 15.1). При этом в час будут обслуживаться в среднем 80 заявок (А = 80,1), а среднее число занятых телефонных номеров (каналов) по формуле (15.30) к = 80,1/30 = 2,67.

15.7. В вычислительный центр коллективного пользования с тремя ЭВМ поступают заказы от предприятий на вычислительные работы. Если работают все три ЭВМ, то вновь поступающий заказ не принимается, и предприятие вынуждено обратиться в другой вычислительный центр. Среднее время работы с одним заказом составляет 3 ч. Интенсивность потока заявок 0,25 (1/ч). Найти предельные вероятности состояний и показатели эффективности работы вычислительного центра.

Решение. По условию п = 3, λ = 0,25 (1 /ч),^ = 3 (ч). Интенсивность потока обслуживаний μ=1/ίο6 =1/3 = = 0,33. Интенсивность нагрузки ЭВМ по формуле (15.24) р = 0,25/0,33 = 0,75. Найдем предельные вероятности состояний:

по формуле (15.25) р0 = (1 + 0,75 + 0,752/2!+ 0,753/3!) = 0,476;

по формуле (15.26) р, =0,75 0,476 = 0,357; р 2 = (θ,752/2ΐ)χ хО,476 = 0,134; р 3 = (θ,753/3ΐ) 0,476 = 0,033, т.е. в стационарном режиме работы вычислительного центра в среднем 47,6% времени нет ни одной заявки, 35,7% – имеется одна заявка (занята одна ЭВМ), 13,4% – две заявки (две ЭВМ), 3,3% – три заявки (заняты три ЭВМ).

Вероятность отказа (когда заняты все три ЭВМ), таким образом, Ртк = р 3 = 0,033.

По формуле (15.28) относительная пропускная способность центра <2= 1 – 0,033 = 0,967, т.е. в среднем из каждых 100 заявок вычислительный центр обслуживает 96,7 заявок.

По формуле (15.29) абсолютная пропускная способность центра А = 0,25-0,967 = 0,242, т.е. в один час в среднем обслуживается 0,242 заявки.

По формуле (15.30) среднее число занятых ЭВМ к = = 0,242/0,33 = 0,725, т.е. каждая из трех ЭВМ будет занята обслуживанием заявок в среднем лишь на 72,5/3 = 24,2%.

При оценке эффективности работы вычислительного центра необходимо сопоставить доходы от выполнения заявок с потерями от простоя дорогостоящих ЭВМ (с одной стороны, у нас высокая пропускная способность СМО, а с другой стороны – значительный простой каналов обслуживания) и выбрать компромиссное решение.

Введение

В данной работе будет рассмотрена схема непрерывных марковских цепей - так называемая "схема гибели и размножения"

Процесс размножения и гибели - это случайный процесс со счётным (конечным или бесконечным) множеством состояний, протекающий в дискретном или непрерывном времени. Он состоит в том, что некоторая система в случайные моменты времени переходит из одного состояния в другое, причём переходы между состояниями происходят скачком, когда наступают некоторые события. Как правило, эти события бывают двух типов: одно из них условно называют рождением некоторого объекта, а второе - гибелью этого объекта.

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

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

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

Процессы размножения и гибели

Процессы размножения и гибели являются частным случаем марковских случайных процессов, которые, тем не менее, находят весьма широкое применение при исследовании дискретных систем со стохастическим характером функционирования. Процесс размножения и гибели представляет собой марковский случайный процесс, в котором переходы из состояния E i допустимы только в соседние состояния E i-1 , E i и E i+1 . Процесс размножения и гибели является адекватной моделью для описания изменений, происходящих в объеме биологических популяций. Следуя этой модели, говорят, что процесс находится в состоянии E i , если объем популяции равен i членам. При этом переход из состояния E i в состояние E i+1 соответствует рождению, а переход из E i в E i-1 - гибели, предполагается, что объем популяции может изменяться не более чем на единицу; это означает, что для процессов размножения и гибели не допускаются многократные одновременные рождения и/или гибели .

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

В случае процесса размножения и гибели с дискретным временем вероятности переходов между состояниями

Здесь d i - вероятность того, что на следующем шаге (в терминах биологической популяции) произойдет одна гибель, уменьшающая объем популяции до при условии, что на данном шаге объем популяции равен i. Аналогично, b i - вероятность рождения на следующем шаге, приводящего к увеличению объема популяции до; представляет собой вероятность того, что ни одно из этих событий не произойдет и на следующем шаге объем популяции не изменится. Допускаются только эти три возможности. Ясно, что, так как гибель не может наступить, если некому погибать .

Однако в противовес интуиции допускается, что, что соответствует возможности рождения, когда в популяции нет ни одного члена. Хотя это можно расценивать как спонтанное рождение или божественное творение, но в теории дискретных систем такая модель представляет собой вполне осмысленное допущение. А именно, модель такова: популяция представляет собой поток требований, находящихся в системе, гибель означает уход требования из системы, а рождение соответствует поступлению в систему нового требования. Ясно, что в такой модели вполне возможно поступление нового требования (рождение) в свободную систему. Матрица вероятностей переходов для общего процесса размножения и гибели имеет следующий вид:

Если цепь Маркова является конечной, то последняя строка матрицы записывается в виде ; это соответствует тому, что не допускаются никакие размножения после того, как популяция достигает максимального объема n. Матрица T содержит нулевые члены только на главной диагонали и двух ближайших к ней диагоналях. Из-за такого частного вида матрицы T естественно ожидать, что анализ процесса размножения и гибели не должен вызывать трудностей . Далее будем рассматривать только непрерывные процессы размножения и гибели, в которых переходы из состояния E i возможны только в соседние состояния E i-1 (гибель) и E i+1 (рождение). Обозначим через i интенсивность размножения; она описывает скорость, с которой происходит размножение в популяции объема i. Аналогично, через i обозначим интенсивность гибели, задающую скорость с которой происходит гибель в популяции объема i. Заметим, что введенные интенсивности размножения и гибели не зависят от времени, а зависят только от состояния E i , следовательно, получаем непрерывную однородную цепь Маркова типа размножения и гибели. Эти специальные обозначения введены потому, что они непосредственно приводят к обозначениям, принятым в теории дискретных систем. В зависимости от ранее введенных обозначений имеем:

i = q i,i+1 и i = q i,i-1 .

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

получим q ii =-(i + i). Таким образом, матрица интенсивностей переходов общего однородного процесса размножения и гибели принимает вид:

Заметим, что за исключением главной диагонали и соседних с ней снизу и сверху диагоналей все элементы матрицы равны нулю. Соответствующий граф интенсивностей переходов представлен на соответствующем рисунке (2.1) :

Рисунок 2.1 - Граф интенсивностей переходов для процесса размножения и гибели

Более точное определение непрерывного процесса размножения и гибели состоит в следующем: некоторый процесс представляет собой процесс размножения и гибели, если он является однородной цепью Маркова с множеством состояний {E 0 , E 1 , E 2 , …}, если рождение и гибель являются независимыми событиями (это вытекает непосредственно из марковского свойства) и если выполняются следующие условия:

(точно 1 рождение в промежутке времени (t,t+Дt), объем популяции равен i) ;

(точно 1 гибель в промежутке времени (t,t+Дt)| объем популяции равен i);

= (точно 0 рождений в промежутке времени (t,t+Дt)| объем популяции равен i);

= (точно 0 гибелей в промежутке времени (t,t+Дt)| объем популяции равен i).

Таким образом, ?t с точностью до есть вероятность рождения новой особи в популяции из n особей, а - вероятность гибели особи в этой популяции за время .

Вероятности перехода удовлетворяют обратным уравнения Колмогорова. Таким образом, вероятность того, что непрерывный процесс размножения и гибели в момент времени t находится в состоянии E i (объем популяции равен i) определяется в виде (2.1):

Для решения полученной системы дифференциальных уравнений в нестационарном случае, когда вероятности P i (t), i=0,1,2,…, зависят от времени, необходимо задать распределение начальных вероятностей P i (0), i=0,1,2,…, при t=0. Кроме того, должно удовлетворяться нормировочное условие.

Рассмотрим теперь простейший процесс чистого размножения, который определяется как процесс, для которого i = 0 при всех i. Кроме того, для еще большего упрощения задачи предположим, что i = для всех i=0,1,2,... . Подставляя эти значения в уравнения (2.1) получим (2.2):

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

Отсюда для P 0 (t) получаем решение:

Подставляя это решение в уравнение (2.2) при i = 1, приходим к уравнению:

Решение этого дифференциального уравнения, очевидно, имеет вид:

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

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

перейдем к определению предельных вероятностей P i . Уравнения для определения вероятностей стационарного режима можно получить непосредственно из (2.1), учитывая, что dP i (t)/dt = 0 при:

Полученная система уравнений решается с учетом нормировочного условия (2.4):

Систему уравнений (2.3) для установившегося режима процесса размножения и гибели можно составить непосредственно по графу интенсивностей переходов на рисунке 2.1, применяя принцип равенства потоков вероятностей к отдельным состоянием процесса. Например, если рассмотреть состояние E i в установившемся режиме, то:

интенсивность потока вероятностей в и

интенсивность потока вероятностей из.

В состоянии равновесия эти два потока должны быть равны, и поэтому непосредственно получаем:

Но это как раз и есть первое равенство в системе (2.3). Аналогично можно получить и второе равенство системы. Те же самые рассуждения о сохранении потока, которые были приведены ранее, могут быть применены к потоку вероятностей через любую замкнутую границу. Например, вместо того, чтобы выделять каждое состояние и составлять для него уравнение, можно выбрать последовательность контуров, первый из которых охватывает состояние E 0 , второй - состояние E 0 и E 1 , и так далее, включая каждый раз в новую границу очередное состояние. Тогда для i-го контура (окружающего состояния E 0 , E 1 ,..., E i-1) условие сохранения потока вероятностей можно записать в следующем простом виде:

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

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

Решение системы (2.5) можно найти методом математической индукции.

При i=1 имеем

Вид полученных равенств показывает, что общее решение системы уравнений (2.5) имеет вид:

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

Таким образом, все вероятности P i для установившегося режима выражаются через единственную неизвестную константу P 0 . Равенство (2.4) дает дополнительное условие, позволяющее определить P 0 . Тогда, суммируя по всем i, для P 0 получим (2.7) :

Обратимся к вопросу о существовании стационарных вероятностей P i . Для того чтобы полученные выражения задавали вероятности, обычно накладывается требование, чтобы P 0 >0. Это, очевидно, налагает ограничение на коэффициенты размножения и гибели в соответствующих уравнениях. По существу требуется, чтобы система иногда опустошалась; это условие стабильности представляется весьма резонным, если обратиться к примерам реальной жизни. Если растут слишком быстро по сравнению с, то может оказаться, что с положительной вероятностью в конечный момент времени t процесс уйдёт из фазового пространства {0,1,…} в "бесконечно удаленную точку?" (особей в популяции станет слишком много). Другими словами процесс станет не регулярным, и тогда равенство (2.4) будет нарушено. Определим следующие две суммы:

Для регулярности процесса размножения и гибели необходимо и достаточно, чтобы S 2 = .

Для существования его стационарного распределения необходимо и достаточно, чтобы S 1 < .

Для того чтобы все состояния E i рассматриваемого процесса размножения и гибели были эргодическими необходимо и достаточно сходимости ряда S 1 < , при этом ряд должен расходиться S 2 = . Только эргодический случай приводит к установившимся вероятностям P i , i = 0, 1, 2, …, и именно этот случай представляет интерес. Заметим, что условия эргодичности выполняются, например, когда, начиная с некоторого i, все члены последовательности {} ограничены единицей, т. е. тогда, когда существует некоторое i 0 (и некоторое С<1) такое, что для всех ii 0 выполняется неравенство:

Этому неравенству можно дать простое толкование: начиная с некоторого состояния E i и для всех последующих состояний интенсивность потока размножения, должна быть меньше интенсивности потока гибели .

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

Рисунок 2.2 - Граф интенсивностей переходов для процесса "чистого" размножения

Аналогично вводится понятие "чистой" гибели. Процессом "чистой" гибели называется такой процесс гибели и размножения, у которого интенсивности всех потоков размножения равны нулю. Граф состояний такого процесса без ограничения на число состояний показан на рисунке:

Рисунок 2.3 - Граф интенсивностей переходов для процесса "чистой" гибели

Система уравнения Колмогорова для таких процессов может быть получена из системы уравнений (2.1), в которой нужно положить все интенсивности потоков процессов гибели равными нулю: .

§ 1. ОБЩИЕ ПРОЦЕССЫ ЧИСТОГО РОЖДЕНИЯ (РАЗМНОЖЕНИЯ) И ПУАССОНОВСКИЕ ПРОЦЕССЫ

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

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

не зависит от

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

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

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

А. Постулаты пуассоновского процесса

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

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

Свойство (1) можно записать еще так.

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

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

Характеристический признак этого графа состоит в том, что каждое из состояний s 2 ,..., s k ,..., s n l связано стрелками переходов в обе стороны с каждым из своих соседних состояний слева и справа, а первое и последнее состояния Sj и s n связаны стрелками в обе стороны только с одним своим соседним состоянием: соответственно с s 2 и s n _ v Таким образом, система S, в которой протекает процесс гибели и размножения, может из любого своего состояния непосредственно перейти только в одно из его соседних состояний. При этом под «размножением» будем понимать процесс по стрелкам слева направо, а под «гибелью» - процесс по стрелкам справа налево.

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

Рассмотрим процесс гибели и размножения с непрерывным временем и с размеченным графом состояний на рис. 11.2.

Матрица плотностей вероятностей переходов процесса гибели и размножения представлена в таблице (с. 124).

Для вероятностей состояний /?,(/), p 2 (t), ...,p k (t), -,Р п _ { (/), P n (t) можно по одному из двух правил, данных в § 4, составить систему дифференциальных уравнений Колмогорова, которая для данного случая будет иметь вид (11.1):

Если марковский процесс однороден (т.е. пуассоновские потоки стационарны), то плотности вероятностей переходов (интенсивности потоков) Ху в системе (11.1) не зависят от времени t; в противном случае Ху представляют собой некоторые функции времени: Ху = Xy(t).

Система (11.1) решается при начальном распределении вероятностей /7j(0), ..., р п { 0), удовлетворяющих нормировочному условию /?j(0) + ... + /> п (0) = 1. Решение системы (11.1) также должно удовлетворять нормировочному условиюp x {t) +... + p n (t ) = 1 в любой момент времени t.

Из графа состояний однородного процесса гибели и размножения (см. рис. 11.1) непосредственно усматривается эргодичность системы S. Поэтому из марковости процесса, по теореме 10.1, вытекает существование финальных вероятностей состоянийp v ..., р п.

Теорема 11.1. Финальные вероятности p v ..., р п процесса гибели и размножения с непрерывным временем можно вычислить по следующим формулам:

Доказательство: Составим по одному из трех правил, данных в § 10, систему линейных алгебраических уравнений:

(сравните с системой дифференциальных уравнений (11.1)).

Матрица коэффициентов системы (11.4) будет иметь следующий вид:

Для упрощения вида этой матрицы проведем следующие элементарные преобразования ее строк: 1-ю строку прибавим ко 2-й; полученную 2-ю строку прибавим к 3-й и т.д.; полученную (п - 1)-ю строку прибавим к п -й строке. В результате получим матрицу, последняя (п- я) строка которой - нулевая, и потому ее можно отбросить.

Таким образом, предельные вероятности состоянийp v ..., р п удовлетворяют системе линейных алгебраических уравнений, соответствующей матрице (11.5):

и нормировочному условию

Из 1-го уравнения системы (11.6) с учетом (11.3) при к= 2:

Из 2-го уравнения системы (11.6) с учетом (11.8) и (11.3) при к= 3: Из 3-го уравнения системы (11.6) с учетом (11.9) и (11.3) при к = 4: итак далее,

Таким образом, мы доказали справедливость формулы во второй строке (11.2). Для доказательства формулы в первой строке (11.2) подставим (11.8), (11.9), (11.10) в нормировочное условие (11.7):

откуда получим требуемое равенство

Правая часть формулы (11.3) устроена следующим образом: в числителе стоит произведение плотностей вероятностей переходов А,..,

начиная с А 12 12 и кончая Х к _ { к, где второй индекс к множителя Х к _ х к

совпадает с индексом а к, причем первый индекс каждого множителя A.j, начиная со второго А 23 , совпадает со вторым индексом предыдущего множителя; в знаменателе стоит произведение множителей получающееся из произведения в числителе, если в последнем у каждого множителя X.. поменять местами индексы: . г

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

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

S k ДО СОСТОЯНИЯ S J.

В формулах (11.2) все финальные вероятностиp v ..., р п выражены через финальную вероятность р у Можно было бы при решении системы (11.6) выразить их через любую другую предельную вероятность.

Часто нумерацию состояний системы S начинают не с единицы, а с нуля: s Q , s v ..., s n . В этом случае формулы (11.2) и (11.3) приобретают соответственно вид:

Пример 11.1. Данные, полученные при исследование рынка ценных бумаг, показали, что рыночная цена одной акции некоторого акционерного общества может колебаться в пределах от 1000 до 2000 руб. включительно. Рассматривая в качестве системы S одну такую акцию, нас будут интересовать следующие ее пять состояний, характеризующихся рыночной ценой акции:

Sj - от 1000 до 1200 руб.; s 2 - от 1200 до 1400 руб.;

• 5 3 - от 1400 до 1600 руб.; s 4 - от 1600 до 1800 руб.;
• 5 5 - от 1800 до 2000 руб. включительно.

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

Требуется спрогнозировать рыночную цену акции на будущее. Стоит ли приобретать акции по цене 1700 руб.?

Так как система S может находиться только в одном из отмеченных пяти состояний, то процесс, протекающий в системе 5, - дискретный.

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

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

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

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

Итак, в системе S протекает однородный марковский дискретный процесс с непрерывным временем.

По данной матрице Л построим размеченный граф состояний:

По этому графу видно (это можно было увидеть и по матрице Л), что данный процесс является процессом гибели и размножения. Финальные вероятности p v p v p v p v р 5 существуют. Найдем их по формуле (11.2) при « = 5. Для этого сначала по формуле (11.3) подсчитаем числа а 2 , а 3 , а 4 , а 5 .

Тогда по формуле в первой строке (11.2)

По формулам во второй строке (11.2):

Таким образом, вероятнее всего (р 3 = 16/39 > р р /=1,2,4, 5) система S будет находиться в состоянии s 3 53 , т.е. цена акции будет находиться в пределах от 1400 до 1600 руб. Поэтому покупать эти акции по цене 1700 руб. не стоит. ?

КРАТКИЕ ВЫВОДЫ

• Процесс гибели и размножения определяется как марковский однородный процесс с непрерывным временем, протекающий в системе S, граф конечного числа состояний которой имеет структуру на рис. 11.1.
• Для процесса гибели и размножения существуют финальные вероятности, которые можно найти из формул (11.2) или (11.1).

КЛЮЧЕВЫЕ СЛОВА И ВЫРАЖЕНИЯ

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

ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ

• 1. Дайте определение процесса гибели и размножения.
• 2. Каков характеристический признак структуры графа состояний системы, в которой протекает процесс гибели и размножения?
• 3. Какой вид имеет матрица плотностей вероятностей перехода для процесса гибели и размножения?
• 4. По каким формулам можно подсчитать финальные вероятности для процесса гибели и размножения?

ЗАДАНИЯ К § 11

11.1. Ответить на вопросы в примере 11.1, если матрица плотностей вероятностей переходов имеет вид

ОТВЕТЫ К ЗАДАНИЮ § 11