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

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

−интенсивности размножения, − интенсивности гибели.

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

(по Колмогорову), (1.14)

Подставляя (1.14) в (1.15), получим:

Для всех последующих состояний уравнения будут иметь одинаковый вид:

(
).

Чтобы определить все предельные вероятности, воспользуемся условием:
. Для этого выразимчерез:

. (1.16)

Введем обозначение
, тогда (1.14) и (1.16) запишутся в виде:.

Все оставшиеся вероятности выражаются через :

.

В результате получим выражение для :

.

Определив , можем рассчитать все.

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

Пусть задан процесс гибели и размножения:

Расчет предельных вероятностей:

;

;

;

Вопросы и задачи

1. Определить предельные вероятности состояний в марковской цепи, описываемой следующей матрицей вероятностей переходов. В начальный момент система находится в первом состоянии

2. Управляемый объект имеет 4 возможных состояния. Через каждый час производится снятие информации и перевод объекта из одного состояния в другое в соответствии со следующей матрицей вероятностей переходов:

Найти вероятности нахождения объекта в каждом из состояний после второго часа, если в начальный момент он находился в состоянии S 3.

3. По заданным коэффициентам системы уравнений Колмогорова составить размеченный граф состояний. Определить коэффициенты А, В, С, Д в уравнениях:

А Р1 + 4 Р2 + 5 Р3 = 0

В Р2 + 4 Р1 + 2 Р4 = 0

С Р3 + 2 Р2 + 6 Р1 = 0

Д Р4 + 7 Р1 + 2 Р3 = 0.

4. Физическая система имеет 4 состояния. Размеченный граф состояний приведен ниже.

Определить предельные вероятности состояний системы.

1.4. Пуассоновские смо

В пуассоновских СМО входной поток заявок – пуассоновский, т.е.
, а время обслуживания распределено по экспоненциальному закону
.

1.4.1. Одноканальные пуассоновские смо

СМО без очереди (N=0). Используем теорию процессов гибели и размножения для определения вероятностей
(рис. 1.9).


;

.

Вероятность отказа заявки в обслуживании равна :

.

Среднее число заявок в системе равно:

. (1.17)

Среднее время пребывания в СМО равно среднему времени обслуживания:

; (1.18)

так как очереди в СМО нет, то

Эффективный поток заявок определяется по формуле:

.

СМО с ограниченной очередью

Размеченный граф данного класса СМО представлен на рис. 1.10.

Конечное состояние в системе определяется максимальным числом мест в очереди плюс 1 канал обслуживания. Введем обозначение
. Система уравнений для нахождения предельных вероятностейимеет вид:

(1.19)

Учитывая, что
, получим уравнение для определения:


,

откуда получим
, где–любое, т.е. на отношение
не накладывается никаких ограничений.

Вероятности
.

Определим среднее число заявок в СМО:

.(1.20)

Обозначим через
, тогда

(1.21)

Подставив (1.20) в (1.21),получим:

. (1.22)

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

;

.

Используя формулы Литтла (1.1 – 1.3), получим:

; (1.23)

; (1.24)

. (1.25)

Рассмотрим частный случай, когда
, т.е.
. В этом случае:

;

.

Основные характеристики СМО определяются по следующим формулам:

СМО с неограниченной очередью. Так как СМО без отказов, то
, а
.

Для получения формул расчета характеристик СМО воспользуемся формулами для СМО с ограниченной очередью.

. (1.26)

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

Отметим, что в СМО с бесконечной очередью

. (1.27)

Предел (1.26) равен:
, и тогда

; (1.28)

; (1.29)

. (1.30)

Рассмотрим вопрос о функции распределения времени пребывания в одноканальной СМО с бесконечной очередью при дисциплине очереди FIFO .

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

Искомая плотность функции распределения определяется выражением:

С учетом (1.19) и (1.27),
запишется в виде:

Видим, что
− экспоненциальное распределение с математическим ожиданием
, что совпадает с (1.28).

Из того, что
− экспоненциальное распределение, следует важный вывод: выходной поток заявок в одноканальной СМО с бесконечной очередью является пуассоновским потоком.

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

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

