Курс_лекций_по_теории_случайных_процессов

§ 15. Свойства марковских процессов

111

[SN(t); t) интегрирования. Обозначим интеграл, стоящий под знаком суммы через Yn. Величины Yn являются независимыми и для всех n 6= 1 одинаково распределенными с.в. (распределение первой величины, также как и первого интервала зависит от начального состояний процесса). Следовательно, по закону больших чисел простому и усиленному

N(t)

1 X

N(t) n=1

Yn ! MeY2

по вероятности и с вероятностью 1. Далее, из теории восстановления следует, что при t ! 1

N(t)	1
	!		;
t		MeS2

что доказывает первое равенство в формуле (15.19).

Для положительно–возвратного процесса вычисления показывают, что

S1

Z

X

Me g(X(u))du = kg(k)fee:

0k2E

Действительно, если g( ) = 1k(X(u)) индикаторная функция состояния k, тогда т.к. согласно результатам гл. 3 среднее число посещений состояния k между двумя посещениями состояния e равно mee=mkk, а среднее время пребывания процесса в состоянии k равно 1= k, то

Me	S1	1k(X(u))du = kmkk		= kfkk		= kfee;
	Z0
			mee		fee

где последнее равенство следует из замечания в конце предыдущего раздела о том, что fii = mii, откуда следует доказательство второго равенства для индикаторной функции.

Таким образом, для произвольной функции

		X
	g(X(u)) =	g(k)1k(X(u))
имеем		k2E
S1		S1
Me Z g(X(u))du = k E g(k)Me Z 1k(X(u))du = k E kg(k)fee;
	X		X
0	2	0	2

что после деления на MeS1(e) = fee приводит к формуле (15.19), где k = 1= kfkk предельная вероятность состояния k, что завершает доказательство.

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

15.5.Критерии положительной возвратности

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

Теорема 15.3. Любой неразложимый марковский процесс с конечным числом состояний jEj < 1 положительно возвратен.

112	Глава 4. Скачкообразные марк. и полумарк. процессы
Доказательство. Oчевидно.

Как следствие, для таких процессов эргодическая теорема выполняется всегда.

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

X

xi ij = 0

i2E

такого, что

X

jxij < 1:

i2E

При этом предельные вероятности равны ai = kxi + c.

Доказательство опускаем.

15.6.Дополнения

Вопросы для контроля.

1. Выпишите дифференциальные уравнения для вероятностей состояний марковского процес-

са.

2.Дайте определение времени достижения процессом некоторого состояния или множества состояний.

3.Дайте определение времени пребывания процесса в некотором множестве состояний.

4.Что называется инвариантным распределением марковского процесса.

5.Как вычислить инвариантное распределение марковского процесса.

6.Что такое система уравнений равновесия марковского процесса и как она выводится?

7.Сформулируйте предельную теорему для переходных вероятностей марковского процесса.

8.Сформулируйте эргодическую теорему для положительно возвратного марковского процес-

са.

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

Задачи.

1. Стандартный марковский процесс X задан своей матрицей интенсивностей переходов ,

23

5	3	2	5
= 4 2	4	2

13 4

Выпишите систему дифференциальных уравнений для вероятностей состояний pi(t). Найдите предельные вероятности.

2. Техническое устройство состоит из двух идентичных блоков. Блоки могут выходить из строя независимо друг от друга. Вероятность выхода из строя каждого блока, работающего в момент t, в промежутке (t, t + t) равна t + o( t) при t !0. Блоки также могут одновременно выйти из строя из-за сбоя электропитания, и вероятность этого для работающих в момент t блоков равна 0 t + o( t) при t !0. Для ремонта вышедших из строя блоков имеется одно ремонтное устройство. Если отказавший блок ремонтируется в момент t, то вероятность окончания ремонта в промежутке (t, t + t) равна t + o( t) при t !0. Если оба блока отказали, то один ремонтируется, а другой ждет своей очереди. Описать функционирование системы марковским

§ 15. Свойства марковских процессов

113

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

3. Стандартный марковский процесс X задан своей матрицей интенсивностей переходов и вектором начального распределения,

= 2	2	3	1	3;	=	0 0 1			:
4	3	1	2	5		@	1	A
	2	1	3				0

Найдите вероятности pk(t) (k = 1; 2; 3) состояний в момент времени t.

4. ([3]) Рассматривается процесс работы ЭВМ. Поток отказов (сбоев) работающей ЭВМ простейший с интенсивностью . Если ЭВМ дает сбой, то он немедленно обнаруживается, и обслуживающий персонал приступает к устранению неисправности (ремонту). Закон распределения времени ремонта показательный с параметром . В начальный момент (t = 0) ЭВМ исправна. Найдите:

