Заявка, заставшая все каналы занятыми, теряется. Сколько нужно иметь каналов, чтобы доля принятых заявок составляла не менее 90%? (См. пример 4.28 и исходные данные.)

Исходные данные к задаче 4.28.

№ l b № l b № l b № l b № l b № l b

1	3	7	6	8	8	11	6	9	16	5	10	21	4	12	26	4	10
2	4	8	7	9	7	12	7	8	17	6	8	22	5	11	27	5	12
3	5	9	8	3	9	13	8	7	18	7	9	23	6	7	28	3	8
4	6	10	9	4	7	14	3	10	19	8	9	24	3	12	29	6	11
5	7	7	10	5	8	15	4	9	20	3	11	25	4	11	30	3	9

4.4. Метод фаз Эрланга

Случайная величина X имеет распределение Эрланга порядкаk с параметром l > 0 , если ее функция плотности вероятности имеет вид

	fk	(x) =	lk		xk -1 e-lx ,	x ³ 0.
			(k -1)!
	На рис. 4.4.1 приведены				графики	распределения Эрланга при

значении параметра l =1 и разных значениях k.

		Рис. 4.4.1
При k =1 получается плотность показательного распределения.
Метод	фаз	Эрланга	применяется ,	ктогда	наряду	с
показательными	распределениями		в стохастической	системе	встречаются

распределения Эрланга.

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

317

можно считать состоящей изk независимых «фаз», каждая из которых имеет одно и то же показательное распределение.

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

Пример 4.29 (система Энгсета с потерями). Система обслуживания состоит из одного прибора. Из n независимых источников поступают требования. Время обслуживания любого требования имеет распределение Эрланга 3-го порядка с параметром μ. Из каждого источника поступает на обслуживание простейший поток заявок, интенсивности l. Интервалы между приходами требований из данного источника назовем паузами. Если требование застает прибор свободным, то начинает сразу обслуживаться. Пока происходит это обслуживание, из данного источника новых требований не поступает. После завершения обслуживания начинается отсчет новой паузы на данном источнике. Требуется найти долю времени, в течение которой прибор будет занят.

Решение. Выделим состояния системы: Е0 –– прибор свободен; Еi –– прибор занят i-й фазой обслуживания. Граф состояний системы изображен на рис. 4.4.2.

Рис. 4.4.2

Для вероятностей состояний системы в момент времениt можно составить систему уравнений:

P0¢(t) = -n lP0 (t) + mP3 (t),

¢
P (t) = nlP (t) - mP (t),
1		0	1
¢
P (t) = mP (t) - mP (t),
2	1		2
¢		(t) - mP3 (t).
P3	(t) = mP2

Тогда для стационарных вероятностей ( P (t) ¾¾¾®P ) получаем систему
	i	t®¥	i
–nlP0 + mP3 = 0,
nlP - mP = 0,
0	1
mP - mP = 0,
1	2

mP2 - mP3 = 0,

318

из которой P =

m

P ,

P = P = P .

Из условия нормировки P

æ m

+ 3

ö

=1.

ç

÷

0

ln

3

1

2

3

3

nl

m

è ln

ø

Поэтому P = P = P =

,

P =

.

Вероятность того,

что система

m + 3nl

3

1

2

m + 3nl

0

занята равна P

+ P + P

=

3nl

. .

1

2

3

m + 3nl

Ответ.

3nl

.

m + 3nl

Задача 4.29.1. В одноканальную систему массового обслуживания

поступает простейший поток требований на обслуживание интенсивности

λ. Времена обслуживания независимы и имеют распределение Эрланга

порядка k с

параметром

μ(в четных вариантах k = 2 ,

в

нечетных k = 3 ).

Требование, заставшее обслуживающий прибор занятым, теряется. Какова

вероятность потери требования? Решите задачу в общем виде, а затем

вычислите

искомую

вероятность

при равномλ

сумме

цифр

Вашего

варианта, а μ возьмите равным l / 2. (См. пример 4.29.)

Задача

4.29.2.

Интервалы

между

приходами

требований

в

одноканальную систему массового обслуживания имеют распределение

Эрланга k-го порядка с параметром («λвходящий поток Эрлангаk-го

порядка»). Времена обслуживания независимы и имеют показательное

распределение с параметром .μТребование, заставшее обслуживающий

прибор занятым, теряется. Какова вероятность потери требования? Решите

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

при λ

равном сумме

цифр

Вашего

варианта, а

μ возьмите

равным l / 2.

(См.

пример 4.29.)

Задача

4.29.3.

Для

вариантов 1–16: На

обслуживающий

прибор

поступает

поток

требований, интервалы между моментами прихода

которых независимы и имеют распределение Эрланга

порядкаk с

параметром l. Времена обслуживания независимы и имеют распределение

Эрланга

порядка m

с

параметромm. Требование,

заставшее

прибор

занятым, получает отказ и теряется (в символике Кендалла имеется в виду

система

массового

обслуживанияEk | Em |1| 0 ).

Найдите долю

времени

простоя системы и долю потерянных требований.

Для

вариантов 17–30. Система

обслуживания

состоит из

одного

прибора.

Из

n

независимых

источников

поступают

