Sluchaynye_protsessy

6.Цепи Маркова

6.1.Определение цепи Маркова

В этом	разделе	будем изучать дискретную случайную последовательность ξi ,
i = 0,1,2,...	, т.е.	случайный процесс с дискретным			множеством	состояний
E = {E1, E2 ,..., Ek }		или	E = {E1, E2 ,..., Ek ,...}	и	дискретным	временем

T = {t1, t2 ,...,tm ,...}. Обычно при рассмотрении дискретной последовательности ξi говорят о некоторой системе, которая может находиться в одном из состояний E = {E1, E2 ,..., Ek ,...} и переходить из одного состояния в другое в дискретные моменты времени.

Определение 1. Дискретная случайная последовательность ξi , i = 0,1,2,..., называется цепью Маркова, если вероятность pis,,js+1 того, что в момент времени s + 1 система будет находиться в состоянии E j , зависит от того, в каком состоянии Ei система находилась в

предыдущий момент времени s и не зависит от того, в каких состояниях она находилась в более ранние моменты времени s −1, s − 2,...,0 :

pis,,js+1 = P(ξs+1 = E j / ξs = Ei ) = P(ξs +1 = E j / ξs = Ei ,ξs−1 = Ek ,...,ξ0 = El ) .

Вероятность

pis,,js+1 = P(ξs+1 = E j / ξs = Ei )

это условная вероятность того, что в момент времени s + 1 система будет находиться в со- стоянии E j при условии, что в предыдущий момент s она находилась в состоянии Ei . Эта

вероятность называется вероятностью перехода из состояния Ei в состояние E j за один шаг для моментов времени s, s + 1.

Цепь Маркова называется конечной, если множество E ее состояний конечное.

Цепь Маркова называется однородной, если условная вероятность pis,,js+1 не зависит от момента времени s . В этом случае эта вероятность обозначается как pi, j и называется ве- роятностью перехода из состояния Ei в состояние E j за один шаг. Мы будем рассматривать только однородные цепи Маркова.

Вероятности перехода pi, j образуют матрицу
P = ( pi, j ) , i, j = 1,2,... ,	(6.1)

которая называется матрицей вероятностей перехода однородной цепи Маркова. Элементы этой матрицы удовлетворяют следующим условиям:

0 ≤ pi, j ≤1,

∞

å pi, j =1, i =1,2,... .

j =1

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

41

Пример 6.1. Урновая модель. Имеем две урны. В первой из них находятся 1 белый и 2 черных шара, во второй – 1 белый и 5 черных шаров. Начиная с первой урны, наугад выни- маем шар за шаром, причем если был вынут белый шар, то следующий шар вынимаем из первой урны, а если черный – то из второй. Каждый вынутый шар тут же возвращаем в урну, из которой он был вынут. Нас может интересовать, например, вероятность вынуть белый (или черный) шар на n -м шаге.

Описанная в данном примере последовательность испытаний образует однородную цепь Маркова с двумя состояниями: E1 – вынутый шар белый и E2 – вынутый шар черный. Ве-

роятности перехода за один шаг имеют следующий смысл: p1,1 – вероятность вынуть белый шар после предыдущего белого, т.е. вероятность вынуть белый шар из первой урны; p1,2 – вероятность вынуть черный шар после предыдущего белого, т.е. вероятность вынуть черный шар из первой урны; p2,1 – вероятность вынуть белый шар после предыдущего черного, т.е. вероятность вынуть белый шар из второй урны; p2,2 – вероятность вынуть черный шар по-

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

					æ		1	2		ö
æ	p	p	ö		ç					÷
							3	3
ç	1,1	1,2	÷		ç					÷
P = ç p2,1		p2,2	÷	=	ç		1		5	÷.	(6.2)
è			ø		ç			6		÷
					è 6					ø

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

чайных толчков, которые возникают в моменты t0 ,t1,... . Частица может находиться в точ- ках a,a + 1,...,a + m,...,b . В точках a и b размещаются поглощающие стенки (экраны). Из каждой точки, кроме точек a и b, частица перемещается в правую точку с вероятностью p и в левую с вероятностью q = 1 − p . При достижении стенок (точек a и b) частичка прили-

пает к ним.

В данном примере рассмотрена система, которая может находиться в одном из состояний E1 = a , …, Ek = b. Если система находится в состояниях E1 = a , или Ek = b, то она с ве- роятностью единица остается в этих состояниях. Если же система находится в одном из про- межуточных между a и b состоянии a + m , то она с вероятностью p переходит в правое состояние a + m +1 и с вероятностью q = 1 − p – в левое состояние a + m −1. Матрица

