Тема 16 Марковски вериги

Марковските процеси са обобщение на процесите с независими нараствания. Нека е зададен процесът x_t, t і 0.

Определение 16.1 Ще казваме, че процесът е Марковски, ако бъдещето и миналото са независими при фиксирано настояще.

Същият смисъл имат думите: Бъдещето зависи само (се определя изцяло) от последния наблюдаван момент. Разгледания в миналата лекция Поасонов процес е очевиден пример за Марковски процес. Състоянието на процеса в даден бъдещ момент е проста сума на състоянието му в момента и съответната случайна величина определяща нарастването му. Така е очевидно и за всички процеси с независими нараствания --- те са марковски.

За разлика от е.п.н.н., Марковските процеси могат да притежават и стойности, които не са числови. Наистина, стойностите на е.п.н.н. трябва да принадлежат на адитивна група --- това изисква определението им.

Особеността при дефиниция на марковски процеси идва от това, че трябва да се разглежда и проверява условна независимост. Когато вероятността на дадено фиксирано състояние е нулева (както това е при процеси с непрекъснато пространство на състоянията), такава проверка е нетривиална --- тя изисква наличието на многомерна вероятностна плътност.

16.1 Марковски вериги

Тук ще се спрем на процеси с дискретно време и крайно дискретно пространство на състоянията. Такива процеси наричаме марковски вериги. Подробно с тях може да се запознаете в книгите [(Кемени и Снелл,1970)] и [(Димитров,1980)]. Ще предположим, че множеството от състояния на веригата са числата 1,2,...,k.

Ако условно означим събитията в ''миналото'', ''настоящето'' и ''бъдещето'' със буквите A, B, C, то Марковското свойство означава просто P (AЗ C|B)=P (A|B)P (C|B). Сега дефиницията за марковост може да се препише по - точно:

Определение 16.2 Ще казваме, че процесът е крайна Марковска верига, ако за всички възможни набори {i₀,i₁,... ,i_n}, (1Ј i_kЈ k) и всяко nі 1 е изпълнено:

P (x₀=i₀,x₁=i₁,... ,x_n=i_n,x_n+1=i_n+1|x_k=i_k)=

P (x₀=i₀,x₁=i₁,... ,x_k-1=i_k-1|x_k=i_k)*

P (x_k+1=i_k+1,... ,x_n=i_n|x_k=i_k).

Марковското свойство дава възможност съвместните разпределения на множеството случайни величини да бъдат пресмятани просто, както показва следната теорема.

Теорема 16.1 Разпределенията на крайна Марковска верига се определят от началното разпределение {p_i=P(x₀=i),i=1,2,... ,k} и матриците на преходни вероятности (във всеки един момент {n=0,1,2,...} на времето) P_i,j(n)= P (x_n+1=j|x_n=i), (i,j=1,2,... k,) по формулата:

(x₀=i₀,x₁=i₁,... ,x_n=i_n) = p

i₀

i₀,i₁

(0)... P

i_n-1,i_n

(n-1). (16.1)

Доказателство: Доказателството се прави по индукция и следва лесно от определението и формулата за умножение на вероятности. Да отбележим, че понеже P (A|B)=P (AЗ B|B), Марковското свойство може да се запише и така: P (AЗ BЗ C|B)=P (AЗ B|B)P (CЗ B|B).
Нека да допуснем, че сме доказали формулата (16.1) за някое n (за n=0,1 тя е очевидна) и всички възможни набори {i₀,i₁,... ,i_n}. От определението 16.2 следва формулата:

P (AЗ BЗ C|B)= P (x₀=i₀,x₁=i₁,... ,x_n=i_n,x_n+1=i_n+1|x_n=i_n)=

P (x₀=i₀,x₁=i₁,... ,x_n=i_n|x_n=i_n) P (x_n=i_n,x_n+1=i_n+1|x_n=i_n)=

(x₀=i₀,x₁=i₁,... ,x_n=i_n|x_n=i_n)P

i_n,i_n+1

(n) =P (AЗ B|B)P (C|B)

Като умножим тази формула с вероятността P (B)=P (x_n=i_n) получаваме търсената рекурсия.