требования. Время

обслуживания любого требования имеет распределение Эрлангаm-го порядка с параметром μ. Из каждого источника поступает на обслуживание

319

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

поступает.			После		завершения			обслуживания				начинается			отсчет			новой
паузы на данном источнике. Требуется найти долю времени, в течение
которой прибор будет занят. (См. пример 4.29 и исходные данные.)
	Исходные данные к задаче 4.29.3.
№	k	m	№	k	m	№	k	m	№	k	m	№	k	m	№	k	m
1	1	3	6	3	2	11	5	2	16	5	3	21	3	3	26	6		2
2	2	2	7	1	6	12	3	4	17	2	2	22	3	4	27	6		3
3	1	4	8	2	4	13	4	3	18	2	3	23	5	2	38	6		4
4	2	3	9	4	2	14	4	1	19	2	4	24	5	3	29	7		2
5	1	5	10	2	5	15	3	5	20	3	2	25	5	4	30	7		3

4.5. Марковские процессы с дискретным множеством состояний. Цепи Маркова

Случайным процессом {X (t)}tÎT называется семейство случайных величин X (t) , зависящих от параметраt, который пробегает некоторое множество значений T. Предполагается, что все эти случайные величины определены на одном и том же вероятностном пространстве{W, A, P} и

принимают

действительные

значения. Множество

значений

будем

называть пространством состояний, а под параметромt будем понимать

время. Так

что величина X (t)

указывает

состояние

системы в

момент

времени t. Множество значений t может быть дискретным T ={0,1, 2,3,¼},

или

непрерывным T = [0,¥).

Иногда

вместо X (t)

будем

использовать

обозначение Xt.

Определение. Случайный процессXt

называется марковским,

если

для

любого

момента

времениt ÎT

=[0,¥)

развитие

процесса

в

0

последующие

моменты времени(при t > t0 )

зависит

только

от

состояния

процесса в момент времениt0

и

не зависит

от того, когда и как процесс

пришел в это состояние.

Пусть некоторый физический объект в каждый

момент времени

может находиться в одном из своих возможных состояний, число которых

конечно или

счетное. В этом случае иногда говорят о

дискретном

множестве

состояний.

Состояния

могут

быть

качественными

и

описываться

словами,

или

количественными

и

характеризоваться

некоторыми числами. Представление о множестве состояний и о структуре

переходов

из

состояния в

состояние

дает

,схемакоторая

называется

320

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

Рис. 4.5.1

Например, в графе состояний(рис. 4.5.1) E0 означает, что устройство новое и не включено в работу, E1 –– устройство работает, E2 –– устройство

неисправно, E –– происходит поиск причин неисправности, E ––

3 4

производится ремонт, E5 –– устройство признано не подлежащим ремонту и утилизировано. Если ремонт удался, то происходит переход в состояние

E1.

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

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

E0).

2.Состояние называется поглощающим (или концевым), если в него можно войти, но из него выйти нельзя (в приведенном примере состояние E5).

3.Состояние Ei называется соседним к состоянию Ej, если возможен непосредственный переход из состоянияEj в состояние Ei. В приведенном

примере E соседнее состояние по отношению Eк , но E не соседнее

3 2 2

состояние по отношению к E3.

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

Рис. 4.5.2

Например, в графе (см. рис. 4.5.2)два эргодических подмножества состояний: {E3 , E4 , E5} и {E6 , E7 }.

321

Случайный процесс изменения состояний объекта можно понимать

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

С

точки

зрения

описания

объекта

первостепенный

интер

представляют вероятности состояний этого объекта. Обозначим через Pi (t) ––

вероятность того, что в момент времени t объект находится в состоянии Ei.

Очевидно, что åPi (t) =1.

i

Часто

интерес

представляет

лишь

установившийся режим

работы

(или стационарный режим), в который объект входит после достаточно

долгого времени работы. При стационарном режиме процесс перехода из

состояния

в состояние продолжается, но вероятности состояний не

изменяются. Обозначим эти вероятности через Pi. Так что P = lim P (t).

i

t®¥

i

Величину Pi можно понимать как среднюю долю времени, в течение

которой объект находится в состоянииEi. В общем случае Pi (t)

зависят от

всей предыстории переходов из состояния в состояние до момента времени

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

математическом

плане

наиболее

просты

марковские

процессы, не

обладающие «памятью» о прошлом.

Еще

раз

повторим, что

случайный

процесс

с

дискретным

множеством состояний называется марковским, если для любого момента

времени t0 вероятность каждого из

его

состояний в будущем(при t > t0 )

зависит только от его состояния в настоящий момент и не зависит от того,

когда и как процесс пришел в это состояние.

Если переходы из состояния в состояние могут происходить только в

определенные моменты времениt0 ,t1,t2 ,..., то процесс называютцепью

Маркова. Моменты переходов из состояния в состояние называют шагами

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

игры, в которых продвижение фишки зависит от выпадения той или иной

грани игрального кубика.

Важными характеристиками марковской цепи являются условные

вероятности перехода системы наk-м шаге в состояниеEj, если на

предыдущем (k – 1) -м

шаге

она

была

в состоянииEi. Обозначим эти

вероятности