вероятностей перехода этой цепи Маркова имеет вид
æ1 0 0 0 ... 0		ö
ç		÷
çq 0 p 0 ... 0		÷
P = ç	0 q 0 p ... 0	÷ .
ç		÷
çMMMMMMMMMMM		÷
ç	0 0 0 0 ...1	÷
è		ø

Состояния a и b системы называются поглощающими.

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

Этот пример имеет также иную интерпретацию. Некий игрок выигрывает и проигрывает определенную сумму с вероятностями p и q = 1 − p соответственно. Суммарный капитал

42

обоих игроков равен b. Игра продолжается до тех пор, пока капитал нашего игрока не уменьшится до нуля ( a = 0) или не возрастет до b, т.е. до того времени, пока один из игро- ков не разорится. Нас может интересовать вероятность разорения нашего игрока и распреде- ление вероятностей на протяжении игры. Такая интерпретация задачи случайных блужданий называется классической задачей о разорении.

6.2. Вероятности перехода за несколько шагов (уравнение ЧепменаКолмогорова)

Сейчас нас будут интересовать вероятности перехода системы, которая образует одно- родную цепь Маркова, из состояния Ei в состояние E j за n шагов. Обозначим эти вероят-

ности как pi, j (n) и назовем матрицу
Pn = (pi, j (n)), i, j = 1,2,... ,	(6.3)

матрицей вероятностей перехода за n шагов. Понятно, что P1 = P , где P – матрица веро- ятностей перехода за один шаг (6.1).

Рассмотрим переходы системы на протяжении последовательных n шагов. Пусть Pn – матрица вероятностей перехода за эти n шагов, Pm – матрица вероятностей перехода за первые m шагов, m < n , Pn−m – матрица вероятностей перехода за оставшиеся n − m ша- гов. Тогда выполняется следующее равенство:

Pn = Pm Pn−m , 0 < m < n .

(6.4)

Действительно, переход за n шагов возможен только через одно из состояний на m -м шаге.

Поэтому по формуле полной вероятности получим

		∞
pi, j (n) = å pi,ν (m) pν, j (n − m) .
		ν=1
Последняя формула есть формула умножения матриц (6.4).
Равенство (6.4) называется уравнением Чепмена–Колмогорова.
Из уравнения (6.4) при n = 2 получим, что
	P = P P = P2				= P2 .
При n = 3 находим:	2	1	1	1
P = P P = P P = P3						= P3 .
3	1	2	2	1	1
Вообще, при любом n имеем		P = Pn
					,	(6.5)
			n

т.е. матрица вероятностей перехода за n шагов равна n -й степени матрицы вероятностей перехода за один шаг.

6.3. Безусловные вероятности цепи Маркова

Для цепи Маркова важно знать абсолютные (безусловные) вероятности состояния систе- мы на любом n -м шаге

ai (n) = P(ξn = Ei ) , i =1,2,... .

Эти вероятности образуют матрицу-строку (вектор-строку) AnT безусловных вероятностей системы для момента времени n :

43

	AT	= (a (n),a		2	(n),...,)= (a (n)) , i =1,2,... .	(6.6)
Элементы вектора AT	n	1			i
	удовлетворяют при любом n очевидным условиям:
n			0 ≤ ai (n) ≤ 1,
			∞
			åai (n) =1.
			i =1

Для полного описания однородной цепи Маркова необходимо знать матрицу вероятно-

стей перехода P и вектор безусловных вероятностей		AT	для начального момента времени
		0
n = 0. Этих данных достаточно, чтобы найти вектор безусловных вероятностей AT				для лю-
бого n -го шага с помощью формулы			n
AT	= AT P .			(6.7)
n	0	n

Действительно, попадание системы в состояние E j на n -м шаге возможно при ее выходе в начальный момент времени из одного из своих состояний и переходе за n шагов в состояние E j . В этом случае применима формула полной вероятности

∞

a j (n) = åaν (0) pν, j (n), j =1,2,... ,

ν=1

которая в векторно-матричной форме имеет вид (6.7).

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

T	æ	1		2	ö
A	= ç		,		÷.
0	è 3			3	ø

По формуле (6.5) найдем матрицу вероятностей перехода за два шага

æ

1

2 öæ

1

2 ö æ

2

7 ö

ç

֍

÷

ç

÷

2

3

3

3

3

9

9

P2 = P

ç

֍

÷ ç

÷

=

ç