Процесс находится в состоянии Ей, если объем (численность) популяции равен к; переход в состояние Ек соответствует гибели одного члена популяции, а переход в состояние Ек+ - рождению.

Этот процесс можно рассматривать как модель СМО, в которой Ек соответствует к заявок в системе, а переход в состояние Ек- или Ек+ - уходу заявки из системы или ее приходу.

Для процесса гибели и размножения с множеством состояний 0, 1,2, ... должны выполняться следующие условия:

Здесь P(+i; bt; к) - вероятность i рождений за время bt при условии, что численность популяции равна к ; P(-i; bt; к) - вероятность i гибелей при тех же условиях.

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

Найдем вероятность того, что объем популяции в некоторый момент времени равен к р(к, t) = P.

Рассмотрим изменение объема популяции в промежутке времени (t, t + 5/). В момент времени t + bt процесс будет находиться в состоянии Ек, если произошло одно из трех взаимно исключающих друг друга и образующих полную группу событий:

• 1) в момент времени t объем популяции равнялся А: и за время bt состояние не изменилось;
• 2) в момент времени t объем популяции равнялся к - 1 и за время bt родился один член популяции;
• 3) в момент времени t объем популяции равнялся к + 1 и за время bt погиб один член популяции.

Тогда вероятность того, что в момент времени t + bt процесс будет находиться в состоянии Ек, равна

Приведенное равенство имеет смысл только при к > О, поскольку популяция не может состоять из (-1) члена. Граничное равенство при к = О имеет вид:

Кроме того, должно выполняться условие нормировки

Выделяя в уравнениях (49.3) и (49.5) р(к) и деля на Ьк получим

Переходя к пределу при bt -> 0, имеем:

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

Рис. 49.2.

Состояние Ek обозначается овалом, в котором записывается число к. Переходы между состояниями обозначаются стрелками, на которых представлены интенсивности переходов.

Разность между интенсивностью, с которой система попадает в состояние Ek, и интенсивностью, с которой она покидает его, должна равняться интенсивности изменения потока в этом состоянии.

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

Интенсивность потока из состояния ~

Разность между ними равна эффективной интенсивности потока вероятностей в состояние

Решение этой системы в общем виде невозможно. Модель даже простой системы является чрезвычайно сложной и трудно анализируемой. Если рассматривать СМО более сложного вида, то вычислительные трудности будут еще более высокими. Поэтому обычно рассматривают решения системы (49.3) - (49.4) в установившемся режиме при t -> оо, р"(к; t) -> 0,р(к, t) -> р{к) = const.

Процесс чистого размножения

Для этого процесса р*=О, А* = А = const. Его можно рассматривать как модель потока заявок, поступивших в СМО. Система уравнений для этого процесса имеет вид:

Пусть начальные условия следующие:

Тогда и при к= 1 получим: ехр