через Pij (k)

и

назовем

их переходными

вероятностями.

Вероятность

Pii (k )

можно

понимать, как

вероятность

сохранить

свое

состояние Ei на k-м шаге.

Переходные вероятности удобно записывать в виде прямоугольной таблицы (квадратной матрицы):

322

	æ P11 (k)		P12 (k ) K P1n (k ) ö
	ç P (k)		P (k) K P			(k)	÷
|| Р ||= ç		21	22		2n		÷ .
ij	ç	M	M	O	M		÷
	ç						÷
	è Pn1 (k ) Pn 2 (k ) K Pnn (k )						ø

Эту		матрицу называют		матрицей	переходных вероятностей или
просто переходной матрицей. Так как на каждом шаге система находиться
в одном из своих возможных состояний, то для любой строки матрицы
сумма	ее	элементов	равна	единице. Матрицы, обладающие		этим
свойством, называют стохастическими.
Для		однозначного в вероятностном смысле описания процесса
переходов из состояния в состояние нужно, помимо переходных матриц,
указать начальное распределение				состояний,	т.е. вероятности P (0), P (0),
					1	2

P3 (0),K, Pn (0). Обычно процесс начинается из определенного состояния Ei.

Тогда Pi =1, а Pj = 0 при	j ¹ i.
Цепь Маркова называется однородной, если переходные вероятности
не меняются от шага	к шагу, т.е. Pij (k) = Pij , и мы имеем одну и ту же
матрицу перехода || Рij ||	на каждом шаге.

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

Рис. 4.5.3

Графу состояний (рис. 4.5.3) соответствует переходная матрица

	æ	P	P	0	0	P	ö
	ç	11	12			15	÷
		0	P	P	0	0
	ç		22	23			÷
|| Рij	||= ç 0		0	P33	P34	0	÷	,
	ç	0	P42	P43	P44	P45	÷
	ç						÷
	ç P		0	0	0	P	÷
	è	51				55	ø

323

где

Р11 =1 – Р12 - Р15 ,

Р22 =1 – Р23 ,

Р33 =1 – Р34 ,

Р44 =1 – Р42 – Р43 - Р45 ,

Р55 =1 – Р51

(это

вероятности

сохранить

свое

состояние

на

очередном

шаге).

Пусть задано распределение состояний в начальный момент времени:

Р1 (0), Р2 (0), Р3 (0),K, Рn (0).

По

формуле

полной

вероятности

получаем

распределение состояний после первого шага:

n

Рj (1) = Р1 (0)Р1 j (1) + Р2 (0)Р2 j (1) +K+ Рn (0)Рnj (1) = åPi (0)Pij (1),

j =1, 2,K, n.

i=1

Используя полученные вероятности, можно по формуле полной

вероятности вычислить вероятности состояний на втором шаге:

Р

(2) = P (1)

Р

(2)

+ Р

(1)P

(2) +K+ Р

(1)

Р

(2) =

n

(1)P (2),

j =1, 2,K, n.

j

P

1

1 j

2

2 j

n

nj

å i

ij

i=1

Продолжение

этих

рассуждений

приводит

к

рекуррентному

соотношению

n

Pj (k) = åPi (k -1) Pij (k),

j =1, 2,K, n.

(4.5.1)

i=1

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

Pi = lim Pi (k).

k ® ¥

Условия существования финальных вероятностей:

1)множество всех состояний должно быть эргодическим;

2)цепь должна быть однородной(во всяком случае переходные

вероятности должны удовлетворять условию: Рij (k) ¾¾¾®Рij ).

k ® ¥

3) должно быть хорошее перемешивание состояний(не должно быть периодических циклов).

Например, для цепи с графом состояний

условие 3) не выполняется, так как при начале из состояния Е1 на нечетном шаге цепь будет находиться в состоянии Е2, а на четном — в состоянии Е1.

Если для однородной цепи финальное распределение существует, то

P = lim P (k),		Р (k) = Р (k – 1) ,
i	k ® ¥ i	ij	ij

и равенства (4.5.1) имеют вид

324

P			n
	=		PP , j =1, 2,K, n.
j		å i ij
			i=1
Иногда в этой записи выделяют слагаемые в правой части с Рjj. Тогда
		n
	å Pi Pij + Pj Pjj = Pj
	i=1(i¹ j )
или
n
å Pi Pij			+ Pj (Pjj	-1) = 0, j =1, 2,K, n.	(4.5.2)
i=1(i¹ j )
Для определения финальных				вероятностей нужно	решить систему

линейных однородных уравнений (4.5.2). Такая система всегда совместна,

(имеет

тривиальное

решениеРi

= 0

при

всехi). Если

же

есть

нетривиальные

решения,

то

их

бесконечно

много. Для

выбора

необходимого

единственного

решения

следует

добавить

условие

нормировки

P

+ P

+ P

+¼+ P =1.

1

2

3

n

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

	n
å Pi Pij + Pj (Pjj -1) 0,= j				1,2,=K, n;
i=1(i¹ j )					(4.5.3)
P	+ P	+ P	+¼+ P =1.
1	2	3	n
Пример 4.30. Граф состояний марковской цепи изображен на рис.
4.5.4. При начальном	распределенииP (0) =1,			P (0) = P (0) = 0 найти
			1	2	3