1

5

֍

1

5

÷

= ç

7

29

÷ .

ç

֍

÷

ç

÷

6

6

è

6 øè

6 ø è

36 36 ø

Наконец, по формуле (6.7) найдем вектор безусловных вероятностей на втором шаге:

æ

1

2

ö

æ

1

ç

÷

æ 11

43

ö

T

T

3

3

2 öç

÷

A

= A P

= ç

,

÷

1

5

= ç

,

÷ .

3

54

2

0 2

è

3 øç

÷ è 54

ø

ç

÷

6

è

6 ø

Таким образом, при втором испытании (начиная с нулевого) мы с вероятностью 1154 вынем белый шар, и с вероятностью 5443 – черный.

6.4. Классификация состояний цепи Маркова

Все состояния цепи Маркова принято разделять на существенные и несущественные.

44

Состояние Ei называется несущественным, если существуют такие j и n , что pi, j (n) > 0, и для всех m p j,i (m) = 0. Все остальные состояния называются существен- ными. Мы видим что, из несущественного состояния Ei . возможен переход в какое-то дру- гое состояния E j , но обратно в Ei вернуться невозможно.

В свою очередь существенные состояния распадаются на классы S (α) так называемых сообщающихся состояний. Существенные состояния Ei и E j называются сообщающимися,

если существуют такие n и m , что pi, j (n) > 0 и p j,i (m) > 0. Это значит, что из состоя- ния Ei за некоторое число шагов n можно попасть в состояние E j , и затем за некоторое

число шагов m вернуться обратно в Ei .

В соответствии с этой классификацией очевидно, что наша система попадает однажды в одно из состояний класса S (α) сообщающихся состояний и никогда не выходит за пределы этого класса. Если класс S (α) состоит только из одного состояния Ei , то это состояние на-

зывается поглощающим.

Цепь Маркова называется неприводимой, если она имеет только один класс сообщаю- щихся состояний.

Существенные состояния бывают периодическими и не периодическими. Периодом di состояния Ei называется наибольшим общий делитель таких чисел n , для кото- рых pi,i (n) > 0 . Вероятность pi,i (n) – это вероятность вернуться в состояние Ei за n ша- гов, выйдя из этого состояния. Состояние Ei которое имеет период di > 1, называется пе- риодическим. Состояние Ei называется не периодическим, если такого периода di > 1 не существует. Таким образом, периодическое состояние Ei – это такое состояние, в которое можно периодически возвращаться через di , 2di , 3di , … шагов. Можно доказать, что все состояния, которые относятся к одному и тому же классу S (α) , имеют один и тот же период, который обозначается, как d(α) и называется периодом класса S (α) . Класс S (α) , для кото-

рого существует период d(α) > 1, называется периодическим. Класс S (α) , для которого не существует d(α) >1, называется не периодическим.

Состояния делятся также на возвратные и не возвратные. Для объяснения этих понятий требуется рассмотреть вероятность Ki(,nj) того, что из состояния Ei система перейдет в со-

стояние E j ровно на n -м шаге. В частности, Ki(,ni ) есть вероятность того, что, начиная с Ei , система впервые вернется в это же состояние на n -м шаге. Обозначим

∞

Li, j = åKi(,nj) . n=1

Понятно, что Li, j есть вероятность того, что, начиная с Ei , система когда-нибудь пройдет через E j . Состояние Ei называется возвратным, если когда Li,i =1, и не возвратным, если Li,i <1. Мы видим, что состояние является возвратным, если система обязательно когда- нибудь вернется в это состояние. В не возвратное состояние система может как вернуться,

45

так и не вернуться. Доказано, что в пределах одного класса S (α) существенных состояний

или все L	<1, или все L		=1. Если все L	=1, то класс S (α) называется возвратным.
i,i		i,i	i,i
Если, наоборот, все L		<1, то класс S (α) называется не возвратным.
	i,i

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

необходимое для перехода из Ei в E j :

∞

Mi, j = ånKi(,nj) .

n=1

Вчастности, Mi,i есть среднее количество шагов до первого возврата в состояние Ei , когда

первоначально также было состояние Ei . Mi,i называется также средним временем возвра- та в состояние Ei . Доказано, что в пределах одного возвратного класса или все Mi, j беско- нечные, или все Mi, j конечные. Классы, для которых все Mi, j конечные, называются по- ложительными, а классы, в которых все Mi, j = ∞ , называются нулевыми.

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

Пример 1. В примере 1 раздела 6.3 с урновой моделью оба состояния образуют один класс существенных сообщающихся состояний.