Определение 16.3 Ще казваме, че Марковската верига е еднородна, ако преходните вероятности P_i,j(n) не зависят от n.

Да означим тази единствена матрица на преходните вероятности с P и вектора от началните вероятности с p₀. Матрицата P се нарича стохастична, защото сумата на елементите й по редове е 1. Една от основните задачи на теорията на Марковските вериги е изследването на граничното поведение на Pⁿ=P*P*··· *P. Да означим елементите на тази матрица с p_i,jⁿ, n=2,3,... . Очевидни са следните уравнения на А.Марков:

p_i,jⁿ⁺¹ =

l=1

p_i,l p_l,jⁿ (16.2)

Сега лесно можем да изразим и вектора от вероятности в момента n: p_n={P (x_n=i)}, (i=1,2,... ,k):

p'_n = p₀'Pⁿ .

16.2 Гранично и стационарно разпределения

Следната теорема се нарича ергодична теорема на А.А.Марков

Теорема 16.2 Ако всички елементи на стохастичната матрица са строго положителни, то съществуват числа p_j, 0 Ј p_j Ј 1, S_j p_j= 1, такива че lim_n

_Ґ p_i,jⁿ =p_j независимо от индекса i.

Доказателство: Снабдяваме линейното пространство R^k с норма: ||x||=S_i=1^k |x_i|. В тази норма то е пълно --- всяка сходяща по Коши редица има граница. Да разгледаме подмножеството K на R^k определено от условията: S_i=1^k x_i = 1, x_i і 0, i=1,2,... ,k.То е компактно и трансформацията P го изобразява в себе си. Ще покажем, че P е свиваща трансформация и, следователно, има единствена неподвижна точка, към която се стремят неговите итерации.

А. Върху елементите на K разстоянието, породено от указаната норма, се пресмята по следния начин:

||x-y||= 2

iО J

(x_i - y_i). (16.3)

Тук с J сме означили множеството от индекси на положителни елементи под знака на сумата. Да отбележим, че това множество е винаги строго по - малко от цялото множество от индекси. Ако не беше така, би било невъзможно S_i=1^k (x_i-y_i) = 0.

Б. Нека означим с a = min_i,jp_i,j. Тогава е изпълнено условието за свиване:

||x'P-y'P||Ј (1-a)||x -y||. (16.4)

Това следва от следната верига неравенства:

||x'P-y'P||=

jО J

p_i,j(x_i-y_i)

(

jО J

p_i,j) (x_i-y_i)

iО I

(

jО J

p_i,j) (x_i-y_i)

iО I

(1-a) (x_i-y_i)

= (1-a)||x -y||.

В. Нека означим със z неподвижната точка на P - точката, удовлетворяваща уравнението: z'P=z'. Тъй като диаметърът на множеството K е 2 имаме:

||z' - x'Pⁿ||Ј ||(z-x)'Pⁿ||Ј 2 (1-a)ⁿ.

Г. Тогава границата P^Ґ съществува, тя е линеен оператор и е проектор върху тази точка и, следователно, може да се запише във формата: P^Ґ= e z'.

Коментар От доказателството е ясно, че граничното състояние на такава верига е единствено и се достига с експоненциална скорост. Ясно е също, че теоремата може да се приложи и за вериги, при които само някаква степен на преходната матрица притежава положителни членове.

Определение 16.4 Ще наричаме разпределението
p={p_i, i=1,2,... ,k} върху пространството на състояния на еднородна крайна Марковска верига стационарно, ако удовлетворява следното съотношение:

p' P = p'. (16.5)

Теорема 16.3 Граничното разпределение (когато съществува) е стационарно.

Доказателство: Удобно е да се използуват за целта т.н. уравнения на Колмогоров:

Pⁿ⁺¹=Pⁿ P. (16.6)

Те се извеждат точно както и уравненията на Марков (16.2). Не е трудно да се провери за граничното разпределение, че то трябва да ги удовлетворява, т.е. да бъде стационарно. Да означим вектора e={1,1,...,1}' и с p - този от граничните вероятности. Тогава от съществуването на гранично разпределение получаваме Pⁿ