наименее вероятное состояние на третьем				.	шагеНайти финальные
вероятности состояний цепи.

Рис. 4.5.4

Решение. Переходная матрица этой цепи имеет вид

æ

P

P

P

ö

æ 0,5

0,5

0

ö

11

12

13

÷.

Р

=

ç P

P

P

÷

=

ç

0,2

0,1

0,7

ij

ç

21

22

23

÷

ç

0,1

0

0,9

÷

ç P

P

P

÷

ç

÷

è

31

32

33

ø

è

ø

325

Найдем вероятности состояний цепи на первом шаге. Воспользуемся формулой (4.5.1), но учтем, что переходные вероятности нам каждом шаге одинаковы (цепь однородная) и поэтому Pij (k) = Pij :

P (1) = P (0)P + P (0)P + P=(0)P							1×0,5 + 0 × 0,2 + 0 ×0,1= 0,5;
1	1	11	2	21	3	31
P (1) = P (0)P + P (0)P					+ P=(0)P		1×0,5 + 0 ×0,1 + 0 ×0 = 0,5;
2	1	12	2	22	3	32
P (1) = P (0)P + P (0)P					+ P (0)=P		1×0 + 0 ×0,7 + 0 ×0,9 = 0.
3	1	13	2	23	3	33

На втором шаге имеем вероятности состояний:

P (2) = P (1)P + P (1)P + P (1)=P									0,5 ×0,5 + 0,5 ×0,2 + 0 ×0,1 = 0,35;
1	1	11	2	21		3		31
P (2) = P (1)P + P (1)P					+ P (1)=P				0,5 × 0,5 + 0,5 ×0,1 + 0 ×0			0,3;=
2	1	12	2	22		3		32
P (2) = P (1)P + P (1)P					+ P (1)=P				0,5 ×0 + 0,5 ×0,7 + 0 ×0,9 = 0,35.
3	1	13	2	23		3		33
Для третьего шага получаем вероятности:
P (3) = P (2)P + P (2)P + P (2)= P									0,35 ×0,5 + 0,3 ×0,2 + 0,35 ×0,1 = 0,27;
1	1	11	2	21		3		31
P (2) = P (1)P + P (1)P					+ P=(1)P				0,35 ×0,5 + 0,3 ×0,1 + 0,35 ×0 = 0,205;
2	1	12	2	22		3		32
P (2) = P (1)P + P (1)P					+ P (1)=P				0,35 ×0 + 0,3 × 0,7 + 0,35 ×0,9 = 0,525.
2	1	12	2	22		3		32
Можно, повторяя вывод уравнений (4.5.1), для определения
финальных вероятностей записать систему равенств
Рj = Р1Р1 j	+ Р2Р2 j		+ Р3Р3 j ,		j =1, 2,3. Но проще составить систему (4.5.3):
				ì–0,5Р1 + 0, 2Р2 + 0,1Р3 = 0,
				ï
				í0,5Р1 – 0,9Р2 = 0,
				ï	Р	+ Р		+ Р	=1.
				î	1		2	3			получим Р1 = 9 / 49 @1 / 5,
Решая систему, например, по правилу Крамера,
Р2 = 5 / 49 @ 1 / 10,			Р3 = 35 / 49 @ 5 / 7 @ 0,7.							Эти	результаты означают, что
примерно 20% времени					цепь проведет в состоянииЕ1, 10% времени ––
состоянии Е2, 70% времени –– в состоянии Е3.
Ответ. Е2 –– наименее вероятное состояние на третьем шаге;
		Р1 = 9 / 49 ,			Р2 = 5 / 49 ,				Р3 = 35 / 49.
Задача 4.30.1. По заданному графу состояний марковской цепи
написать		переходную						матрицу			вероятностей. При		начальном
распределении			P (0) = 1,				P (0) = P (0) = P (0) = 0					найти	наиболее
			1					2	3	4

вероятное состояние на третьем шаге. Найти предельные (финальные) вероятности состояний цепи. В вариантах 1, 7, 13, 19, 25 использовать граф № 1; в вариантах 2, 8, 14, 20, 26 –– граф № 2; в вариантах 3, 9, 15, 21, 27 ––

граф № 3; в вариантах 4, 10, 16, 22, 28 – граф № 4; в вариантах 5, 11, 17, 23, 29 –– граф № 5; в вариантах 6, 12, 18, 24, 30 –– граф № 6. (См. пример 4.30

и исходные данные.)

Исходные данные к задаче 4.30.1.

№ a1 a2 a3 a4 a5 a6 a7 № a1 a2 a3 a4 a5 a6 a7

326