Решение этого уравнения естьр (; /) = А/ exp (-АД По индукции можно получить, что

Таким образом, вероятности распределены по закону Пуассона.

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

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

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

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

не зависит от

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

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

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

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

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

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

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

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

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

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

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

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

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

Эти начальные условия единственным образом определяют решение системы (2). (В частности, ). Явные формулы для выводились независимо многими авторами, однако для нас они не представляют интереса.

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

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

Рис. 29

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

Марковская непрерывная цепь называется «процессом гибели и размножения», если ее граф состояний имеет вид, представленный на рис.29, т. е. все состояния можно вытянуть в одну цепочку, в кото­рой каждое из средних состояний (S 2 , ..., S n –1) связано прямой и об­ратной связью с каждым из соседних состояний, а крайние состояния (S 1 , S n) – только с одним соседним состоянием.

Пример 1. Техническое устройство состоит из трех одинаковых узлов; каждый из них может выходить из строя (отказывать); отказавший узел немедленно начинает восстанавливаться. Состояния систе­мы нумеруем по числу неисправных узлов:

S 0 – все три узла исправны;

S 1 – один узел отказал (восстанавливается), два исправны;

S 2 – два узла восстанавливаются, один исправен;

S 3 – все три узла восстанавливаются.

Граф состояний показан на рис.30. Из графа видно, что про­цесс, протекающий в системе, представляет собой процесс «гибели и размножения».

Рис. 30

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

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

Рис. 31

Напишем алгебраические уравнения для вероятностей состояний. Для первого состояния S 1 имеем:

λ 12 p 1 = λ 21 p 2 (7.1)

Для второго состояния S 2 суммы членов, соответствующих входя­щим и выходящим стрелкам, равны:

λ 23 p 2 + λ 21 p 2 = λ 32 p 3 + λ 12 p 1

Но, в силу (7.1), можно сократить справа и слева равные друг дру­гу члены и; получим:

λ 23 p 2 = λ 32 p 3

λ 34 p 3 = λ 43 p 4

. . . . . . . . .

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

λ k -1,k p k -1 = λ k,k -1 p k (7.2)

где k принимает все значения от 2 до n.

Итак, предельные вероятности состояний р 1 , р 2 , ..., р n в любой схеме гибели и размножения удовлетворяют уравнениям:

λ 12 p 1 = λ 21 p 2

λ 23 p 2 = λ 32 p 3

λ 34 p 3 = λ 43 p 4

. . . . . . . . . . . (7.3)

λ k -1,k p k -1 = λ k,k -1 p k

. . . . . . . . . . .

λ n -1, n p n -1 = λ n , n -1 p n

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

р 1 + р 2 + ... + р n = l (7.4)

Будем решать эту систему следующим образом: из первого урав­нения (7.3) выразим р 2:

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

(7.6)

Из третьего, с учетом (7.6):

(7.7)

Эта формула справедлива для любого k от 2 до n .

Обратим внимание на ее структуру. В числителе стоит произведе­ние всех плотностей вероятности перехода (интенсивностей) λ ij , стоя­щих у стрелок, направленных слева направо, с начала и вплоть до той, которая идет в состояние Sk ; в знаменателе – произве­дение всех интенсивностей λ ij , стоящих у стрелок, идущих справа налево, опять-таки, с начала и вплоть до стрелки, исходящей из состояния S k . При k =n в числителе будет стоять произведение интен­сивностей λ ij , стоящих у всех стрелок, идущих слева направо, а в знаменателе – у всех стрелок, идущих справа налево

Итак, все вероятности р 1 , р 2 , ..., р n выражены через одну из их: p 1. Подставим эти выражения в нормировочное условие: р 1 + р 2 + ... + р n = l Получим:

Остальные вероятности выражаются через p 1:

(7.9)

Таким образом, задача «гибели и размножения» решена в общем виде: найдены предельные вероятности состояний.

Пример 2. Найти предельные вероятности состояний для процесса гибели и размножения, граф которого показан на рис. 32.

Рис. 32

Решение. По формулам (7.8) и (7.9) имеем:

Пример 3. Прибор состоит из трех узлов; поток отказов – простейший, среднее время безотказной работы каждого узла равно . Отказавший узел сра­зу же начинает ремонтироваться; среднее время ремонта (восстановления) узла равно ; закон распределения этого времени показательный (поток восста­новлений простейший). Найти среднюю производительность прибора, если при трех работающих узлах она равна 100%, при двух – 50%, а при одном и менее – прибор вообще не работает.

Решение. Перечень состояний системы и граф состояний уже приводились в примере 1 данного параграфа. Разметим этот граф, т. е. проставим у каждой стрелки соответствующую интенсивность λ ij (см. рис. 33.).

Рис. 33.

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

По стрелкам вправо систему переводят отказы. Если система на­ходится в состоянии S 0 , то работают три узла; каждый из них подвергается по­току отказов с интенсивностью ; значит, поток отказов, действующий на всю систему, в три раза более интенсивен: = 0,5 и

Средняя производительность прибора в установившемся режиме:

Номинала.

Происхождение термина «схема гибели и размножения» ведет начало от биоло­гических задач, где подобной схемой описывается процесс изменения числен­ности популяции