(1)вероятность того, что в момент t ЭВМ будет работать;

(2)вероятность того, что за время (0; t) ЭВМ даст хотя бы один сбой; 3) предельные вероятности состояний ЭВМ.

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

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

6.([3]) Электронное техническое устройство состоит из двух одинаковых взаимозаменяемых узлов. Для работы устройства достаточно, чтобы работал хотя бы один узел. При выходе из строя одного из узлов устройство продолжает нормально функционировать за счет работы другого узла. Поток отказов каждого узла простейший с параметром . При выходе из строя узла он сразу начинает ремонтироваться. Время ремонта узла показательное с параметром . В начальный момент (при t = 0) оба узла работают. Найдите следующие характеристики работы устройства:

(1)вероятности состояний как функции времени: 0 исправны оба узла; 1 исправен один узел, другой ремонтируется; 2 ремонтируются оба узла (устройство не работает);

(2)вероятность p(t) того, что за время t устройство ни разу не прекратит работу;

(3)предельные вероятности состояний устройства;

(4)долю времени в стационарном режиме работы, в течение которого устройство будет находиться в исправном состоянии;

5) среднее время Tp бесперебойной работы устройства (от включения после восстановления до очередного выхода из строя) в стационарного режима.

7. ([3]) Техническое устройство подвержено простейшему потоку отказов с интенсивностью . Отказ обнаруживается не сразу, а через случайное время, распределенное показательно с параметром . Как только отказ обнаружен, производится осмотр устройства, в результате которого либо оно с вероятностью p направляется в ремонт, либо с допоплнительной вероятностью q = 1 p списывается и заменяется новым. Время осмотра имеет показательное с параметром , время ремонта показательное распределение с параметром , распределение времени замены списанного устройства новым показательное с параметром . Найдите предельные вероятности состояний устройства. Определите:

(1) какую долю времени в среднем устройство будет работать нормально;

114	Глава 4. Скачкообразные марк. и полумарк. процессы

(2)какую долю времени устройство будет работать с необнаруженым отказом (давать брак);

(3)какова средняя стоимость ремонтов устройства и его замен за единицу времени, если средняя стоимость ремонта равна r, а цена нового технического успройства равна c;

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

Библиографические замечания.

Уравнения для вероятностей состояний марковского процесса восходят, конечно, к работе Колмогорова [20], но теперь приводятся в любом учебнике по теории случайных процессов (см., например, [1, 2, 3, 4]). Подробное исследование характеристик дублированных систем надежности проведено в [25] (см. также [26]). Предельные и эргодические теоремы для марковских процессов также представляют собой стандартный материал учебных курсов по теории случайных процессов. Подход, связанный с использованием теории восстановления, в предложенном виде оригинален. Доказательство критерия положительной возвратности Фостера см. в [29].

§ 16. Процессы рождения и гибели

115

§16. Процессы рождения и гибели

16.1.Определение

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

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

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

ij = 8	i;	j = i + 1;
>	i;	j = i 1;
<	( i + i);	j = i:
>
:

Величины i и i называются интенсивностями рождения и гибели соответственно. Здесь предполагается, что 0 = 0, а в случае конечного пространства состояний E = f0; 1; 2; :::ng также и

n = 0.

Таким	образом, ПРГ полностью задается набором интенсивностей рождения и гибели
( i; i); i	= 0; 1; :::. Из определения следует, что матрица интенсивностей переходов имеет 3-

х диагональный вид, а граф переходов этого процесса имеет вид, изображенный на рис.16.1.

k-1 k
	0	q q q	k 1	k	q q q
			k k
0	1			k+1
	1			+1

Рис. 16.1. Размеченный граф переходов ПРГ

16.2.Уравнения Колмогорова

Как и в общем случае решение систем уравнений Колмогорова (13.2 – 13.4) для ПРГ редко удается найти в явном виде, а его представление в форме

P (t) = e t = X 1 k tk;

k 0 k!

малопригодно для фактических расчетов.

116	Глава 4. Скачкообразные марк. и полумарк. процессы

Для вектора вероятностей состояний p~(t) = (p0(t); : : : ; pk(t); : : : )0 относительно начального распределения , где

pk(t) = P fX(t) = kg

система уравнений Колмогорова для вероятностей состояний (15.3)

	d~p0(t)	= p~0	;
	dt