1	0,8	0,2	0,5	0,4	0,5	0,3	0,6
2	0,3	0,4	0,6	0,4	0,5	0,4	0,4
3	0,1	0,8	0,4	0,4	0,5	0,8	0,4
4	0,4	0,2	0,4	0,5	0,6	0,5	0,8
5	0,3	0,2	0,9	0,6	0,7	0,7	0,2
6	0,5	0,9	0,4	0,3	0,5	0,6	0,4
7	0,7	0,2	0,6	0,5	0,3	0,5	0,5
8	0,2	0,2	0,5	0,5	0,7	0,3	0,5
9	0,1	0,8	0,5	0,4	0,6	0,8	0,3
10	0,4	0,1	0,5	0,5	0,8	0,6	0,9
11	0,2	0,1	0,8	0,7	0,6	0,8	0,2
12	0,4	0,8	0,5	0,4	0,4	0,5	0,7
13	0,8	0,3	0,7	0,3	0,6	0,5	0,5
14	0,3	0,4	0,5	0,3	0,8	0,5	0,3
15	0,1	0,9	0,4	0,5	0,8	0,7	0,1

16	0,5	0,3	0,4	0,3	0,6	0,6	0,9
17	0,3	0,2	0,8	0,7	0,7	0,6	0,2
18	0,5	0,9	0,4	0,6	0,4	0,3	0,4
19	0,8	0,1	0,6	0,2	0,6	0,4	0,3
20	0,4	0,3	0,4	0,5	0,7	0,5	0,4
21	0,1	0,9	0,5	0,4	0,7	0,8	0,2
22	0,2	0,2	0,4	0,8	0,5	0,7	0,8
23	0,3	0,2	0,9	0,5	0,8	0,7	0,1
24	0,4	0,8	0,5	0,5	0,3	0,4	0,4
25	0,7	0,2	0,7	0,3	0,6	0,4	0,5
26	0,4	0,4	0,5	0,3	0,8	0,3	0,6
27	0,1	0,9	0,3	0,5	0,8	0,7	0,2
28	0,3	0,1	0,3	0,6	0,6	0,8	0,9
29	0,4	0,2	0,9	0,5	0,7	0,7	0,2
30	0,6	0,9	0,4	0,7	0,6	0,2	0,3

граф № 1

граф № 2

граф № 3

граф № 4

граф № 5

граф № 6

327

Задача 4.30.2. Происходит процесс случайного блуждания по

целочисленной решетке E = {0,1, 2,3, 4}. Обозначим через Ek						пребывание
частицы	в	точке	с	координатойk. Начальное	состояние	частицыEk,
k = 0,1, 2,3, 4.		Каждую		единицу времени	частица с	вероятностьюp
сдвигается	вправо, с		вероятностью q –– влево,		или остается	на месте с
вероятностью 1 – p – q .

Найдите вероятности состояний частицы на третьем шаге. Найдите стационарные (финальные) вероятности состояний частицы. (См. пример 4.30 и исходные данные; k –– остаток от деления номера варианта на5. Например, для 17 варианта k = 2 , так как 17 = 3 ×5 + 2 .)

Исходные данные к задаче 4.30.2.

№	p	q	№	p	q	№	p	q	№	p	q	№	p	q
1	0,2	0,4	7	0,1	0,7	13	0,3	0,1	19	0,5	0,2	25	0,2	0,1
2	0,3	0,5	8	0,2	0,3	14	0,1	0,5	20	0,6	0,3	26	0,1	0,3
3	0,4	0,3	9	0,1	0,4	15	1/3	1/4	21	0,3	0,4	27	0,5	0,1
4	0,2	0,5	10	0,4	0,5	16	0,1	0,3	22	0,7	0,1	28	1/4	1/3
5	0,6	0,2	11	0,2	0,7	17	0,4	0,2	23	0,5	0,4	29	1/3	1/5
6	0,3	0,6	12	0,1	0,2	18	0,2	0,6	24	0,7	0,2	30	0,5	0,3

Пример 4.31. В городе N каждый житель имел одну из профессий A,

B или C. Дети в следующем поколении сохраняли профессию отцов с вероятностями соответственно 0,6, 0,2 и 0,4 и с равными вероятностями выбирали любую из двух других профессий. Если в данный момент профессию A имеет 20% жителей города, профессию B –– 30%, а профессию C –– 50% жителей, то

1)каково распределение по профессиям будет в следующем поколении;

2)каким будет распределение по профессиям через много поколений (финальное распределение)?

328

Решение. Смену поколений будем считать шагом Марковской цепи.

Имеем	начальное	распределение(на			нулевом		шаге): PA (0) = 0, 2 ,
PB (0) = 0,3, PC (0) = 0,5 . Переходная матрица имеет вид:
			A	B	C
		A	0,6	0,2	0,2
		B	0,4	0,2	0,4
		C	0,3	0,3	0,4

В	соответствии	с	формулами(4.5.1) получаем распределение
вероятностей на первом шаге (в первом поколении):
	PA (1) = 0, 2 × 0, 6 + 0,3 × 0, 4 + 0,5 ×0,3 = 0,39;
	PB (1) = 0, 2 × 0, 2 + 0,3 × 0, 2 + 0,5 × 0,3 = 0, 25;
	PC (1) = 0, 2 × 0, 2 + 0,3 × 0, 4 + 0,5 × 0, 4 = 0,36.
Для	вычисления финальных вероятностей составляем систему
уравнений (4.5.2)
	PA = PA × 0,6 + PB ×0, 4 + PC × 0,3;
	PB =PA ×0, 2 + PB × 0, 2 + PC × 0,3;
	PC = PA ×0, 2 + PB × 0, 4 + PC × 0, 4.