Пример 2. В примере 2 раздела 6.3 со случайными блужданиями на прямой имеются три класса состояний: {a}, {a + 1,...,a + m}, {b}. Состояния {a}, {b} – существенные погло-

щающие. Состояния a + 1,...,a + m – не существенные. Система при длительном функцио-

нировании выходит из этих состояний и обратно не возвращается.

Пример 6.3. Пусть цепь Маркова имеет следующую матрицу вероятностей перехода:

æ	0	1	ö
P = ç			÷.
ç	1	0	÷
è			ø

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

P = P = ... = P		æ	0	1	ö
		= ç			÷ .
2 4	2n	ç	1	0	÷
		è			ø

Это значит, что класс состояний нашей цепи периодический с периодам d = 2 . Для конечных цепей Маркова справедлива следующая теорема.

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

6.5. Предельные вероятности состояний цепи Маркова

Часто нас интересует поведение системы, функционирующей достаточно длительное время. Это значит, что нас интересует поведение вероятностей pi, j (n) при n → ∞ . В неко-

торых случаях эти вероятности сходятся при n → ∞ к некоторым пределам, которые назы- ваются предельными вероятностями. Условия существования предельных вероятностей оп- ределяет следующая теорема.

46

Терема (Маркова). Если существует такое s > 0, что все pi, j (s) > 0, то существуют та-

кие числа p j , j =1,2,...,k , что независимо от индекса i выполняются следующие соотно- шения:

lim pi, j (n) = p j , j =1,2,...,k ,		(6.8)
n→∞
k
å p j	=1.

j =1

Физический смысл этой теоремы состоит в том, что вероятности pi, j (n) перехода из со- стояния Ei в состояние E j за n шагов при n → ∞ не зависят от состояния Ei , из которого

был начат переход. Система как бы забывает о своем состоянии в далеком прошлом. Пример. Применима ли теорема о предельных вероятностях к цепи Маркова с матрицей

вероятностей перехода	0	1
æ			ö
P = ç			÷?
ç	1	0	÷
è			ø

Поскольку для такой цепи		1	0				0	1
P	æ			ö		æ			ö
	= ç			÷ , P		= ç			÷, m = 1,2,... ,
2m	ç	0	1	÷	2m+1	ç	1	0	÷
	è			ø		è			ø

то для каждого s матрица Ps имеет нулевые элементы. Условия теоремы не выполняются, так что мы не можем утверждать, что предельные вероятности существуют.

Объединим предельные вероятности p j , j =1,2,...,k , в вектор-строку предельных веро-

ятностей
( p )T = ( p , p ,..., p ) .			(6.9)
1	2	k
Тогда выражение (6.8) можно записать в следующей векторно-матричной форме:
lim P = P		,	(6.10)
n→∞	n

где P – (k × k)-матрица предельных вероятностей. Все строки матрицы P одинаковы и

совпадают с вектором-строкой ( p )T (6.9).

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

PT p = p ,		(6.11)
k
å p j	=1.	(6.12)

j =1

Действительно, запишем для цепи Маркова уравнение Чэпмена–Колмогорова (6.4) в виде

Pn+1 = Pn P

и найдем предел обеих частей при n → ∞ . Поскольку при этом Pn+1 = Π , Pn = Π , то по-

лучаем уравнение

P = P P ,

из которого следует (6.11).

47

Рассмотрим также безусловные предельные вероятности
a j	= lim a j (n) ,
	n→∞

образующие вектор-строку безусловных предельных вероятностей (A )T = (a ,a ,...,a ) ,
так что		1 2	k
(A )T = lim A .			(6.13)
n→∞	n	P (6.9), то он является и
Теорема. Если существует вектор предельных вероятностей
вектором безусловных предельных вероятностей:
A = P .			(6.14)

Чтобы получить равенство (6.14), запишем соотношение (6.7), взяв предел от обеих его

частей:				lim AT	= AT lim P .
			n→∞ n		0 n→∞	n
Учитывая обозначения пределов (6.10), (6.13), получим
				(A )T = AT Π .
					0
Поскольку a (0) + a	2	(0) + ... + a	k	(0) = 1	и матрица P состоит из одинаковых строк, то
1

легко понять, что A0T Π = (P )T , и равенство (6.14) доказано.

Пример 6.4. Найти предельные вероятности для цепи Маркова из примера 6.1 раздела 6.1 на урновую модель.

Поскольку матрица вероятностей перехода этой цепи (6.2) имеет вид

					æ		1	2		ö