в координатной форме примет вид
pk(t) = k 1pk 1(t) ( k + k)pk(t) + k+1pk+1(t)				(16.1)
с начальным условием, задаваемым начальным распределением
= p~(0) = (ak;			k 2 E)0:	(16.2)

Эту систему в явном виде также удается решить не часто. Рассмотрим поэтому стационарные вероятности состояний.

16.3.Стационарные вероятности

Если k k > 0 для всех k 2 E, то ПРГ неразложим и в силу предельной теоремы для марковских процессов при условии его положительной возвратности (к выяснению этих условий мы вернемся несколько позже) пределы

lim pk(t) = k;

t!1

существуют и не зависят от начального распределения = p~(0). При этом, как следует из (16.1), они должны удовлетворять уравнениям

(

0 = 0 + 1 1;

(16.3)

0 = k 1ak 1 ( K + k)ak + k+1ak+1:

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

дополним систему уравнений (16.3) условием нормировки
X
k = 1:	(16.4)
k 0

Напомним, что система уравнений (16.3, 16.4) называется системой уравнений равновесия (СУР) или уравнениями глобального баланса. Для решения этой системы перепишем ее следующим образом:

(

k 1ak 1 kak = kak k+1ak+1 = 0;0a0 1a1 = 0:

Обозначив выражение вида kak k+1ak+1 через zk, получим рекуррентное соотношение

0 = z0 = = zk 1 = zk; k 1;

которое позволяет представить предельные вероятности в виде

=

k 1

k 1

=

=

k 1 0

;

k

1:

(16.5)

k

k

k 1 0

Для определения вероятности 0 воспользовавшись уравнением нормировки (16.4) найдем

01 1

0	=		1 +	0 k 1		:	(16.6)
		@	X		A
			k 1	1 k

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

§ 16. Процессы рождения и гибели

117

16.4.Условие положительной возвратности ПРГ

Условием того, чтобы все состояния были сообщающимися, является

k k > 0 для всех k 2 E:

(16.7)

Кроме того, для исключения мгновенных состояний предположим, что

k < 1; k < 1:

(16.8)

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

R1 =	X	1 k	;	R2	=	0 k 1 :
					X
	k 1 0 k				k 1	1 k

Теорема 16.1 (Карлин, Мак-Грегор). Пусть X(t) неразложимый процесс гибели и размножения с интенсивностями рождения и гибели ( k; k), k k > 0, тогда

(1)если R1 = 1, то процесс возвратен,

(2)если R1 = 1; R2 < 1 положительно возвратен,

(3)если R1 < 1 невозвратен.

Доказательство этой теоремы выходит за рамки данного учебника. Его можно найти в специальной литературе (см., например, [10]).

16.5.Дополнения

Вопросы для контроля.

1.Дайте определение процесса рождения и гибели.

2.Нарисуйте граф переходов для ПРГ.

3.Приведите выражения для инвариантных вероятностей ПРГ.

4.Приведите условия неразложимости возвратности и положительной возвратности ПРГ.

Упражнения.

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

Задачи.

1. (Система с резервированием.) Рассмотрим техническую систему, состоящую из трех одинаковых устройств, работающих независимо друг от друга. Для функционирования системы достаточно исправной работы двух устройств. Третье - резервное. Каждое устройство может выйти из строя. Тогда его нужно ремонтировать. Вероятность того, что работающее устройство в интервале (t; t+ t) выйдет из строя, равна t+o( t) при t ! 0. Восстановлением отказавших устройств занимается один оператор. Если в момент t имеется два или три отказавших устройства, то оператор занимается ремонтом того, которое отказало первым, а другое (или другие) ждут своей очереди. Вероятность того, что в интервале (t; t + t) оператор закончит ремонт устройства, равна t+o( t). Описать функционирование системы марковским процессом, записать систему дифференциальных уравнений для вероятностей состояний, найти предельные вероятности.

118	Глава 4. Скачкообразные марк. и полумарк. процессы

Библиографические замечания.

Процессы рождения и гибели возникли первоначально в качестве моделей изучения динамики популяций (для истории вопроса см., например, [10]). Однако, вскоре их начали использовать и в других многочисленных приложениях. С момента развития телефонии в начале XX века ПРГ активно используются в качестве моделей исследования и оптимизации телефонных систем (библиография на эту тему многочисленна, укажем лишь наиболее доступный для студентов учебник [5], а также [15]). В настоящее время проблемы ИНТЕРНЕТа и телекоммуникаций дали дальнейший толчек развитию скачкообразных марковских процессов и, в частности многомерных ПРГ, что привело к созданию теории стохастических сетей [27]. Во второй половине XX века на повестку дня выходят вопросы надежности оборудования и сложных технических систем и снова ПРГ активно используются для моделирования и изучения характеристик надежности систем (см., например, [28]).

§ 17. Примеры

119

§ 17. Примеры

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

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

Проверим для такого процесса условия теоремы Карлина и Мак-Грегора. Т.к. k = 0, то процесс невозвратен. Критерий устойчивости процесса имеет вид

P

8

1

=

9

= P

8

1

=

9

= 1;

<n 1 XTn

1=

<n 1 n

1=

X

X

т.е. условием устойчивости

процесса является расходимость ряда

1

. Следовательно, при

:

;

:

;

n

1

n

n = = const, например, процесс устойчив.

P

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

имеют вид		(17.1)
(pk(t) = k 1pk 1(t) kpk(t);
p0	(t) = 0p0(t);
c начальным условием	pk(0) = k0;	(17.2)

если процесс с вероятностью 1 выходит из нулевого состояния, и допускают аналитическое решение лишь в некоторых частных случаях.

Если интенсивности переходов k зависят от состояний процесса линейно, k ' k, то процесс устойчив, если же k ' k2, то процесс неустойчив, т.к. за конечное время процесс уходит в бесконечность.

Рассмотрим один частный случай, когда k = . Для вычисления распределения процесса X = fX(t); t 0g в этом случае обозначим через

X

P (z; t) = MzXt = zkpk(t)

его производящую функцию. Этот ряд сходится при jzj 1. Тогда из (17.1, 17.2) при k = имеем

dP (z; t)		=	P (z; t) + zP (z; t) = (1 z)P (z; t);	(17.3)
dt
P (z; 0)		=	1:	(17.4)

Отсюда

P (z; t) = Ce (1 z)t:

Подставив t = 0 получим, что C = 1, т.е.

P (z; t) = e (1 z)t:

Разложим функцию в ряд по степеням z:

e (1 z)t = e t X ( t)k zk; k!

k 0

а так как такое разложение единственно, то соответствующее распределение

pk(t) =	( t)k
	k! e t;	(17.5)

является пуассоновским, что оправдывает следующее определение.

120	Глава 4. Скачкообразные марк. и полумарк. процессы

Определение 17.1. Процесс чистого размножения с постоянными интенсивностями рождения

k = называется пуассоновским.

Замечание 1. Напомним, что в разделе 4.4. мы уже сталкивались с пуассоновским процессом, как процессом восстановления с показательно распределенными интервалами между восстановлениями (см. определение 4.3). Данное определение не противоречит предыдущему, просто пуассоновский процесс может быть определен разными способами. В качестве упражнения 2 покажите эквивалентность этих определений.

17.2.Процесс чистой гибели

Рассмотрим теперь другой частный случай ПРГ, когда все k > 0; k = 0. Тогда, очевидно, траектория процесса монотонно убывает с высотой ступенек 1.

Определение 17.2. Процессом чистой гибели называется ПРГ, все интенсивности рождения которого равны нулю, k = 0.

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

Пример 1. Дублированная система. Рассмотрим систему горячего дублирования без восстановления при котором длительности исправной работы в основном и резервном состояниях имеют показательные распределения с параметром (аналогичная система с восстановлением рассмотрена в примере 15.1)и исследуем распределение времени до первого отказа. Обозначим через X(t) число работающих (исправных) элементов в момент времени t. Тогда процесс X(t) является процессом чистой гибели с фазовым пространством E = f0; 1; 2g, интенсивностями гибели k = k k = 0; 1; 2 и поглощением и состоянии 0. Уравнения Колмогорова для вероятностей состояний для этого процесса примут вид

p2(t) = 2 p2(t);

p1(t)	=	p1(t) + 2 p2(t);
p0(t)	=	p1(t);

9

=

;

(17.6)

;

которую следует решать с начальным условием

p2(0) = 1; p1(0) = p0(0) = 0:

(17.7)

Так как нас интересует распределение времени T до отказа системы, которое имеет вид

FT (t) = PfT tg = p0(t);

то, как не трудно убедиться (решая систему, например, методом неопределенных коэффициентов), для этого распределения получим выражение

FT (t) = p0(t) = 1 2e t + e 2 t

из этой формулы следует, в частности, что среднее время работы дублированной системы системы без восстановления равно

11

mбез восст.	= Z (1 FT (t))dt =	Z (2e t e 2 t)dt =			= 2
		2	1		3

00