Эта	система уравнений при условии нормировкиP + P			+ P =1
имеет решение			A B	C
	PA =18 / 39,		PB = 9 / 39, PC =12 / 39.
Ответ. PA =18 / 39,		PB = 9 / 39, PC =12 / 39.

Задача 4.31.1. Каждый житель некоторого города принадлежит к одной из социальных групп(богатые, средний класс, живущие за чертой бедности). По истечении года представительi-й группы сохраняет свой социальный статус с вероятностьюPi, или с равными вероятностями переходит в одну из двух других групп. Пусть в данный моментa% жителей богаты, b% относятся к среднему классу, c% живут в нищете.

Впредположении, что описанная социальная динамика остается

неизменной на протяжении многих, определителет финальный социальный состав жителей города. (См. пример 4.31 и исходные данные.)

Исходные данные к задаче 4.31.1.

	№	a	b	c	P1	P2	P3	№	a	b	c	P1	P2	P3
	1	5	65	35	0,9	0,5	0,9	16	5	65	35	0,9	0,6	0,9
	2	10	65	30	0,8	0,6	0,9	17	10	65	30	0,95	0,7	0,8
	3	10	60	30	0,7	0,8	0,9	18	10	60	30	0,9	0,5	0,9
	4	15	55	30	0,9	0,6	0,9	19	15	55	30	0,8	0,6	0,9
	5	10	70	20	0,95	0,7	0,8	20	10	70	20	0,7	0,8	0,9
	6	5	70	25	0,9	0,5	0,9	21	5	70	25	0,9	0,6	0,9
	7	15	65	20	0,8	0,6	0,9	22	15	65	20	0,95	0,7	0,8

329

8	8	70	22	0,7	0,8	0,9	23	8	70	22	0,9	0,5	0,9
9	5	65	35	0,9	0,6	0,9	24	5	65	35	0,8	0,6	0,9
10	10	65	30	0,95	0,7	0,8	25	10	65	30	0,7	0,8	0,9
11	10	60	30	0,9	0,5	0,9	26	10	60	30	0,9	0,6	0,9
12	15	55	30	0,8	0,6	0,9	27	15	55	30	0,95	0,7	0,8
13	10	70	20	0,7	0,8	0,9	28	10	70	20	0,9	0,5	0,9
14	5	70	25	0,9	0,6	0,9	29	5	70	25	0,8	0,6	0,9
15	15	65	20	0,95	0,7	0,8	30	15	65	20	0,7	0,8	0,9

Задача 4.31.2. Перед началом теледебатов зрители разделялись на три равные по численности группы: E1 –– сторонники кандидата A; E2 –– неопределившиеся; E3 –– сторонники кандидата B.

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

	E1	E2	E3
E1	P11	P12	P13
E2	P21	P22	P23
E3	P31	P32	P33

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

Исходные данные к задаче 4.31.2.

№	P11	P12	P21	P22	P31	P32
1	0,9	0,1	0,1	0,8	0	0,2
2	0,8	0,2	0,1	0,8	0,1	0,1
3	0,9	0,1	0,05	0,8	0	0,05
4	0,8	0,15	0,1	0,8	0	0,1
5	0,9	0,05	0,1	0,8	0	0,2
6	0,9	0,1	0,1	0,8	0	0,05
7	0,8	0,2	0,05	0,9	0	0,1
8	0,9	0,1	0,1	0,8	0	0,2
9	0,8	0,15	0,1	0,8	0	0,2
10	0,9	0,05	0,1	0,8	0,1	0,1
11	0,8	0,15	0,05	0,9	0	0,1
12	0,9	0,1	0,1	0,8	0	0,05
13	0,8	0,2	0,1	0,8	0	0,1
14	0,9	0,1	0,1	0,8	0	0,2
15	0,8	0,15	0,1	0,9	0	0,05

№	P11	P12	P21	P22	P31	P32
16	0,9	0,1	0,1	0,8	0	0,2
17	0,8	0,2	0,05	0,8	0	0,015
18	0,9	0,1	0,1	0,8	0	0,1
19	0,8	0,2	0,1	0,8	0	0,2
20	0,9	0,1	0,05	0,9	0	0,05
21	0,8	0,15	0,1	0,8	0	0,1
22	0,9	0,05	0,1	0,8	0	0,2
23	0,9	0,1	0,1	0,8	0	0,2
24	0,8	0,2	0,1	0,8	0,1	0,1
25	0,9	0,1	0,05	0,9	0	0,1
26	0,8	0,15	0,1	0,8	0	0,2
27	0,9	0,05	0,1	0,8	0	0,2
28	0,9	0,1	0,1	0,8	0	0,05
29	0,8	0,2	0,1	0,9	0	0,1
30	0,9	0,1	0,05	0,8	0	0,2

330

Пример 4.32. Устройство состоит из двух блоков(например, двигатель и ходовая часть). Пусть A означает безотказную работу первого блока, B –– безотказную работу второго блока. По истечении каждой единицы времени проверяется состояние этих ,блокови в случае неисправности производится их ремонт. Вероятность безотказной работы блоков в течение единицы времени равны соответственно0,9 и 0,8. Если неисправность блока обнаружена, то вероятность отремонтировать блок в течение единицы времени равна соответственно0,3 и 0,4. Найти предельные вероятности для состояний устройства: E1 = AB; E2 = AB;