e p', а преминаването в граница на уравненията (16.6) води до e p'= e p'P. Така се получава, че граничното разпределение p е ляв (нетривиален) собствен вектор на P. Това означава, че ако в даден момент веригата има такова разпределение, то ще се запази неизменно и за в бъдеще.

16.3 Класификация на състоянията

Ще започнем тази тема с два тривиални примера.

Пример 16.1 Да разгледаме следните матрици на преходни вероятности:

P₁=

ж
и

q	p
0	1

ц
ш

, P₂=

ж
з
з
и

0	1	0
0	0	1
1	0	0

ц
ч
ч
ш

При матрицата P₁ системата остава завинаги в състоянието 2, когато го достигне. Такова състояние се нарича поглъщащо. Понякога цял клас състояния може да бъде поглъщащ -- веднъж достигнат вече не може да бъде напуснат. Поглъщащото състояние (или клас) може да се достига в случаен момент на времето -- за тази конкретна верига разпределението му е геометрично.

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

При матрицата P₂ периодично се сменят три състояния в реда:

1,2,3,1,2,3,.. или

2,3,1,2,3,1,.. или

3,1,2,3,1,2,..

и всъщност цялата вероятностна мярка е съсредоточена върху три траектории, започващи от различни начални състояния в зависимост от вектора на началните вероятности p₀. Бъдещото поведение на такава верига става напълно предсказуемо --- то детерминирано се определя от нейното настояще. Състояние от този тип се нарича периодично. Естествено е, че състоянията, през които преминава траекторията при своето периодично движение, образуват периодичен клас състояния. Такъв клас е винаги поглъщащ, но може, разбира се, да бъде достигнат в случаен момент на времето. Състояние, което не принадлежи на никой периодичен клас се нарича апериодично.

Изобщо казано състоянията на веригата могат да бъдат частично наредени: казваме че състоянието i

j, ако p_i,jⁿ > 0 за някое n. Ясно е, че еквивалентните състояния в тази наредба образуват клас. Когато от класа не може да се излезе, класът е максимален в указаната частична наредба. Една верига може да има няколко такива класа. Такъв клас ще наричаме ергодичен, а състоянията в него ергодични.

Класификацията на състояния представлява особен интерес в теорията на Марковските вериги поради следните теореми:

Теорема 16.4 Възвратната апериодична Марковска верига е ергодична.

Всъщност не е трудно да се съобрази, че теоремата на Марков следва от тази теорема --- периодичността и невъзвратността винаги са свързани с наличието на нулеви вероятности. Така неговата матрица с положителни елементи е матрица на ергодична верига.

Теорема 16.5 Граничното разпределение на ергодична Марковска верига е единствено и не зависи от началното състояние.

16.4 Примери и задачи

Пример 16.2 ''Канал с шум'' или Марковска верига с две симетрични състояния.

Системата сменя състоянието си с вероятност p < 1/2 или остава в същото състояние с вероятност q=1-p. Тогава преходната матрица P е симетрична. Нейната n-та степен Pⁿ е също симетрична и двете съответно имат вида:

ж
и

q	p
p	q

ц
ш

, Pⁿ=

ж
и

1 - p_n	p_n
p_n	1 - p_n

ц
ш

Уравненията на Марков в този случай се записват просто:

	1-p_n	=	(1-p)(1-p_n-1)+p p_n-1	(16.7)
	p_n	=	p(1-p_n-1)+(1-p) p_n-1.

Чрез изваждане на второто уравнение от първото получаваме:

1-2p_n = (1-2p) (1- 2p_n-1)

1-2p_n = (1-2p)ⁿ

Следователно получаваме, че p_n

1/2. Така в този частен случай граничното разпределение е равномерното.

Пример 16.3 Неергодична верига.

Да разгледаме веригата със симетрична преходна матрица:

ж
з
з
и

1	0	0
0	q	p
0	p	q

ц
ч
ч
ш

Да означим с p вектора от начални вероятности. Покажете, че граничното разпределение (зависещо от началното) е

p₁, (p₂+p₃)/2, (p₂+p₃)/2.

Д.Въндев -Теория на вероятностите - January 9, 2002