æ	p	p	ö		ç					÷
							3	3
ç	1,1	1,2	÷		ç					÷
P = ç p2,1		p2,2	÷	=	ç		1	5		÷	,
è			ø		ç					÷
								6
					è 6					ø

т.е. не содержит нулевых элементов, то эта цепь удовлетворяет теореме 6.? и предельные ве- роятности существуют.

Система уравнений (6.11), (6.12) для предельных условных вероятностей в данном приме-

ре имеет вид

13 p1 + 16 p2 = p1 , 23 p1 + 56 p2 = p2 ,

p1 + p2 =1.

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

23 p1 - 16 p2 = 0,

p1 + p2 =1.

Отсюда получаем p1 = 0,2, p2 = 0,8. Такими же будут и безусловные предельные вероят-

ности a1 = 0,2 , a2 = 0,8 . Это значит, что после продолжительного числа экспериментов

48

мы будем на каждом шаге вынимать белый шар с вероятностью a1 = 0,2 и черный шар – с

вероятностью a2 = 0,8 .

Характеристическое уравнение для данной цепи Маркова:

æ

1

- l

1

ö

ç

÷

T

3

6

| P

- lI |=

ç

2

5

÷

= 0 ,

ç

÷

ç

- l÷

3

6

è

ø

т.е.

l2 - 76 l + 16 = 0 ,

l = 7 / 6 ±	49/36 - 4/ 6	,
1,2	2

λ1 = 1, λ2 = 0.1667 .

49

7.СЛУЧАЙНЫЕ ПРОЦЕССЫ С НЕЗАВИСИМЫМИ ПРИРАЩЕНИЯМИ

7.1.Процессы с некоррелированными приращениями

Будем рассматривать случайный процесс	x(t) с нулевым математическим ожиданием,
E(x(t)) = 0, и назовем величину x(t) - x(s)	для t ³ s приращениями процесса на отрезке
[ s,t ]. Будем считать, что для всех s и t дисперсия приращениями конечная:
E(ξ(t) − ξ(s))2 < ∞.
Определение 7.1. Случайный процесс x(t)	с нулевым математическим ожиданием и ко-

нечной дисперсией приращений x(t) - x(s) для всех t , s называется процессом с некорре-

лированными приращениями, если для любых t1 < t2 ≤ t3 < t4
E(ξ(t4 ) − ξ(t3 ))(ξ(t2 ) − ξ(t1))) = 0 .	(7.1)

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

Если η – произвольная случайная величина, то процессы x(t) + h и x(t) имеют одни и

те же приращения. Это означает, что свойство некоррелированности (7.1) сохраняется, если к

исходному процессу с некоррелированными приращениями добавить некоторую случайную величину. Мы можем, например, рассматривать процесс ξ(t) − ξ(t0 ) , принимающий значе-

ние 0 в любой фиксированный момент времени t0 и имеющий некоррелированные прира-

щения.

При анализе процессов с некоррелированными приращениями большое значение имеет

следующая функция:
ì	E (( x(t) - x(t0 )) 2 ), t ³ t0	,	(7.2)
F (t) = í	- E (( x(t ) - x(t0 )) 2 ), t < t0 ,
î

где t0 – заранее выбранное число. В выражении (7.2) M ((ξ (t)-ξ(t0 )2 ) есть дисперсия при-

ращения процесса на отрезке [t0 ,t]. Функция F(t) (7.2) имеет следующие свойства.
1. Для всех u £ t
D(ξ(t) − ξ(u)) = E((ξ(t) − ξ(u))2 = F(t) − F(u) .		(7.3)
Эта свойство показывает, как по известной функции F(t)	найти дисперсию приращения
процесса на отрезке [u,t].
Для доказательства формулы (7.3) выберем t0 из условия	u < t0 < t . Получим
E((ξ(t) − ξ(u))2 ) = E(((ξ(t) − ξ(t0 )) − (ξ(u) − ξ(t0 )))2 ) =
= E((ξ(t) − ξ(t0 ))2 ) − 2E((ξ(t) − ξ(t0 ))(ξ(u) − ξ(t0 ))) + E((ξ(u) − ξ(t0 ))2 ) .

Второе слагаемое в правой части этого равенства равно нулю в силу некоррелированности приращений процесса x(t) , первое слагаемое есть F(t), а третье слагаемое равно ( - F(t) ).

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

2. Функция F(t) (7.2) – неубывающая по t . Это значит, что если t ³ u , то и

F (t ) ³ F (u ) .

50