E3 = AB; E4 = AB.

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

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

AB

AB

AB

AB

AB

0,9×0,8

0,9×0,2

0,1×0,8

0,2×0,1

0,9×0,4

0,9×0,6

0,1×0,4

0,1×0,6

AB

0,3×0,8

0,3×0,2

0,7×0,8

0,7×0,2

AB

0,3×0,4

0,3×0,6

0,7×0,4

0,7×0,6

AB

В итоге переходная матрица имеет вид

	æ0, 72		0,18	0,8	0,02	ö
	ç	0,36	0,54	0, 04	0,06	÷
|| P	||= ç					÷.
ij			0, 06	0,56	0,14 ÷
	ç0, 24
	ç	0,12	0,18	0, 28	0, 42	÷
	è					ø

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

P = 0, 72P + 0,36P + 0, 24P + 0,12P ,
1	1	2	3	4
P = 0,18P + 0,54P + 0,06P + 0,18P ,
2	1	2	3	4
P = 0,08P + 0,04P + 0,56P + 0, 28P ,
3	1	2	3	4
P = 0, 02P + 0,06P + 0,14P + 0, 42P .
4	1	2	3	4

331

	Это система линейных однородных уравнений, она имеет бесконечно
много		решений. Для получения единственного нужного нам решения
вместо			любого	из	уравнений	запишем	условие	нормир
P + P + P + P =1.				Решая	систему, например,	по формулам Крамера
1	2	3	4

получим P = P( AB) = 48 / 102 , P = P( AB) =19 / 102, P = P( AB) = 20 / 102,
1					2			3
P4 = P(
	AB			) =15 / 102.
Ответ. P(E1 ) = 48					/ 102 , P(E2 ) = 19 / 102,			P(E3 ) = 20 / 102,
				P(E4 ) = 15	/ 102.

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

станцию приезжает мастер для проверки исправности

блоков

станции.

Если блок

неисправен,

то

мастер

либо ремонтирует

блок

на

месте

(практически мгновенно), либо забирает блок для ремонта в мастерской, и

возвращает на место при следующем посещении станции.

Пусть Ai означает безотказную работуi-го блока.

Вероятность

безотказной работы i-го

блока

между проверками ранаPi.

Вероятность

того, что неисправность блока незначительная и устранима на месте равна

pi.

событий: E1 = A1 A2 ;

Найдите

предельные

значения

вероятностей

E2 = A1

=

Найдите вероятности

этих

состояний

на

A2 ; E3

A1 A2 ; E4 = A1 A2 .

третьем шаге, если в начале оба блока были исправны. (См. пример 4.32 и

исходные данные.)

У к а з а н и е .

При

вычислении

переходных

вероятностей

внимательно

учитывайте

все

возможности. Например,

переход E1 ® E1

состоится, если:

1) оба блока сохранят свою работоспособность(вероятность чего

равна P P );

1 2

2) первый блок выйдет из строя и будет отремонтирован на месте

(вероятность чего равна(1 – P ) p ), а второй блок сохранит свою

1 1

работоспособность (с вероятностью P2),

3) первый блок сохранит свою работоспособность(с вероятностью

P1), а второй блок выйдет из строя и будет отремонтирован на месте (вероятность чего равна (1 – P2 ) p2 ),

4) оба	блока		выйдут		из	строя		и будут		отремонтированы на месте
(вероятность чего равна (1 – P )(1 – P ) p p								2	).
				1		2	1
Поэтому вероятность перехода E1 ® E1 равна
p =P P + (1 – P ) p P +P (1 –							P ) p + (1 – P )(1 – P ) p p .
11	1	2	1	1	2	1	2		2	1	2	1	2

332

Исходные данные к задаче 4.32.

№	P1	P2	p1	p2	№	P1	P2	p1	p2	№	P1	P2	p1	p2
1	0,8	0,9	0,4	0,5	11	0,8	0,9	0,3	0,6	21	0,9	0,8	0,3	0,4
2	0,9	0,85	0,5	0,6	12	0,85	0,9	0,6	0,4	22	0,8	0,9	0,6	0,3
3	0,8	0,95	0,6	0,3	13	0,9	0,8	0,6	0,3	23	0,85	0,9	0,3	0,5
4	0,8	0,9	0,5	0,4	14	0,8	0,9	0,3	0,5	24	0,9	0,8	0,6	0,5
5	0,85	0,9	0,6	0,5	15	0,8	0,9	0,6	0,5	25	0,8	0,9	0,4	0,6
6	0,9	0,8	0,3	0,6	16	0,9	0,85	0,4	0,6	26	0,8	0,9	0,3	0,7
7	0,8	0,9	0,4	0,6	17	0,8	0,95	0,3	0,7	27	0,9	0,85	0,4	0,6
8	0,8	0,95	0,5	0,7	18	0,8	0,9	0,4	0,6	28	0,8	0,95	0,5	0,7
9	0,9	0,85	0,5	0,6	19	0,9	0,85	0,5	0,7	29	0,8	0,9	0,6	0,7
10	0,8	0,95	0,4	0,7	20	0,8	0,95	0,6	0,7	30	0,85	0,9	0,3	0,6

Пример 4.33. В зоне обслуживания бригады ремонтников находится
три прибора, работающих в автоматическом режиме. В конце каждого
месяца	ремонтники		проводят	профилактический			осмотр приборов, в и
случае обнаружения неисправных, забирают их для ремонта или замены на
новые. Отремонтированный (или новый) прибор возвращают на место при
очередном		профилактическом		осмотре, т.е. через			месяц.	Вероятность
выхода	из	строя	в течение месяца работающего прибора 1/3равна.
Требуется		найти	стационарное			распределение		вероятностей	числа
исправных приборов в начале каждого месяца.
Решение. Рассмотрим марковскую цепь, состояния которой будем
различать по числу работоспособных приборов. Пусть Ei –– означает, что
работоспособны i приборы. Всего имеется четыре возможных состояния:
E0, E1, E2, E3.
Составим переходную матрицу этой цепи. Если на данном шаге цепь
находится в состоянииE0, то на очередном шаге будут доставлены три
работоспособных прибора и цепь с вероятностью1 перейдет в состояние
E3. Поэтому p00 = p01			= p02 = 0 , а p03		= 1.
Если		на данном шаге цепи			имеется только		один работоспособный

прибор, то следующем шаге будет поставлено два новых прибора и

вероятность перехода E1 ® E3	равна вероятности того, что имеющийся в
наличии прибор сохранит	свою	работоспособность, .е. p13	= 2 / 3.
Вероятность же перехода E1 ® E2 равна		вероятности выхода	из строя

имеющегося прибора, т.е. p12 =1 / 3 , а p10 = p11 = 0 .

При наличии на данном шаге двух годных приборов в соответствии с формулой Бернулли, имеем переходные вероятности:

p	= P(E	2	® E )	=P (0)	=C0	(1 / 3)=0 (2 / 3)2	4 / 9;
23			3	2	2

333

p

= P(E

2

® E

)

P (1)

C1 (1= / 3)1 (2 / 3)1

4 / =9;

=

22

2

2

2

p

= P(E ® E )

P=(2)

(1 /=3)2 1 / 9;=

21

2

1

2

p20 = P(E2 ® E0 ) = 0.

Наконец, при трех годных приборах на данном шаге

p

= P(E ® E )

P (0)

C0 (1/= 3)0 (2 / 3)3

8 / 27;=

=

33

3

3

3

3

p

= P(E ® E

)

P (1)

C1

(1=/ 3)1(2 / 3)2

12 /=27;

=

32

3

2

3

3

p

= P(E ® E )

P (2)

C2

(1=/ 3)2 (2 / 3)1

6 / 27;=

=

31

3

1

3

3

p = P(E ® E ) = (1 / 3)3.

30

3

0

Запишем переходную матрицу:

æ

0

0

0

1

ö

ç

0

0

1 / 3

2 / 3

÷

ç

÷ .

ç 0

1 / 9

4 / 9

4 / 9 ÷

ç

6 / 27 12 / 27

8 / 27

÷

è1 / 27

ø

Этой переходной матрице соответствует система уравнений(4.5.2) для вычисления стационарных вероятностей:

u0 = u3 ×1 / 27;

u1 = u2 ×1 / 9 + u3 × 6 / 27;

u2 = u1 ×1 / 3 + u2 × 4 / 9 + u3 ×12 / 27;

u3 = u0 ×1 + u1 × 2 / 3 + u2 × 4 / 9 + u3 ×8 / 27.

Решая эту систему уравнений, с учетом условия нормировки u0 + u1 + u2 + u3 =1, получаем

u0 =1 / 64, u1	9=/ 64, u2 27=/ 64, u3 27=/ 64.
Ответ. P(E1 ) =1 / 64,	P(E2 ) = 9 / 64, P(E3 ) = 27 / 64, P(E4 ) = 27 / 64.

Задача 4.33. В некоторой фирме имеетсяn однотипных устройств (например, ксероксов, принтеров и т.п.). Устройства эксплуатируются с перегрузкой и поэтому часто выходят из строя. В конце каждой недели фирма подает заявку на поставку новых устройств для замены вышедших из строя. Время исполнения заявки –– одна неделя. Вероятность выхода из строя в течение недели для каждого работающего устройства равнаp. Найдите стационарное распределение числа пригодных к работе устройств в начале недели. (См. пример 4.33 и исходные данные.)

Исходные данные к задаче 4.33.

№	n	p	№	n	p	№	n	p	№	n	p	№	n	p	№	n	p
1	3	1/4	6	5	1/2	11	4	1/5	16	3	1/7	21	5	2/5	26	4	1/9
2	4	1/3	7	3	1/5	12	5	1/6	17	4	1/8	22	3	2/7	27	5	3/7
3	5	1/5	8	4	1/4	13	3	2/5	18	5	1/7	23	4	2/5	28	3	3/8
4	3	1/2	9	5	1/4	14	4	1/6	19	3	1/8	24	5	2/7	29	4	2/7

334