Diszkrét és folytonos paraméter Markov láncok. Csiszár Vill

Diszkrét és folytonos paraméter¶ Markov láncok Csiszár Vill®

Tartalomjegyzék 1. Bevezetés

1

I. Diszkrét paraméter¶ Markov láncok

2

2. Visszatér®ség

2

2.1.

Markov-tulajdonság . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

2.2.

Állapotok osztályozása . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

2.3.

Visszatér®ség

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.4.

Az átmenetvalószín¶ségek konvergenciája . . . . . . . . . . . . . . . . .

12

2.5.

Stacionárius eloszlás

15

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

3. Pozitív rekurrens Markov láncok 3.1.

Nagy számok törvénye

3.2.

Centrális határeloszlás-tétel

3.3.

Tabu állapotok

3.4.

19

. . . . . . . . . . . . . . . . . . . . . . . . . . .

19

. . . . . . . . . . . . . . . . . . . . . . . .

22

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

A CHT-ben szerepl® szórásnégyzet kiszámítása . . . . . . . . . . . . . .

26

4. Reguláris mérték 4.1.

Reguláris függvény

4.2.

Reguláris mérték

4.3.

28 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

Megfordított láncok . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

5. Elnyel®dési valószín¶ségek

36

6. Véges állapotter¶ Markov láncok

38

6.1.

Irreducibilis, aperiodikus mátrixok . . . . . . . . . . . . . . . . . . . . .

40

6.2.

Irreducibilis, periodikus mátrixok

. . . . . . . . . . . . . . . . . . . . .

41

6.3.

Konvergencia és sebessége

. . . . . . . . . . . . . . . . . . . . . . . . .

43

6.4.

Perron-Frobenius tétel

. . . . . . . . . . . . . . . . . . . . . . . . . . .

44

6.5.

A konvergenciasebesség becslése megállási id®kkel

. . . . . . . . . . . .

7. MCMC módszerek

46

48

7.1.

A Hastings-Metropolis algoritmus . . . . . . . . . . . . . . . . . . . . .

48

7.2.

Gibbs mintavételez®

51

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

i

II. Folytonos paraméter

52

8. Innitezimális generátor

52

9. Kolmogorov-féle dierenciálegyenletek

57

10.Születési-halálozási folyamatok

59

10.1. A Poisson folyamat . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59

10.2. Születési folyamatok

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

10.3. Születési-halálozási folyamatok . . . . . . . . . . . . . . . . . . . . . . .

63

11.Visszatér®ség

64

11.1. Az állapotok osztályozása

. . . . . . . . . . . . . . . . . . . . . . . . .

64

11.2. A Markov lánc trajektóriái . . . . . . . . . . . . . . . . . . . . . . . . .

64

11.3. Visszatér®ség

66

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11.4. Stacionárius eloszlás

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

12.A Kolmogorov-egyenletek megoldhatóságáról

ii

67

69

1. BEVEZETÉS

1

1. Bevezetés Tekintsünk egy megszámlálható sok csúcspontú, irányított gráfot úgy, hogy minden élre egy nemnegatív szám van írva, és minden csúcs kimen® éleire írt számok összege

1

(hurokél is megengedett). Ezen a gráfon bolyongunk az élekre írt valószín¶ségek szerint. Ha egységnyi id®közönként lépünk akkor diszkrét paraméter¶ Markov láncot kapunk. Ha pedig egy adott csúcsból exponenciális eloszlású id® elteltével lépünk tovább (ahol az eloszlás paramétere a csúcsra jellemz®), akkor folytonos paraméter¶ Markov láncunk lesz. Mindkét esetben igaz, hogy a lánc jöv®beli fejl®dése csak a pillanatnyi állapottól függ, a múlttól nem. Ilyen jelleg¶ folyamattal számos helyen találkozhatunk, például tömegkiszolgálási rendszerekben, populációk fejl®désének vizsgálatánál, diúziós modelleknél. A folyamat általánosítása, ha a jöv®beli fejl®dés csak a mostani és az el®z® néhány állapottól függ. Ez az általánosítás még szélesebb kör¶ alkalmazásokat tesz lehet®vé, pl. az írott nyelvek is tanulmányozhatók így. A folyamattal kapcsolatban a következ® kérdések merülhetnek fel : Honnan hová lehet eljutni ? Mekkora eséllyel érünk vissza a kiindulási helyünkre ? Mekkora az esélye, hogy végtelen sokszor visszatérünk ? Átlagosan mennyi id® alatt érünk vissza a kiindulási helyre, vagy általánosabban egy másik csúcsba ? Vannak-e elnyel® csúcsok ? Ha igen, mekkora eséllyel nyel®dünk el bennük ? Van-e stacionárius kezdeti eloszlás ? Hány ? Tart-e a bolyongás egy stacionárius eloszláshoz ? Milyen gyorsan ? Érvényes-e valamilyen NSzT ? Érvényes-e valamilyen CHT ? Ebben a jegyzetben el®ször a diszkrét, majd a folytonos paraméter¶ Markov láncokkal foglalkozva próbálunk meg válaszolni a fenti kérdésekre. A tárgyhoz kapcsolódó további ajánlott irodalom : 1. W. Feller : Bevezetés a valószín¶ségszámításba és alkalmazásaiba (I. kötet), 15., 16., 17. fejezet. 2. S. Karlin, H. M. Taylor : Sztochasztikus folyamatok. 2., 3., 4. fejezet. 3. K. L. Chung : Markov Processes with Stationary Transition Probabilities. 4. Barczy Mátyás, Pap Gyula : Sztochasztikus folyamatok példatár és elméleti kiegészítések II. rész (diszkrét idej¶ Markov-láncok). 5. Pap Gyula : Sztochasztikus folyamatok.

2

I. rész

Diszkrét paraméter¶ Markov láncok 2. Visszatér®ség Ebben a fejezetben arra keressük a választ, hogy a lánc milyen gyakran tér vissza a kezdeti állapotba, illetve milyen s¶r¶n látogatja meg a különböz® állapotokat. Megkérdezhetjük, hogy átlagosan mennyi ideig tart, míg egy adott állapotból a lánc el®ször eljut egy másik adott állapotba (ha egyáltalán eljut). Rokon kérdés, hogy egy távoli id®pontban mekkora eséllyel lesz a lánc az egyes állapotokban.

2.1. Markov-tulajdonság Deniáljuk el®ször pontosan a Markov láncot !

2.1. Deníció.

{Xn }n∈N folyamat, ahol Xn : Ω → I valószín¶ségi változók az (Ω, F, P ) valószín¶ségi mez®n, I pedig megszámlálható halmaz. A folyamatot Legyen adott az

diszkrét paraméter¶ homogén Markov láncnak nevezzük, ha A folyamat Markov-tulajdonságú, azaz

B⊆I

és minden

m≥n

Fn = σ(X0 , X1 , . . . , Xn ) jelöléssel minden

esetén

P (Xm ∈ B | Fn ) = P (Xm ∈ B | Xn ). (Ezt a tulajdonságot általános mérhet® állapottérre is deniálhatjuk.) A Markov folyamat stacionárius (vagy homogén) átmenetvalószín¶ség¶, azaz minden

i, j ∈ I

esetén minden olyan

n-re,

melyre

P (Xn = i) > 0,

P (Xn+1 = j | Xn = i) = pij , n-t®l

függetlenül.

2. VISSZATÉRSÉG

I

3

az állapottér, elemeit a továbbiakban

i, j, k, . . . jelöli. Esetünkben az Fn σ -algebra

atomos, ezért a Markov-tulajdonság azzal ekvivalens, hogy

P (Xm ∈ B | Xn1 = i1 , . . . , Xnk = ik ) = P (Xm ∈ B | Xnk = ik ), ha

n1 < · · · < nk ≤ m.

Feladat: A Markov-tulajdonság ekvivalens megfogalmazásai.

Mutassuk

meg, hogy a Markov-tulajdonság ekvivalens a következ®kkel :

P (Xn+1 ∈ B | Fn ) = P (Xn+1 ∈ B | Xn ).

1.

2. Minden

A ∈ Fn−1

és

B ∈ F n+1 = σ{Xn+1 , Xn+2 , . . .}

esetén

P (A ∩ B | Xn ) = P (A | Xn )P (B | Xn ). 3. Minden A

F n+1 -mérhet® Y -ra E(Y | Fn ) = E(Y | Xn ),

P = (pij )

mátrixot átmenetmátrixnak nevezzük (nem keverend® össze a va-

lószín¶séggel), elemei az átmenetvalószín¶ségek. Az hívjuk, és

ha a baloldal értelmes.

p = (pi )-vel

X0

eloszlását kezdeti eloszlásnak

jelöljük. Ez a két objektum már meghatározza a folyamatot,

hiszen a véges dimenziós eloszlásokat a Markov-tulajdonságot felhasználva kapjuk :

P (X0 = i0 , X1 = i1 , . . . , Xn = in ) = = P (X0 = i0 )P (X1 = i1 |X0 = i0 ) · · · P (Xn = in |X0 = i0 , . . . , Xn−1 = in−1 ) = = pi0 pi0 i1 · · · pin−1 in .

2.2. Deníció.

A

P

mátrix

1. sztochasztikus, ha

pij ≥ 0

és minden sor összege

1,

2. duplán sztochasztikus, ha sztochasztikus, és minden oszlop összege 3. szubsztochasztikus, ha

2.3. Tétel.

Tetsz®leges

mátrixhoz, létezik mátrixa

P.

I

I -n

pij ≥ 0 adott

p

és minden sor összege legfeljebb

eloszláshoz és

|I| × |I|

méret¶

1,

1. P

sztochasztikus

állapotter¶ Markov lánc, melynek kezdeti eloszlása

p,

átmenet-

2. VISSZATÉRSÉG

Bizonyítás.

4

(vázlat) A bizonyítás a Kolmogorov alaptételen múlik. Ez a következ®t

mondja ki : Legyen

X

teljes szeparábilis metrikus tér,

n

és minden

a Borel halmazok

σ -algebrája, Θ pedig

(X , B ) a tér n-edik hatványát. Tegyük fel, hogy minden θ1 , . . . , θn ∈ Θ-ra adott B (n) -en a Pθ1 ,...,θn valószín¶ségi mérték, melyek

tetsz®leges halmaz. Jelölje

n-re

B

(n)

eleget tesznek az alábbi konzisztenciafeltételeknek :

Pθ1 ,...,θn ,θn+1 ,...,θn+m (A(n) × X m ) = Pθ1 ,...,θn (A(n) ) minden A(n) ∈ B (n) -re, (n) (ii) Minden π ∈ Sn permutációra Pθ1 ,...,θn (A ) = Pθπ(1) ,...,θπ(n) (π(A(n) )). Ekkor létezik valószín¶ségi mez® és azon Xθ valószín¶ségi változók, melyek (i)

véges di-

menziós eloszlásai az adottak. Legyen

X = I , Θ = N,

és

P0,1,...,n (i0 , i1 , . . . , in ) = pi0 pi0 i1 · · · pin−1 in , belátható, hogy ezek eleget tesznek a konzisztenciafeltételeknek. Ekkor a Kolmogorov alaptétel által garantált

Xn

folyamat valóban Markov lánc a kívánt kezdeti eloszlással

és átmenetvalószín¶ségekkel.

2.4. Állítás.

n¶ségek (feltesszük,

(n)

pij = P (Xn+m = j|Xm = i) az n-edrend¶ átmenetvalószíhogy P (Xm = i) > 0), ezekre teljesül a Chapman-Kolmogorov

Legyenek

egyenl®ség :

(n+m)

pij

=

X

(n) (m)

pik pkj .

k Ez azt jelenti, hogy a a

(n)

pij

mennyiségek éppen a

Pn

mátrix megfelel® elemei.

Bizonyítás. P (Xn+m = j | X0 = i) =

X

P (Xn+m = j, Xn = k | X0 = i) =

k

X

P (Xn+m = j | Xn = k, X0 = i)P (Xn = k | X0 = i) =

k

X

(m) (n)

pkj pik .

k

2.2. Állapotok osztályozása

2.5. Deníció. olyan

n ≥

1. Azt mondjuk, hogy az

(n) 0, hogy pij

>

i

állapotból elérhet®

(0) 0. Ez reexív (pii

= 1)

j , (i → j),

ha van

és tranzitív (Chapman-

2. VISSZATÉRSÉG

5

Kolmogorov) reláció. 2. Azt mondjuk, hogy

i

j

és

közlekednek, ha

i→j

és

j → i.

Ez ekvivalenciarelá-

ció, tehát osztályokra bontja az állapotteret (csak az átmenetmátrixtól függ). A Markov lánc irreducibilis, ha egyetlen osztályból áll. 3. Az

i

állapot lényeges, ha

i→j

esetén

j→i

is teljesül.

Az állapotokra értelmezett valamely tulajdonság osztálytulajdonság, ha egy osztálynak vagy minden eleme ilyen tulajdonságú, vagy egy sem. Triviálisan látszik, hogy a lényegesség osztálytulajdonság, azaz beszélhetünk lényeges és lényegtelen osztályokról.

i lényeges, j lényegtelen, és i → j . Létezik k , hogy j → k , de i → j → k , tehát i lényegessége miatt k → i → j , ami ellentmondás.)

(Biz. : Tegyük fel, hogy

k 6→ j .

Másrészt

A lényeges osztályokból nem lehet kijutni (mert akkor vissza is tudnánk jönni, azaz osztályon belül maradnánk), a lényegtelenekb®l viszont igen : ha elhagytuk ®ket, akkor többé már nem térhetünk vissza. A lényegtelen osztályok között parciális rendezés van :

C >> D,

ha

i ∈ C, j ∈ D

2.6. Deníció.

esetén

i→j

(tranzitív, reexív, antiszimmetrikus).

(n)

{n > 0 : pii > 0} halmaz legnagyobb közös osztója az i periódusa, jelölése d(i). Ha a halmaz üres, akkor a periódust nem értelmezzük. Ha d(i) = 1, akkor Az

az állapot aperiodikus.

2.7. Állítás. Bizonyítás.

Egy osztály minden állapotának ugyanannyi a periódusa.

(n)

i, j ∈ C azonos osztálybeliek. Ekkor létezik n, m, hogy pij > (n+2s+m) (m) (s) (n+s+m) > 0, pii > 0. Emiatt > 0, pji > 0. Ha valamely s-re pjj > 0, akkor pii d(i)|n+s+m és d(i)|n+2s+m, amib®l d(i)|s következik. d(i) tehát közös osztója az ilyen s számoknak, azaz d(i)|d(j). Mivel i és j szerepe felcserélhet®, az állítást beláttuk.

2.8. Tétel.

Legyen

C osztály d periódussal, és i ∈ C tetsz®leges. Ekkor C felbomlik d darab C0 (i), C1 (i), . . . , Cd−1 (i) részosztályra úgy, hogy ha j ∈ Cr (i) (n) és pij > 0, akkor szükségképpen n ≡ r mod d. Továbbá létezik N (j) küszöbindex, hogy (nd+r) n ≥ N (j) esetén pij > 0.

Bizonyítás. (m) pij

> 0,

(Részosztályok) Legyen

akkor

(k)

j ∈ C . Létezik k , hogy pji > 0. d|k + n és d|k + m, azaz n ≡ m mod d.

Legyen

Ha

n-re

és

(n)

m-re pij > 0

és

2. VISSZATÉRSÉG

6

P d= K k=1 ck nk alakban, 2 N = n0 max |ck |. Osszuk el az n ≥ N

A második állításra rátérve, a legnagyobb közös osztó el®áll ahol

ck

számot

P (n ) pii k > 0. Legyen n0 = nk , és maradékosan n0 -val : n = ln0 + q . Ekkor

egész, és

nd =

K X

(ld + qck )nk ,

k=1

és ebben a lineáris kombinációban az együtthatók már nemnegatívak. Ezért

((n+m0 )d+r) és pij

>

(m d+r) 0, ha pij 0

> 0.

Tehát

N (j) = N + m0

Vegyük észre, hogy a részosztályok függetlenek az függ t®le : ha

j ∈ Cr (i)

és

k ∈ Cs (i),

akkor

i

(nd)

pii

> 0,

jó lesz.

állapottól, csak az indexelésük

k ∈ Cs−r (j).

A fenti tétel segítségével

belátható, hogy legtöbbször elég irreducibilis és aperiodikus Markov láncokat vizsgálni. A nem lényeges állapotokat elhagyva ugyanis, ha egyszer belekerülünk valamelyik

d periódussal, és P (X0 ∈ Cr ) = 1, akkor az {Xnd }n=0,... egy irreducibilis, aperiodikus ML Cr állapottérrel (d) és qij = pij átmenetvalószín¶ségekkel. osztályba, akkor végleg ott is maradunk. Ha tehát

2.9. Példa.

C

lényeges osztály

Legyen az átmenetmátrix a következ® :

               

 0 1/4 1/4 0 0 0 1/2 0  1 0 0 0 0 0 0 0   0 1/2 0 1/2 0 0 0 0    0 0 0 0 2/3 0 0 1/3   0 0 0 0 0 1 0 0    0 0 0 0 1/2 0 1/2 0   0 0 0 0 0 0 1 0   0 0 0 0 0 0 0 1

Adjuk meg a ML osztályait, keressük meg közülük a lényegeseket ! Mennyi az egyes osztályok periódusa ?

2.3. Visszatér®ség Vezessük be a következ® jelöléseket :

(0)

fij = 0,

(n)

fij = P (Xn = j, Xk 6= j : k = 1,2, . . . n − 1 | X0 = i) n ≥ 1,

2. VISSZATÉRSÉG

Az az

7

(n)

fij mennyiség tehát annak valószín¶sége, hogy az i állapotból indulva a lánc el®ször n. lépésben ér el a j állapotba. Legyen még fij∗

∞ X

=

(n)

fij ,

és

gij = P (Xn = j

végtelen sok

n-re | X0 = i).

n=1

2.10. Deníció.

Az

i

állapot visszatér® vagy rekurrens, ha

átmeneti vagy tranziens. Ha

=

P∞

(n) n=1 nfii . Az

i

i

fii∗ = 1,

egyébként pedig

visszatér®, akkor az átlagos visszatérési id®

állapot pozitív rekurrens, ha

m i < ∞,

ha pedig

mi = ∞,

mi = akkor

nulla rekurrens.

2.11. Állítás. 2.

i→j

1.

akkor és csak akkor, ha

fij∗ > 0.

gij = fij∗ gjj .

3. Ha

i

rekurrens állapot, akkor

gii = 1,

ha pedig

i

tranziens, akkor

gii = 0.

4. A nem lényeges állapotok tranziensek (fordítva azonban nem igaz). 5. Ha

gii = 1

Bizonyítás. 1.

fij∗ > 0,

akkor

gij = 1.

A fenti állítások az utolsó kivételével egyszer¶en láthatók.

(n)

(n)

és

fij ≤ pij

és

(n)

pij ≤

2. A végtelen sok

Pn

(m)

m=1

n-re

fij

, ezért

(n)

supn≥1 pij ≤ fij∗ ≤

P∞

(n)

n=1

pij

.

kifejezésre a v.s. rövidítést használva,

gij = P (Xn = j v.s. | X0 = i) = ∞ X P (Xn = j v.s., Xk = j, Xl 6= j : l = 1, . . . , k − 1 | X0 = i) = k=1 ∞ X

P (Xn = j

v.s.

(k)

| Xk = j, Xl 6= j : l = 1, . . . , k − 1, X0 = i)fij =

k=1 ∞ X

(k)

gjj fij = gjj fij∗ .

k=1

gii (m) = P (Xn = i legalább m különböz® n > 0− ra | X0 = i), ha m ≥ 1. gii (1) = fii∗ , és gii = limm→∞ gii (m). Viszont m ≥ 2-re

3. Legyen Ekkor

gii (m) =

∞ X k=1

(k)

fii gii (m − 1) = fii∗ gii (m − 1).

2. VISSZATÉRSÉG

Tehát

8

gii (m) = (fii∗ )m .

j olyan, hogy i → j , de j 6→ i. Létezik olyan állapotsorozat, melyre pˆ = pii1 pi1 i2 · · · pin j > 0, és a bels® állapotok egyike sem i. Ekkor fii∗ ≤ 1 − pˆ.

4. Legyen

Az utolsó állítás bizonyításához tegyünk egy kis kitér®t a megállási id®k világába ! Legyenek adva az

τ :Ω→N értelmes az azt a

Xn

valószín¶ségi változó megállási id®, ha

Xτ : ω 7→ Xτ (ω) (ω)

σ -algebrát,

Fn = σ(X0 , . . . , Xn ). A {τ = n} ∈ Fn minden n-re. Ekkor

valószín¶ségi változók, és most is

valószín¶ségi változóról beszélni. Deniálhatjuk még

amely a megállás id®pontjáig meggyelhet® eseményekb®l áll :

Fτ = {A ∈ F∞ : A ∩ {τ = n} ∈ Fn ∀n}. Err®l könnyen látható, hogy valóban

σ -algebra.

Xn folyamatra teljesül az er®s Markov-tulajdonság, id®re, k ≥ 0-ra és B mérhet® halmazra

Azt mondjuk, hogy az den

τ

véges megállási

ha min-

P (Xτ +k ∈ B | Fτ ) = P (Xτ +k ∈ B | Xτ ). Vegyük észre, hogy ha

Xτ = Xn

és

Fτ = Fn ,

P (τ = n) = 1,

azaz

τ

(1)

determinisztikus megállási id®, akkor

azaz az er®s Markov tulajdonságból következik a közönséges.

Fordítva általában nem igaz ez az állítás, de a mi esetünkben igen.

2.12. Tétel.

Az

Bizonyítás.

El®ször belátjuk, hogy (1) jobb oldala

{Xn }n≥0

Markov láncra teljesül az er®s Markov tulajdonság.

Fτ -mérhet®,

azaz

σ(Xτ ) ⊆ Fτ .

{Xτ ∈ B} ∩ {τ = n} = {Xn ∈ B} ∩ {τ = n} ∈ Fn . Másrészt,

Fτ

is atomos, tehát elég az egyenl®séget az atomokon bizonyítani. Egy atom

általános alakja :

C = {τ = m, X0 = i0 , . . . , Xm = im }. Fτ -beliek, diszjunktak, kiadják a teljes Ω-t, és ha A ∈ Fτ , akkor A ∩ C = = (A ∩ {τ = m}) ∩ C . Mivel a metszet els® tagja Fm -beli, ami atomos, van olyan Z Ezek nyilván

halmaz, melyre

A ∩ {τ = m} = ∪(j0 ,...,jm )∈Z {X0 = j0 , . . . , Xm = jm }.

2. VISSZATÉRSÉG

Ezt

C -vel

9

elmetszve, a metszet vagy üres, vagy maga

C.

Azt kell tehát belátni, hogy

Z P ((Xτ +k ∈ B) ∩ C) =

I(Xτ +k ∈ B)dP = Z P (Xτ +k ∈ B|Xτ )dP = P (Xτ +k ∈ B|Xτ = im )P (C).

C

C

C

A pozitív valószín¶ség¶

atomon a Markov tulajdonság szerint

P (Xτ +k ∈ B | C) =

X

(k)

pim j .

j∈B A fentiek szerint azt kell belátni, hogy

P (Xτ +k ∈ B | Xτ = im )

is ugyanennyi. Ehhez

egyrészt azt kell látni, hogy

P (Xτ +k ∈ B | Xτ = im , τ = n) =

X

(k)

pim j

j∈B

An = {Xτ = im , τ = n} A = ∪An = {Xτ = im }, ekkor

a közönséges Markov tulajdonság szerint, másrészt legyen ezen diszjunkt események unióját jelölje

P P (Xτ +k ∈ B | A) =

P (Xτ +k ∈ B | An )P (An ) X (k) P = pim j . P (An ) j∈B

τ megállási (k) = j|Xτ = i) = pij .

Vegyük észre, hogy beláttuk, hogy a újraindul, azaz

P (Xτ +k

id®t®l a ML a múlttól függetlenül

A még bizonyítandó állításra visszatérve, deniáljuk azt a

n-edszer

térünk vissza az

véges, és

Xτn = i.

i

állapotba. Ekkor

τn

An

τn

id®pontot, amikor

megállási id®, amely

1

valószín¶séggel

Legyen

An = {Xτn +1 , Xτn +2 , . . . , Xτn+1 −1 Ekkor

és

független az

Fτn σ -algebrától,

valamelyike

melybe az

j} ∈ Fτn+1 .

A1 , . . . , An−1

események tartoznak,

mivel az er®s Markov tulajdonság szerint

P (An | Fτn ) = P (An | Xτn ) = P (An ), σ(Xτn ) a triviális σ -algebra. A lánc újraindulási tulajdonságából következik, P (An ) = p > 0, n-t®l függetlenül (p annak az esélye, hogy i-b®l indulva el®bb

hiszen hogy

2. VISSZATÉRSÉG

érünk

j -be,

10

mint vissza

i-be).

események közül végtelen sok következik be, azaz

fij∗ = 1

ekkor az is igaz, hogy

2.13. Tétel.

gij = 0

1

A Borel-Cantelli lemma szerint

és

gjj = 1,

gij = 1.

valószín¶séggel az

An

Érdemes megjegyezni, hogy

azaz a visszatér®ség osztálytulajdonság.

akkor és csak akkor, ha

P∞

(n)

n=0

pij < ∞.

A bizonyítás el®tt egy nagyon hasznos kis lemmát látunk be, mely a Toeplitz szummációs tétel speciális esete.

2.14. Lemma. Ha

limn→∞ an /

(Nörlund) Legyenek

Pn

k=0

ak = 0,

an ≥ 0

és

bn

valós sorozatok, és

limn→∞ bn = b.

akkor

Pn k=0 ak bn−k lim P = b. n n→∞ k=0 ak

Bizonyítás.

A bizonyítást arra az esetre végezzük el, amikor

is hasonlóan intézhet® el. Legyen

-hoz N

olyan küszöbindex, hogy

|

n X

B olyan, hogy |bn − b| < B n ≥ N esetén |bn − b| < . n−N X

ak (bn−k − b)| ≤ (

k=0 Ebb®l

n X

ak ) + (

k=0

véges, a végtelen eset minden

n-re,

és adott

ak )B.

k=n−N +1

Pn Pn k=0 ak bn−k k=n−N +1 ak Pn lim sup Pn − b ≤ + B lim = . n→∞ ak ak n→∞ k=0

Megjegyzés : Ha az

Bizonyítás.

b

an

k=0

sorozat korlátos, akkor biztosan teljesíti a lemma feltételét.

(2.13 Tételé.)

n X r=1

(r)

pij =

n X r−1 X

(r−k) (k) pjj

fij

n−1 X

=

r=1 k=0

(k) pjj ,

bk =

k X

n−k X

(s)

fij =

s=1

k=0

ahol

ak =

(k)

pjj

(s)

fij ,

n X

ak bn−k ,

k=0

b0 = 0.

s=1 Ekkor az el®z® lemmát alkalmazva,

b = fij∗ , Pn

lim Pm=1 n n→∞ m=0

és

(m)

pij

(m) pjj

= fij∗ .

(2)

2. VISSZATÉRSÉG

11

i = j esetre alkalmazzuk, akkor megkapjuk, hogy i akkor és csak akkor P∞ (n) visszatér®, ha n=0 pii = ∞. Most tegyük fel, hogy i 6= j és gij = 0. Ekkor vagy (n) fij∗ = 0, vagy gjj = 0. Az els® esetben pij = 0 minden n-re, azaz a sor összege nulla. P (n) P (n) A második esetben j tranziens állapot, ezért pjj véges, és így pij is. Ha most P (n) gij > 0, akkor gjj = 1, azaz j rekurrens, és fij∗ > 0, amib®l pij = ∞ adódik. Ha ezt az

Egy táblázatban foglalhatjuk össze, hogy tetsz®leges két állapot esetén mi mondható el az

fij∗ , gij ,

P

(n)

pij

mennyiségekr®l :

fij∗

gij

P

(n)

pij

i, j

ugyanabban a rekurrens osztályban

1

1

∞

i, j

ugyanabban a tranziens osztályban

>0

0

<∞

i, j

különböz® osztályban,

i → j, j

tranziens

>0

0

<∞

i, j

különböz® osztályban,

i → j, j

rekurrens

i 6→ j

∞

c>0 c>0 0

0

0

Mindezek segítségével kiszámolható például az, hogy az egydimenziós bolyongás akkor és csak akkor visszatér®, ha szimmetrikus.

2.15. Példa.

Bolyongás a számegyenesen. Legyen a jobbra lépés valószín¶sége

q = 1 − p (p, q > 0). A lánc irreducibilis, visszatér®séget ! Elég a 0 állapottal foglalkozni. balra lépésé

(2n) p00

Felírható, hogy

∞ X 2n n=0

n

=

periódusa

2.

p,

a

Vizsgáljuk a

2n n p (1 − p)n . n

xn = (1 − 4x)−1/2 ,

ha

0 < 4x < 1.

|1 − 2p|−1 < ∞, azaz a (2n) 1 lánc tranziens. Szimmetrikus esetben viszont a lánc rekurrens (p00 ∼ √ ). Tranziens πn ∗ esetben érdekesek az fij valószín¶ségek. Tegyük fel el®ször, hogy i > j . Nyilvánvaló, ∗ ∗ i−j hogy fij = (f10 ) . (2) szerint Ha tehát

p 6= 1/2,

akkor az átmenetvalószín¶ségek sorösszege

∗ f10

P∞

=

n=1 P∞ n=0

(n)

p10

(n)

p00

.

2. VISSZATÉRSÉG

12

Mármost

(2n+1) p10

=

2n+1 n 1 2n + 2 n+1 n+1 p (1 − p)n+1 , p (1 − p) = 2p n + 1 n

ezért

∗ f10 =

1 2p

1 |1−2p|

−1

1 |1−2p|

1 = (1 − |1 − 2p|) = 2p

Hasonlóan járhatunk el, ha

i < j, (

∗ f01

mennyiség kell. Végül pedig

∗ f00

P∞

=

(

1, (1 − p)/p,

ha ha

p < 1/2 . p > 1/2

ehhez csak az

p/(1 − p), 1,

∗ fii∗ = f00 ,

ha ha

p < 1/2 p > 1/2

és

(2n)

n=1 p00 = P∞ = 1 − |1 − 2p| = (2n) p n=0 00

(

2p, 2(1 − p),

ha ha

p < 1/2 . p > 1/2

2.4. Az átmenetvalószín¶ségek konvergenciája Az eddigiekb®l az következik, hogy ha

j

átmeneti állapot, akkor

(n)

pij → 0.

Vajon

rekurrens állapot esetén mit mondhatunk err®l a határértékr®l ?

2.16. Tétel.

Ha

Bizonyítás.

Az egyszer¶ség kedvéért vezessük be a következ® jelöléseket :

fn =

i

rekurrens állapot

d

periódussal, akkor

(nd)

limn→∞ pii

=

d . mi (n)

pn = pii

,

(n) fii . El®ször belátjuk, hogy a

{n ≥ 1 : fn > 0} halmaz legnagyobb közös osztója

d.

Legyen ugyanis ez a legnagyobb közös osztó

df .

Mivel

{n ≥ 1 : fn > 0} ⊂ {n ≥ 1 : pn > 0}, d|df . Másrészt, ha pn > 0, akkor n el®áll n = n1 + . . . + nk alakban, ahol fni > 0. Ezért df |n, azaz df közös osztó, és így df |d. P∞ Legyen ezután rn = k=n+1 fk , azaz annak a valószín¶sége, hogy az els® n lépés

2. VISSZATÉRSÉG

13

alatt nem térünk vissza

i-be.

∞ X

Igazak a következ® összefüggések :

rk =

k=0

∞ X

kfk = mi ,

k=1

n X

rk pn−k = 1,

k=0

a második összefüggés úgy adódik, hogy a lánc lehetséges meneteit az bontjuk aszerint, hogy hányadik lépésben járt utoljára az

n.

lépésig fel-

i állapotban (éppen az n − k .

lépésben). Ha

lim supn→∞ pnd = λ,

akkor válasszunk egy olyan részsorozatot, melyre

lim pnk d = λ.

k→∞ Tetsz®leges olyan

s-re,

melyre

fs > 0, nk d X

λ = lim pnk d = lim (fs pnk d−s + k→∞

mivel

pn =

Pn

j=1

k→∞

fν pnk d−ν ),

ν=1,ν6=s

fj pn−j . Tetsz®leges > 0-hoz legyen N

olyan nagy, hogy

P∞

n=N

fn < .

Ekkor

nk d X

nk d X

fν pnk d−ν =

ν=1,ν6=s

N −1 X

fν pnk d−ν +

ν=N,ν6=s

fν pnk d−ν ≤

ν=1,ν6=s

+

N −1 X ν=1,ν6=s

Felhasználva, hogy

lim(an + bn ) ≤ lim inf an + lim sup bn ,

λ ≤ fs lim inf pnk d−s + k→∞

∞ X

! fν

sup pnk d−ν .

ν
folytathatjuk a fenti sort :

! fν

λ = fs lim inf pnk d−s + (1 − fs )λ. k→∞

ν=1,ν6=s

lim inf k→∞ pnk d−s ≥ λ, azaz P limk→∞ pnk d−s = λ. Ugyanez igaz akkor is, ha s = cj sj alakú, ahol cj > 0 egész szám, és fsj > 0. Mivel minden elég nagy t esetén td felírható ilyen alakban (ezt a részosztályokról szóló tételnél bizonyítottuk), elmondhatjuk hogy t ≥ t0 esetén limk→∞ p(nk −t)d = = λ. Mármost (nk −t0 )d nX k −t0 X rνd p(nk −t0 −ν)d , 1= rh p(nk −t0 )d−h = Ezt átrendezve azonnal következik, hogy

h=0

ν=0

2. VISSZATÉRSÉG

hiszen

pn

14

csak akkor lehet pozitív, ha

Pmk

d | n.

bm sorozatról hogy konvergens, csak a bmk −ν sorozatokról, minden rögzített ν -re. P∞ Tegyük fel el®ször, hogy ν=0 rνd = ∞, ekkor minden N -re

a Nörlund lemmában, azaz

ν=0

1 ≥ lim

N X

k→∞

tehát

λ = 0.

Ha viszont

m¶ködik : válasszuk

|

nX k −t0

P∞

N -et

aν bmk −ν ,

Egy olyan jelleg¶ összeg jelent meg, mint

ν=0 rνd

csakhogy most a

rνd p(nk −t0 −ν)d = λ

ν=0

N X

nem tudjuk,

rνd ,

ν=0

< ∞,

akkor a Nörlund lemmához hasonló bizonyítás

olyan nagyra, hogy

rνd (p(nk −t0 −ν)d − λ) |≤

ν=0

N X

P∞

ν=N +1 rνd

<

legyen. Elég nagy

k -ra

rνd | p(nk −t0 −ν)d − λ | + ≤ 2.

ν=0

Tehát

1−λ

nX k −t0

rνd → 0,

ν=0 amib®l

λ = 1/

P

rνd

következik (és ez a végtelen esetben is érvényes).

Írjuk át a tört nevez®jét :

∞ X

rνd =

νd+d−1 ∞ X 1 X ν=0

ν=0

d

j=νd

∞

rj =

1X mi rj = . d j=0 d

Megkaptuk tehát, hogy a sorozat limsupja a kívánt érték. Ha most

lim inf n→∞ pnd = η , akkor az el®z® = λ, azaz limn→∞ pnd létezik.

gondolatmenet lemásolásával azt kapjuk, hogy

η=

i állapot akkor és csak akkor pozitív rekurrens, ha a (nd) limn→∞ pii határérték pozitív. Az is könnyen látszik, hogy a pozitivitás osztálytulajAzt kaptuk tehát, hogy az

i és j ugyanabban a rekurrens osztályban vannak, akkor van olyan n és m, (m) (m+kd+n) (n) (kd) (m) > 0 és pji > 0. A pii ≥ pij pjj pji kifejezésben k -val végtelenhez azt kapjuk, hogy ha j pozitív állapot, akkor szükségképpen i is az.

donság : ha

(n) hogy pij tartva

Most már könnyen bebizonyítható a következ® általános tétel.

2.17. Tétel. = 1,2, . . . , d

Legyen

i, j

két tetsz®leges állapot, és jelölje

esetén

(nd+r)

lim pij

n→∞

= fij∗ (r)

d , mj

j

periódusát

d.

Ekkor

r=

2. VISSZATÉRSÉG

ahol

fij∗ (r) ≥ 0

Bizonyítás.

és

Pd

15

fij∗ (r) = fij∗ . (Tranziens állapotra P (nd+r) fij∗ (r) = ∞ . Ekkor n=0 fij

r=1

Legyen

(nd+r) pij

=

n X

legyen

mj = ∞.)

(kd+r) (nd−kd) pjj .

fij

k=0

A Nörlund lemmából azonnal következik az állítás,

(kd+r)

ak = fij

,

(kd)

bk = pjj

szere-

posztással.

2.18. Következmény. oldal azt fejezi ki, hogy

j

Minden

i-b®l

i, j

állapotpárra

lim n−1

Pn

k=1

(k)

pij = fij∗ /mj .

Itt a bal

indulva, a lánc várhatóan a lépések hányad részét tölti a

állapotban.

2.19. Példa.

Az egydimenziós szimmetrikus bolyongás nulla rekurrens.

2.20. Példa.

Vegyünk egy bolyongást a nemnegatív számokon, a nullában egy vissza-

ver® fallal. Legyen a jobbra lépés esélye irreducibilis, periódusa

d = 2.

p < 1/2,

a balra lépésé

q = 1 − p.

A lánc

Korábbi számolásunk alapján a lánc visszatér®. A mag-

asabb rend¶ átmenetvalószín¶ségeket nem könny¶ kiszámítani, viszont az elérési id®kre (átlagosan ennyi lépés alatt érünk i-b®l

mij

átlagos

j -be) fel tudunk írni egyenleteket.

m00 = 1 + m10 , m10 = q + p(1 + m20 ), m20 = m21 + m10 , m21 = m10 . Ezeknek az egyenleteknek a végtelen is megoldása, tegyük azonban fel, hogy a mennyiségek végesek. Ekkor az

m00 = 1 +

1 1 1 − 2p d p , = , =1− 1 − 2p m00 2 − 2p m00 q

megoldás adódik. Ha tehát a lánc nulla állapotból átlagosan ránézve a láncra, kb.

2/3

1/4

eséllyel lép jobbra, és

3/4

eséllyel balra, akkor a

3 lépés alatt ér vissza a nullába, egy távoli páros id®pontban eséllyel lesz éppen a nulla állapotban, és a láncot sokáig

futtatva, nagyjából a lépések

1/3-át

tölti a nulla állapotban (és ez utóbbi nem függ a

kezdeti eloszlástól).


2.21. Deníció. cionárius, ha

pi =

P egy átmenetvalószín¶ségmátrix. A (pi )i∈I eloszlás stak∈I pk pki minden i ∈ I -re, azaz a pi kezdeti eloszlású, P átmenetva-

Legyen

P

2. VISSZATÉRSÉG

lószín¶ség¶

Xn

16

Markov láncra

P (Xn = i) = pi

i ∈ I, n ≥ 0-ra.

minden

Ez utóbbi eset-

ben azt mondjuk, hogy a Markov lánc stacionárius (ez megfelel a szokásos deníciónak, azaz hogy a véges dimenziós eloszlások eltolás-invariánsak).

2.22. Tétel.

Legyen

C

πi = 1/mi .

lényeges osztály, és jelölje

ui =

X

Ekkor az

uk pki , i ∈ C

k∈C egyenletrendszer

Bizonyítás. rens, akkor

P

|ui | < ∞

i∈C

megoldásai :

ui = cπi .

El®ször belátjuk, hogy ezek megoldások. Ha

πi = 0.

C

Legyen

(nd)

pii

=

n

X

(nd−1)

pik

X

pki =

(nd−1)

pik

(nd)

P

k∈C

πk pki .

X

≥

(nd−1)

lim pik

X

n→∞

(nd+r)

pij

i∈C

πi ≥

i∈C

P

πi

≥

X

(nd+r)

lim pij

n→∞

X

=

dπj ,

j∈Cr (i)

πi ≤ 1. X

ami a

dπk pki ,

k∈C−1 (i)

j∈Cr (i)

j∈Cr (i)

P

X

pki =

Másrészt, mivel

1 = lim

ezért

pki .

k∈C−1 (i)

k∈C−1 (i)

πi ≥

d.

végtelenhez :

dπi = lim pii

azaz

átmeneti vagy nulla rekur-

pozitív rekurrens, jelölje periódusát

k∈C Tartson

C

XX

πk pki =

i∈C k∈C

X k∈C

végessége miatt csak úgy lehet, ha

πk

X

pki =

i∈C

πi =

X

πk ,

k∈C

P

k∈C

πk pki

minden

Ezután meg kell mutatni, hogy nincs más megoldás. Legyen

ui

i-re.

egy abszolút kon-

vergens megoldás. Ekkor

ui =

X k∈C−1 (i)

uk pki =

X

X

k∈C−1 (i) l∈C−1 (k)

ul plk pki =

X l∈C−2 (i)

ul

X k∈C−1 (i)

plk pki =

X

(2)

ul pli ,

l∈C−2 (i)

(a szummák az abszolút konvergencia miatt felcserélhet®k), ezt iterálva kapjuk, hogy

2. VISSZATÉRSÉG

17

n, r-re

minden

X

ui =

(nd+r)

uk pki

.

k∈C−r (i) Mivel az összeg tagjainak van konvergens majoránsa, határértéket véve kapjuk, hogy



 X

ui = 

uk  dπi , ∀r.

k∈C−r (i)

C

Ha

átmeneti vagy nulla rekurrens, akkor

szükségképpen

P

k∈C−r (i)

Megjegyzés : az

uk = K

ui = π i

konstans,

ui = 0, ha pedig és ui = Kdπi .

megoldásra tehát visszahelyettesítéssel :



 X

πi = 

πk  dπi ,

P

i∈C

πi = 1

X

azaz

k∈C−r (i) amib®l

pozitív rekurrens, akkor

k∈C−r (i)

C

is következik. A

1 πk = , d

pozitív osztályon tehát

πi

stacionárius kezdeti

eloszlás.

2.23. Tétel.

Legyen adott a

Dα : α ∈ A,

itív osztályokat a

pi

P

sztochasztikus mátrix az

és legyen

állapottéren. Jelölje a poz-

a pozitív állapotok halmaza. Ekkor

eloszlás akkor és csak akkor stacionárius, ha

(

0 λα π i

pi = ahol

D = ∪α Dα

I

λα ≥ 0,

Bizonyítás. i 6∈ D,

P

α

⇒:

ha ha

i 6∈ D, i ∈ Dα ,

λα = 1. Ha

pi

stacionárius eloszlás, akkor minden

akkor határátmenettel

pi =

X

(n)

pj lim pji = 0,

j∈I ha pedig

i ∈ Dα ,

akkor az el®z® miatt

pi =

X j∈D

(n)

pj pji =

X j∈Dα

(n)

pj pji ,

n-re pi =

P

j∈I

(n)

pj pji

. Ha

2. VISSZATÉRSÉG

18

hiszen másik pozitív osztályból nem lehet

pi =

X j∈Dα

i-be

jutni. Ezért minden

N -re

N 1 X (n) pj p , N n=1 ji

P P pi = ( j∈Dα pj )πi , azaz λα = j∈Dα pj . ⇐: Ha i 6∈ D, akkor P (Xn = i) = 0 minden n-re, hiszen a pozitív lép ki a lánc. Ha viszont i ∈ Dα , akkor amib®l határátmenettel

P (Xn = i) =

X

(n)

pk pki = λα

X

(n)

πk pki = λα πi = pi ,

k∈Dα

k∈Dα

πi

hiszen az el®z® tétel bizonyításánál láttuk, hogy

i ∈ Dα ,

osztályokból nem

stacionárius eloszlás

Dα -n,

azaz ha

akkor

πi =

X

(n)

πk pki .

k∈Dα

Összefoglalva azt kaptuk, hogy egy stacionárius Markov lánc csak pozitív osztályokból áll. Egy osztályban egyértelm¶en létezik stacionárius eloszlás, a Markov lánc eloszlása ezen stacionárius eloszlások keveréke. Az osztályokat még részosztályokra is szét lehet bontani (nd + r alakú id®pontokban ránézve), így irreducibilis, pozitív rekurrens, aperiodikus láncokat kapunk, egyértelm¶ stacionárius eloszlással, és tetsz®leges

Xn eloszlása a stacionárius eloszláshoz tart. (Tetsz®leges Markov eloszlásból elindítva vizsgálhatjuk, hogy Xn eloszlása hová tart.)

kezdeti eloszlás esetén láncot tetsz®leges

2.24. Példa.

A most belátottak segítségével bizonyítható, hogy a korábbi példában

szerepl® egydimenziós bolyongás a

0-ban

visszaver® fallal pozitív rekurrens. Megold-

hatók ugyanis a stacionárius eloszlás egyenletei, és kapjuk, hogy

π0 =

2.25. Példa. n

1 − 2p , 2 − 2p

πi = π 0

Egy érmét, melyen a fej valószín¶sége

dobásból alkotott sorozat végén hány fej van.

láncot alkot, eloszlást !

pi−1 , i ≥ 1. qi

P (X0 = 0) = 1,

és

pk,k+1 = p, pk,0

p, dobálva, jelölje Xn , hogy az els®

Xn irreducibilis, aperiodikus Markov = 1 − p = q . Keressünk stacionárius

3. POZITíV REKURRENS MARKOV LÁNCOK

(i)

Oldjuk meg a

π = πP

19

egyenletrendszert :

π0 = q

∞ X

πk = q, πi = pπi−1 = pi q,

k=0

Geo(q) − 1. (n) Tekintsük a pik átmenetvalószín¶ségek határértékét. Ha

azaz a stacionárius kezdeti eloszlás

(ii)

n > k,

akkor

(n)

pik = pk q .

Ennek segítségével könnyen kiszámítható, hogy átlagosan hány dobás kell ahhoz, hogy egy

k

hosszú fejsorozat megjelenjen. Legyen ez a mennyiség

µk .

Erre

mk = mk0 + m0k = 1/q + µk , és mivel

mk = 1/πk ,

kapjuk, hogy

µk =

1−pk . qpk

3. Pozitív rekurrens Markov láncok 3.1. Deníció.

Nevezzük az

Xn

Markov láncot ergodikusnak, ha irreducibilis és poz-

itív rekurrens. (Figyelem : az irodalomban nem feltétlenül ezt nevezik ergodikusnak ! !)

Láttuk, hogy az ilyen Markov láncok hosszú távú viselkedését különösen egyszer¶ leírni (ha még aperiodikusak is, akkor ez még inkább igaz).

3.1. Nagy számok törvénye

3.2. Tétel.

Legyen

Xn

ergodikus Markov lánc

tetsz®leges függvény. Ha

I(f ) =

P

i∈I

f (i)πi

πi

stacionárius eloszlással, és

f :I→R

sor abszolút konvergens, akkor

n

1X f (Xk ) → I(f ) 1 n k=0 Megjegyzés : A

Bizonyítás.

Zn = f (Xn )

Legyen

id®ket, melyek az

i∈I

i-be

valószín¶séggel.

sorozat nem feltétlenül Markov lánc.

tetsz®leges rögzített állapot, deniáljuk azokat a megállási

tett látogatások id®pontjait adják meg :

0 = τ0 < τ 1 < . . . ,


τn

az

n.

elérési id®pont. Ezek

1

valószín¶séggel véges megállási id®k. Minden

l(n) valószín¶ségi változót, amely lánc i-ben : τl(n) ≤ n < τl(n)+1 .

deniáljuk azt az hányszor járt a

A

Zk -k

20

megmondja, hogy az

n.

n-re

lépésig

összegére a következ® felbontási formulát használjuk :

n X

Zk =

k=0

τX 1 −1

l(n)−1 τh+1 −1

Zk +

k=0

X X h=1

Zs +

s=τh

n X

l(n)−1 0

Zk = Y +

k=τl(n)

1 l(n)

X h=1

Yh + Y 00 (n).

h=1

Pozitív és negatív részre való felbontással feltehet®, hogy

l(n)−1

X

f ≥ 0.

Ekkor

  l(n) n X X 1 1  0 Yh ≤ Zk ≤ Y + Yh  . l(n) k=0 l(n) h=1

Korábban már meggondoltuk, hogy az er®s Markov-tulajdonság miatt az függetlenek, és azonos eloszlásúak. Mivel

1

Yh

változók

valószín¶séggel végtelen sokszor jár a lánc

i-ben, l(n) 1 valószín¶séggel végtelenhez tart. Ezért a nagy számok er®s törvénye szerint l(n)

1 X Yh → E(Yh ) 1 l(n) h=1 Másrészt

Y 0 /l(n) → 0 (1


valószín¶séggel), tehát

1 l(n)

Pn

k=0

Zk

is tart

E(Yh )-hoz 1

va-

lószín¶séggel. Számítsuk ki ezt a várható értéket ! Az egyszer¶ség kedvéért tegyük fel, hogy a lánc

i-b®l

E(Yh ) = E

indul. Ekkor

∞ X k=0

P∞

Zk χ{k < τ1 }

=

∞ X X k=0 j∈I

f (j)P (Xk = j, k < τ1 ) =

X

f (j)uj ,

j∈I

P (Xk = j, k < τ1 ), azt fejezi ki, hogy két i-ben tett látogatás között a lánc átlagosan hányszor jár j -ben (a kezd®pontot beleszámítva, a végpontot nem). P Ezért j∈I uj = mi < ∞. Megmutatjuk, hogy uj kielégíti a stacionárius eloszlás

ahol

uj =

!

k=0


21

egyenletrendszerét.

X

uj pjl =

∞ XX

j

j ∞ X

P (Xk = j, k < τ1 )P (Xk+1 = l | Xk = j) =

k=0

E [P (Xk+1 = l | Xk )χ{k < τ1 }] =

k=0

∞ X

E [P (Xk+1 = l | Fk )χ{k < τ1 }] ,

k=0

ahol az utolsó lépésben a Markov tulajdonságot használtuk. Felhasználva, hogy

< τ1 } Fk -mérhet®, X

uj pjl =

j

∞ X

χ{k <

folytathatjuk :

E [E(χ{Xk+1 = l, k < τ1 } | Fk )] =

k=0 ∞ X

P (Xk+1 = l, k < τ1 ) =

k=0 Ez pedig tényleg

ul ,

∞ X

P (Xk = l, k ≤ τ1 ).

k=1

hiszen a kezd®pontot kihagytuk, a végpontot viszont bevettük, de

i állapotban van a lánc, az összeg nem változott. Ezért uj = cπj . 1 = ui = cπi , azaz uj = πj /πi . Tehát

mivel mindkett®ben az Ha most

i = j,

akkor

E(Yh ) =

X

f (j)uj =

j∈I Ha most

f (j) = 1

minden

j -re,

I(f ) . πi

akkor azt kapjuk, hogy

n

n+1 1 X 1 = Zk → , l(n) l(n) k=0 πi azaz

n

n

1 X l(n) 1 X Zk = Zk → I(f ) 1 n + 1 k=0 n + 1 l(n) k=0

3.3. Példa.


i = (i1 , . . . , ik ) egy k hosszú állapotsorozat, ahol pi1 i2 ·pi2 i3 · · · pik−1 ik > > 0. Hová tart az i sorozat relatív gyakorisága n lépésb®l ? Válasz : πi1 · pi1 i2 · pi2 i3 · · · pik−1 ik -hez. (Készítünk egy új ML-ot, melynek állapotai a k hosszú sorozatok, ez is ergodikus lesz, tehát alkalmazható rá a tétel). Legyen


22

3.2. Centrális határeloszlás-tétel Ugyanabban a felállásban, mint az el®bb, vizsgáljuk, hogy a részletösszegeket hogyan kell normálni, hogy normális határeloszlást kapjunk. Két lemmára lesz szükségünk.

3.4. Lemma. Bizonyítás.

P (n − τl(n) ≥ t) ≤ ct ,

Legyen

P (n − τl(n) ≥ t) =

n ≥ t.

n X

ahol

Jelölje az

limt→∞ ct = 0.

i-be

való visszatérés lépésszámát

τ.

P (n − τl(n) = s) =

s=t n−1 X

P (Xn−s = i)P (τ > s) + P (τ1 > n) ≤

∞ X

s=t és ez valóban

P (τ > s) + P (τ1 > t) = ct ,

s=t

0-hoz

tart, mivel mind

τ

várható értéke véges,

τ1

pedig

1

valószín¶séggel

véges.


Legyen

P (|Y 00 (n)| ≥

Ha

t

Y 00 (n) √ n

A felbontási formula jelölésével,

, δ √

adott. Minden

τl(n) +s

n) ≤ P (n − τl(n) > t) + P  max | 0<s≤t

< δ/2,

< δ/2

sztochasztikusan.

t-re 

elég nagy, akkor az els® tag

a második tag is

→0

minden

mivel a zárójelben egy

1

n-re,

X

Zj | ≥

√

 n .

j=τl(n)

ezek után ha

n

elég nagy, akkor

valószín¶séggel véges,

n-t®l

független

valószín¶ségi változó áll.

Bizonyítás nélkül idézzük fel a Kolmogorov egyenl®tlenséget !

3.6. Lemma.

Vi független, nulla várható érték¶, véges szórású valószín¶ségi c > 0-ra

Legyenek

változók. Ekkor minden

P ( max | 1≤k≤n

k X i=1

Pn Vi | ≥ c) ≤

i=1

D2 (Vi ) . c2


3.7. Tétel. Ha

0<

Teljesüljenek az el®z® tétel feltételei, és legyen

E(Vh2 )

< ∞,

23

Vh = Yh − I(f )(τh+1 − τh ).

akkor

Pn

f (Xk ) − nI(f ) p → N (0,1). nπi E(Vh2 )

k=0

Bizonyítás.

A

Vh

valószín¶ségi változók függetlenek, azonos eloszásúak,

0

várható

érték¶ek. A felbontási formula szerint

n X

l(n)−1

Zk − nI(f ) =

k=0

X

Vh + Y 0 + Y 00 (n) − I(f )(n − τl(n) + τ1 ).

h=1

√ Y 0 / n sztochasztikusan 0-hoz tart. A 3.4 lemma szerint ugyanez √ √ 00 igaz az (n − τl(n) )/ n tagra, a 3.5 lemma miatt pedig Y (n)/ n is sztochasztikusan 0hoz tart. A Cramér-Szlujkij lemma szerint ezért elég csak a Vh -k összegével foglalkozni, Azt már tudjuk, hogy

azaz megmutatni, hogy

Pl(n)−1 Vh p h=1 → N (0,1). nπi E(Vh2 ) Szeretnénk a CHT-re hivatkozni, azonban itt az összegzés egy véletlen indexig történik, ett®l kellene megszabadulni. Legyen

n∗ = [nπi ].

Azt tudjuk, hogy

Pn∗ Vh p h=1 → N (0,1), ∗ n E(Vh2 ) n∗ -ot l(n) − 1-re cserélni. Tudjuk, hogy ezek nagy valószí0 00 egymáshoz. Legyen , δ adott, n = nπi (1 − δ), n = nπi (1 + δ),

itt kellene az összegzésben n¶séggel közel vannak és

Am = {n0 < l(n) − 1 < n00 , ∀n ≥ m}. Ezek b®vül® események, és

l(n) → πi n

minden

n ≥ m-re.

Ha pedig

⊂ ∪m Am .

1, ezért van olyan m, melyre P (An ) > 1 − l(n) − 1 és n∗ már közel vannak egymáshoz, akkor

Mivel a bal oldali esemény valószín¶sége

−


24

használhatjuk a Kolmogorov-egyenl®tlenséget.

  ∗ l(n)−1 n q X X 2δnπi E(Vh2 ) P  Vh − Vh ≥ c n∗ E(Vh2 ) ≤ + 2 ∗ < 2, 2 c n E(V ) h=1 h h=1 ha

δ

n

elég kicsi, és

tochasztikusan

0-hoz

elég nagy. Tehát

l(n) − 1-et n∗ -ra

cserélve, a különbség sz-

tart, így a Cramér-Szluckij lemmára való ismételt hivatkozással

készen vagyunk.

Vajon hogyan lehet az

E(Vh2 ) mennyiséget kiszámítani ? Már a NSzT-e bizonyításánál

Yh várható értéke kiszámolásakor olyan valószín¶ségek alatt i-b®l j -be megyünk, de közben nem járunk i-ben.

észrevehettük, hogy fel, hogy

n

lépés

bukkantak

3.3. Tabu állapotok

Xn

Legyen

ML, és

3.8. Deníció.

H⊆I

Átmenetvalószín¶ségek tabu állapotokkal :

(n) H pij (n) Jelölje H fij

(n)

= j,H pij

∗ Legyen még H pij hányszor jár a lánc

3.9. Lemma.

adódnak, a

=

=

= I(i = j, i 6∈ H).

P∞

(n) n=1 H pij , mely azt adja meg, hogy

j -ben,

míg

H -ba

= = = =

(n) k,H pij (n) k,H pij ∗ k,H pij ∗ k,H pij

i-b®l

indulva, várhatóan

beér (a beérést is beszámítva).

Alapformulák : legyen

n ≥ 1, k 6∈ H .

Ekkor

Pn−1 (s) (n−s) + k,H pik · H pkj Ps=1 (s) (n−s) n−1 + s=1 H pik · k,H pkj ∗ ∗ + k,H pik · H pkj ∗ ∗ + H pik · k,H pkj

(1A) (2A) (1B) (2B)

1-es formulák a k els®, a 2-esek a k utolsó elérése szerinti felbontásból B formulák pedig az A-k összegzésével keletkeznek. Az

3.10. Deníció. H mij

= P (Xn = j, Xm 6∈ H 0 < m < n|X0 = i).

(0) . Legyen H pij

(n) H pij (n) H pij ∗ H pij ∗ H pij

Bizonyítás.

tetsz®leges.

P∞

Legyen

(n) n=1 nH fij .

mij =

P∞

n=1

(n)

nfij

az átlagos elérési id®, általában pedig


25

∗ Megjegyzések : H fij : annak valószín¶sége, hogy mint

H -ba.

H mij

3.11. Lemma.

≤ mij .

Legyen

C

Ha

pozitív osztály,

i, j, k ∈ C , C

∗ El®ször is, k fij

(n)

(n)

pozitív osztály, és

∗ k fij

=

mjk + mkj , mik + mkj − mij

∗ k pij

=

mik + mkj − mij . mjj

továbbá

Bizonyítás.

i-b®l indulva, a lánc el®bb ér j -be, akkor mij < ∞ minden i, j ∈ C .

∗ + j fik = 1.

(n)

fij = j pij = k,j pij +

n−1 X

Másrészt az

(s)

(n−s)

k,j pik · j pkj

j 6= k .

(1A) (n)

formula szerint

= k fij +

s=1

Ekkor

n−1 X

(s) j fik

(n−s)

· fkj

.

s=1

Emiatt

mij = k mij +

∞ n−1 X X (s) (n−s) = n j fik · fkj n=1

= k mij +

s=1

∞ X

(s) j fik

s=1 Megcserélve

j

és

k

∞ X

(n−s)

((n − s)fkj

(n−s)

+ sfkj

∗ + j mik . ) = k mij + mkj · j fik

n=s+1

szerepét, kapjuk hogy

∗ ∗ mik +mkj −mij = mkj +mjk · k fij∗ −mkj · j fik = mjk · k fij∗ +mkj (1− j fik ) = k fij∗ (mjk +mkj ),

ami az els® bizonyítandó formula. Ebb®l speciális esetként kapjuk, hogy

∗ j fjk

Másrészt, az

(1B)

(2B)

mjj . mjk + mkj

formula szerint

∗ k pij

A

=

= j,k p∗ij + j,k p∗ij · k p∗jj = k fij∗ (1 + k p∗jj ).

formulából pedig

∗ ∗ (1 + k p∗jj ). 1 = fjk = k p∗jk = j,k p∗jk + k p∗jj · j,k p∗jk = j fjk


26

A fenti kett®t egymással elosztva,

∗ k pij

∗ k fij ∗ j fjk

=

k=i = mii /mjj .

Megjegyzés :

∗ hogy i pij

=

(mik + mkj − mij )/(mjk + mkj ) mik + mkj − mij = . mjj /(mjk + mkj ) mjj

helyettesítéssel ismét megkapjuk, (amit már eddig is tudtunk),

3.4. A CHT-ben szerepl® szórásnégyzet kiszámítása Visszatérve az eredeti feladathoz, a

τh+1 −1

X

Vh = Yh − I(f )(τh+1 − τh ) =

(f (Xn ) − I(f ))

n=τh

τh megállási Pτh+1 −1 id®k a rögzített i állapotba tett látogatások id®pontjai). Ehhez el®ször a n=τh g(Xn ) mennyiség négyzetének várható értékét számoljuk ki, majd ezt a g = f − I(f ) függvényre alkalmazzuk. Az egyszer¶ség kedvéért tegyük most is fel, hogy X0 = i. Ekkor mennyiség négyzetének várható értékét keressük (emlékezzünk arra, hogy a

E

h P τ1 −1 n=0

2 i g(Xn ) =

i i hP hP 2 2 ∞ g(X )χ{n ≤ τ }) = g(X )χ{n < τ }) = E ( E ( ∞ n 1 n 1 n=1 n=0 E

P∞

n=1

g 2 (Xn )χ{n ≤ τ1 } + 2 P∞

(n) n=1 i pij

P

g 2 (j)

P

g 2 (j) πji + 2

j∈I

j∈I

π

P

+2

j∈I,j6=i

P

P

n<m

j∈I,j6=i

P

l∈I

P

g(Xn )g(Xm )χ{m ≤ τ1 } =

l∈I

g(j)g(l) π

(n) (m−n) n<m i pij i pjl

P

g(j)g(l) πji πl (mji + mil − mjl ),

(3)

=


27

a 3.11. Lemmát használva. Tovább számolva,



τX 1 −1

πi E 

!2  g(Xn )

=

n=0

XX

I(g 2 ) + 2

g(j)g(l)πj πl (mji + mil − mjl ) − 2g(i)

j∈I l∈I

X

g(l)πl =

l∈I

I(g 2 ) − 2g(i)I(g) + 2I(g)

X

g(j)πj mji + 2I(g)

X

j∈I

g(l)πl mil −

l∈I

−2

XX

g(j)g(l)πj πl mjl .

j∈I l∈I Ha most

g = f − I(f ),

akkor

XX πi E(Vh2 ) = I (f − I(f ))2 − 2 {f (j) − I(f )}{f (l) − I(f )}πj πl mjl . j∈I l∈I A most kiszámolt képlet segítségével az i-be való visszatérési id® második momentumát is megkaphatjuk. Ehhez válasszuk a

g = 1

függvényt, a (3) egyenletb®l és a 3.11.

Lemmából :

E(τ 2 ) =

X X πj 1 +2 · i p∗jl = πi π i j∈I,j6=i l∈I " X

mii + 2mii

j∈I,j6=i

3.12. Példa.

πj

X

∗ i pjl

X

= mii + 2mii

l∈I

πj mji = mii

j∈I,j6=i

Legyen egy Markov lánc állapottere

N,

# X mji 2 −1 mjj j∈I

és a folyamat olyan, hogy

0-ból

átugrunk valamelyik állapotba, geometriai eloszlású ideig ott maradunk, majd visszaugrunk

0-ba.

Tehát :

p0j = αj , ahol

αj > 0,

P∞

pj0 = βj ,

pjj = 1 − βj , j ≥ 1,

αj = 1, 0 < βj < 1. Ez irreducibilis, aperiodikus. ha van πj stacionárius eloszlása. Az egyenletek :

j=1

pozitív rekurrens,

πj = (1 − βj )πj + αj π0 , j ≥ 1,

π0 =

∞ X j=1

βj πj ,

A lánc akkor

4. REGULÁRIS MÉRTÉK

amit a

πj =

28

αj π számok elégítenek ki. Ez akkor lehet eloszlás, ha βj 0

ekkor

π0 =

1+

1 P∞

αk k=1 βk

, πj =

P∞

αj j=1 βj

< ∞,

és

αj π0 . βj

mjj = 1/πj , (j ∈ N), másrészt nyilván ∗ miatt. Felhasználva, hogy m00 = 0 f0j (m0j +

Számoljuk ki az átlagos elérési id®ket ! Egyrészt

mj0 = 1/βj , (j ≥ 1) a + mj0 ), kapjuk, hogy m0j =

Ha most

geometriai eloszlás

m00 − mj0 = ∗ 0 f0j

j 6= k , j, k 6= 0,

1+

P∞

αk k=1 βk

αj

Most már megkaphatjuk a

0-ba

1+

k6=j

βk

.

1 1 = + βj αk

1+

X αl l6=k

!

βl

.

való visszatérési id® második momentumát :

2

E(τ ) =

∞ X j=1

m0j -t

1 1 = βj αj

!

akkor

mjk = mj0 + m0k

Mj. : ezt, és

−

X αk

αj

1 2 1+ + 2 βj βj

.

is ki lehet egyszer¶bben is számolni.

4. Reguláris mérték A (nemnegatív) reguláris mértékek a stacionárius eloszlások általánosításai. Eleget tesznek a stacionárius eloszlásra vonatkozó egyenletrendszernek, de nem követeljük meg, hogy végesek legyenek. Legyen mátrix megszorításat a

C -beli

u = uPC (u ≥ uPC , szubreguláris) függvény C -n, ha ha

tetsz®leges osztály, és jelölje

állapotokra. Legyen

u = (ui )i∈C

PC

sorvektor,

az átmenet-

v = (vi )i∈C

u reguláris (szuperreguláris, szubreguláris) mérték u ≤ uPC ). Hasonlóan, v reguláris (szuperreguláris, v = PC v (v ≥ PC v , v ≤ PC v ).

oszlopvektor. Azt mondjuk, hogy

C -n,

C


29

4.1. Reguláris függvény

4.1. Lemma.

C

Legyen

tetsz®leges osztály. Ha létezik

v = (vi )i∈C ≥ 0,

és

j ∈ C,

melyre

X

vi ≥

pik vk + pij , i ∈ C,

(4)

k∈C,k6=j

vi ≥ fij∗

akkor

minden

i ∈ C -re,

Vegyük észre, hogy ha a a

wi = vi /vj

számok (a

Bizonyítás. ≥

és a

vi = fij∗

v = (vi ) nemnegatív szuperreguláris függvény, és vj > 0, akkor j állapottal) kielégítik a (4) rendszert. (1)

vi ≥ pij = fij . Indukcióval megmutatjuk, n-re. Legyen most m ≥ 1, és i ∈ C . Az

(4) szerint

(m) minden m=1 fij

Pn

egyenl®séggel teljesíti (4)-et.

(m+1)

fij

X

=

hogy

vi ≥

(m)

pik fkj

k∈C,k6=j egyenl®séget felhasználva, ha az állítást

vi ≥

(1) fij

X

+

pik vk ≥

(1) fij

n-re

X

+

pik

(1) fij

+

n X

n X

(m)

fkj =

m=1

k∈C,k6=j

k∈C,k6=j

már tudjuk, akkor

X

(m) pik fkj

=

(1) fij

+

(m+1) fij

=

n+1 X

(m)

fij .

m=1

m=1

m=1 k∈C,k6=j Ezért

n X

vi ≥ fij∗ .

Másrészt,

pij +

X

∗ pik fkj = pij +

Ha

(m)

(1)

pik fkj = fij +

m=1 k∈C,k6=j

k∈C,k6=j

4.2. Tétel.

∞ X X

C

gvény konstans. Ha

∞ X

(m+1)

fij

= fij∗ , i ∈ C.

m=1

rekurrens osztály, akkor minden nemnegatív szuperreguláris füg-

C

tranziens, és

|C| ≥ 2, akkor van rajta 0 és 1 közötti nem-konstans

szuperreguláris függvény.

Bizonyítás. vi ≥

Legyen

X k∈C

v = (vi )i∈C

pik vk ≥

X k∈C

pik

nemnegatív szuperreguláris függvény. Ekkor

X j∈C

pkj vj =

X j∈C

(2)

pij vj ≥ . . . ≥

X k∈C

(n)

pik vk , ∀n.


30

vk

Ebb®l látszik, hogy ha valamelyik

pozitív, akkor az összes

vi

is az. Legyen

v >0

j ∈ C -re wi = vi /vj a lemma ∗ ∗ szerinti függvény, tehát vi /vj ≥ fij . Ha C rekurrens, akkor fij = 1, ezért vi konstans. ∗ Ha most C tranziens, akkor legyen j ∈ C tetsz®leges, vj = 1, és vi = fij , ha i 6= j . A szuperreguláris. Ekkor a megjegyzés szerint tetsz®leges

lemma szerint ekkor

X

vi = fij∗ =

∗ pik fkj + pij =

k∈C,k6=j

X

pik vk ,

ha

i 6= j,

k∈C

és

∗ vj = 1 > fjj =

X

∗ pjk fkj + pjj =

k∈C,k6=j

X

pjk vk ,

ha

i = j.

k∈C

i 6= j -re fij∗ = 1

Ez a függvény nem konstans, mivel ha minden

lenne, akkor

∗ fjj =1

lenne.

4.2. Reguláris mérték Térjünk rá a reguláris mértékek vizsgálatára ! Vezessük be az tehát azt fejezi ki, hogy két

i-ben

h-ban

ehi = h p∗hi

jelölést, ez

tett látogatás között a lánc átlagosan hányszor jár

(a végpontot beleszámítva, a kezd®pontot nem). A reguláris mértékekr®l szóló

tétel el®tt bizonyítsunk be egy hasznos lemmát.

4.3. Lemma.

Legyen

C

i, j, k, l, h ∈ C

rekurrens osztály,

(n)

PN

lim Pn=0 N N →∞ n=0

pij

(n) pkl

=

tetsz®leges állapotok. Ekkor

ehj . ehl

Megjegyzések: 0 < ehi < ∞. ∗ H pij < ∞.

Feladat : mutassuk meg, hogy tetsz®leges osztályban ha

j → H (j -b®l

el lehet jutni

H -ba),

akkor

Általánosan,

Pozitív rekurrens osztályra az állítás már korábban szerepelt. Ekkor ugyanis

= mh /mi Mivel

h

és

(1/N )

(n) 0 pij

PN

→ 1/mj .

tetsz®leges lehet, és

ell = 1,

kapjuk, hogy

ehj elj = = elj , ehl ell azaz

ehj = ehl elj .

ehi =


Bizonyítás.

31

i, j

Azt már korábban láttuk, hogy tetsz®leges

állapotpárra

(n)

PN


pij

= fij∗ .

(n) pjj

(5)

Ezért, mivel az osztály rekurrens,

PN

(n)

n=0 lim PN N →∞ n=0 err®l kell belátni, hogy

elj -vel

(n)

PN

pij

=

(n)

pkl


(n)

n=0

,

pll

(n)

PN

egyenl® (ezt a

pjj

phh

taggal b®vítve kapjuk az ál-

talános eredményt). A kulcslépés egy olyan hányados határértékének meghatározása, ahol a számlálóban és a nevez®ben az els® helyen álló állapotok egyeznek meg. A (2A) alapformulából

(n)

n−1 X

(n)

plj = l plj +

(s)

(n−s)

pll l plj

,

s=1 amib®l összegzéssel

N X

(n)

plj =

N X

n=1

(n)

l plj +

n=1

Alkalmazzuk a Nörlund lemmát

N −1 X

N −s X

s=1 (n)

a0 = 0, an = pll PN

(s)

pll

(n)

n=1 lim PN N →∞ n=1

plj

(n) pll

=

(t) l plj .

t=1 ,

∗ l plj p∗ll

bn =

(t) t=1 l plj szereposztással !

Pn

+ l p∗lj .

Mivel az osztály rekurrens,

PN


(n)

plj

(n) pll

PN

=


(n)

plj

(n) pll

= l p∗lj = elj .

Ebb®l (5) által már következik az állítás.

4.4. Tétel.

C rekurrens osztály, ui = cehi , ahol h ∈ C

Legyen

talános alakja :

ekkor a nemnegatív reguláris mértékek áltetsz®leges. Másrészt, az

ui = ehi

mérték

tetsz®leges osztályon szuperreguláris, és akkor és csak akkor reguláris, ha az osztály rekurrens.


32

Megjegyzések: Rekurrens osztályban

P

i∈C

ehi = mhh ,

attól függ®en véges vagy végtelen, hogy

az osztály pozitív vagy nulla rekurrens. Pozitív rekurrens osztályban tehát nem kapunk új megoldást (itt

ehi = πi /πh ).

A multiplikatív tulajdonságból következik, hogy a különböz®

h

választásokkal

kapott mértékek csak konstans szorzóban térnek el egymástól.

Bizonyítás.

El®ször belátjuk, hogy

ui = cehi

reguláris mérték, azaz megoldása az

egyenletrendszernek. Felhasználva, hogy tetsz®leges

(n+1) h phi

X

=

C

osztályban

(n) h phk pki ,

k∈C,k6=h kapjuk, hogy

X

ehk pki =

∞ XX

(n) h phk pki

=

k∈C n=1

k∈C

∞ X X

(n) h phk pki

n=1 k∈C ∞ X (n+1) h phi n=1

+

=

(n) h phh phi

(1)

= ehi − h phi + h p∗hh phi = ehi ,

(1) mivel h phi

∗ = phi , és h p∗hh = fhh = 1. Rögtön látszik, hogy ha az osztály tranziens, akkor P ∗ fhh < 1 miatt k∈C ehk pki < ehi , azaz a mérték szuperreguláris, de nem reguláris. Másrészt, legyen most ui ≥ 0 megoldása az egyenletrendszernek. Az egyenletrendP (n) szer iterációjával ui = k∈C uk pki minden n-re, azaz a mérték vagy konstans nulla, vagy szigorúan pozitív. Ez utóbbi esetben legyen

(n)

qij = Megmutatjuk, hogy ezek egy

C -n

uj (n) p , ui ji

i, j ∈ C.

adott sztochasztikus mátrix

n-dik

hatványának ele-

mei. Ehhez azt kell látni, hogy nemnegatívak (triviális), a sorok összege

1 (a regularitás

miatt), és teljesül a Chapman-Kolmogorov egyenl®ség :

X k∈C A

qij

(n)

qik qkj =

X uk k∈C

ui

pki

uj (n) uj (n+1) (n+1) p = pji = qij . uk jk ui

átmenetvalószín¶ségekkel deniált Markov-lánc irreducibilis

C -n,

és rekurrens


(mert

(n)

(n)

qii = pii

33

). Ezért a lemma alapján

(n) n=0 qij lim PN (n) N →∞ n=0 qjj

PN

1= azaz

PN (n) pji uj uj = lim Pn=0 = eji , (n) N ui N →∞ ui pjj n=0

ui = uh ehi .

Rekurrens osztályban tehát konstans szorzó erejéig egyértelm¶en létezik nemnegatív reguláris mérték, pozitív rekurrens esetben összege véges, nulla rekurrens esetben összege végtelen. Tranziens (lényeges) osztályban véges összeg¶ reguláris mérték nincs, végtelen összeg¶ vagy van, vagy nincs.

4.5. Példa. összege is

ui = c

A

1.

P

mátrix duplán sztochasztikus, ha sztochasztikus, és az oszlopok

(Tegyük fel, hogy a hozzá tartozó Markov lánc irreducibilis.) Ekkor az

mérték reguláris.

p = 1/2, akkor a p 6= 1/2, akkor az

Az egy dimenziós egyszer¶ bolyongás átmenetmátrixa ilyen. Ha lánc rekurrens, tehát ez az egyetlen reguláris mérték. Ha viszont

ui = (p/q)i

ett®l különböz® reguláris mérték.

4.6. Példa.

Kártyakeverés : tegyük fel, hogy egy pakli kártyában

erést a lapok egy átrendezése, azaz egy

N

lap van. Egy kev-

SN -beli permutáció határoz meg. Ha egy paklit

elkezdünk keverni, az egyes keverések utáni állapotok (kártya-sorrendek) egy Markov láncot alkotnak. Tegyük fel, hogy a kever® a

π -szerinti

átrendezést (keverést)

szín¶séggel alkalmazza. Ekkor a Markov lánc átmenetvalószín¶ségei :

rπ

való-

pσρ = rρ◦σ−1 .

Ha

tehát a lánc irreducibilis, akkor stacionárius eloszlása egyenletes, aperiodikus esetben sok keverés után a pakli jól meg lesz keverve.

4.3. Megfordított láncok

4.7. Deníció.

Legyen

P

tetsz®leges átmenetmátrix, és

u pji uji elem¶

P -re a teljes állapottéren. Ekkor a qij = ugyanezen az állapottéren. Q a P u szerinti megfordítása.

mérték

4.8. Állítás.

uk > 0 (k ∈ I) reguláris Q mátrix is átmenetmátrix

A magasabbrend¶ átmenetvalószín¶ségekre igaz, hogy

(n)

qij

(n) uj . ui

= pji

A két mátrix által meghatározott Markov láncok osztályai megegyeznek, továbbá a két láncban egyszerre nulla rekurrensek, pozitív rekurrensek, vagy tranziensek. Az mérték a

Q

által meghatározott Markov láncra is reguláris.

uk


34

Az állítás bizonyítása az el®z® szakaszban szerepelt (kivéve az utolsó állítást, ami triviális). Vegyük még észre, hogy ha most kapjuk

Q-t

megfordítjuk

u

szerint, akkor vissza-

P -t.

Tegyük fel, hogy

uk > 0

stacionárius eloszlás a

P

átmenetmátrixra. (Ez akkor

lehetséges, ha a Markov láncnak minden osztálya pozitív rekurrens.) Tegyük még fel, hogy

P (X0 = k) = uk .

Ekkor

(n)

P (Xm = j|Xm+n

uj pji P (Xm = j, Xm+n = i) (n) = i) = = = qij , P (Xm+n = i) ui

N -re az Yn = XN −n (n = 0, . . . , N ) sorozat (véges) stacionárius Maralkot, uk kezdeti eloszlással, qij átmenetvalószín¶ségekkel. (Mivel a Markov

azaz minden kov láncot

tulajdonság azzal ekvivalens, hogy a jelenre nézve a múlt és a jöv® feltételesen független, az

Yn

sorozat is Markov tulajdonságú.)

Azt mondjuk, hogy az

Xn

Markov lánc megfordítható (u-ra nézve), ha megfordítása

önmaga. Tegyük most fel ismét, hogy megfordítható. Sorsoljuk ki az

ui > 0

X0

stacionárius eloszlás, és a Markov lánc

értékét az

ui

eloszlás szerint. Ezután egymástól

függetlenül indítsunk el egy-egy Markov láncot el®re és hátra

P

szerint. Ekkor egy

kétirányban végtelen stacionárius Markov láncot kapunk. Ehhez azt kell látni, hogy a Markov tulajdonság a teljes folyamatra érvényben marad (feladat : lássuk be !), valamint, hogy az átmenetvalószín¶ségeket a

(n)

pij

értékek adják. Ez utóbbi külön-külön

a két félegyenesen igaz, és

P (Xn = j|X−m

4.9. Példa.

P (X−m = i, Xn = j) = = i) = P (X−m = i)

P

k

(m) (n)

X (m) (n) uk pki pkj (n+m) = pik pkj = pij . ui k

Egyszer¶ bolyongás egy dimenzióban (jobbra

lép). Tegyük fel, hogy

p 6= 1/2.

p,

balra

q

valószín¶séggel

uk = 1 = pi−1,i = p,

Láttuk, hogy két reguláris mérték van. Ha az

qi,i+1 = pi+1,i = q , és qi,i−1 k azaz ezzel a mértékkel a lánc nem megfordítható. Az uk = (p/q) mértékkel megfordítva mérték szerint fordítjuk meg a láncot, akkor

a láncot,

qi,i+1 = és hasonlóan

qi+1,i = q ,

ui+1 p pi+1,i = q = p, ui q

azaz a lánc megfordítható.


4.10. Példa.

35

Kártyakeverés. Az

uk = 1

mértékkel megfordítva a láncot,

qσρ = pρσ = rσ◦ρ−1 = r(ρ◦σ−1 )−1 , tehát a lánc akkor megfordítható, ha

4.11. Példa.

rπ = rπ−1

minden

π -re.

Fejek száma egy dobássorozat végén (p a fej valószín¶sége). Láttuk, hogy

a Markov lánc irreducibilis, pozitív rekurrens. Hogy néz ki a megfordítása ? tehát

qk+1,k =

uk pk,k+1 = 1, uk+1

q0,k =

uk = p k q ,

uk pk,0 = pk q. u0

A lánc nyilván nem megfordítható.

4.12. Állítás.

Xn irreducibilis Markov lánc, melynek létezik egy u > 0 reguláris mértéke. Ekkor Xn pozitív reguláris függvényei kölcsönösen egyértelm¶ megfeleltetésben állnak az u szerint megfordított Yn Markov lánc pozitív reguláris függvényeivel.

Bizonyítás. mérték

Legyen

Ha

v > 0

reguláris függvény

Xn -re,

akkor

sk = u k v k

pozitív reguláris

Yn -re : X

sk qkj =

k Ugyanígy, ha

X k

uk v k

X uj pjk = uj pjk vk = uj vj = sj . uk k

s > 0 reguláris mérték Yn -re, akkor vk = sk /uk

pozitív reguláris függvény

Xn -re. Ha az irreducibilis Markov lánc rekurrens, akkor már korábban láttuk, hogy pozitív reguláris függvényei csak a konstans függvények, pozitív reguláris mértékei pedig az

ui = cehi

alakú mértékek. A fenti állítás tehát tranziens esetben érdekes.

4.13. Példa.

egyszer¶ bolyongás egy dimenzióban (jobbra

p,

balra

q

valószín¶séggel

lép). Keressük meg a pozitív reguláris függvényeket ! Láttuk, hogy ha az

uk = (p/q)k

mértékkel fordítjuk meg a láncot, akkor önmagát kapjuk. Tehát a lánc pozitív reguláris függvényei

sk = vk = uk alakúak, ahol

k

vk = (q/p)

sk

k q sk p

pozitív reguláris mérték. Ebb®l a függvények (konstans szorzó erejéig) :

, illetve

vk = 1.

5. ELNYELDÉSI VALÓSZíNSÉGEK

36

5. Elnyel®dési valószín¶ségek Legyen

Xn

C1 , C2 , . . .

Markov lánc, jelölje

a rekurrens osztályokat,

T

pedig a

tranziens állapotok unióját. Tudjuk, hogy rekurrens osztályból nem lehet kilépni, tranziensb®l pedig vagy lehet, vagy nem, aszerint, hogy az osztály lényeges-e. Egy tranziens állapotból indulva tehát vagy örökké tranziens állapotban marad a lánc, vagy elnyel®dik valamelyik rekurrens osztályba.

(n)

σi

i (tranziens) állapotból indulva, n lépés (n) (n) múlva a lánc tranziens állapotban van. Ekkor σi monoton csökken®, és limn→∞ σi = = σi annak esélye, hogy i-b®l indulva a lánc örökre tranziens állapotban marad. Minden n ≥ 0-ra igaz, hogy Jelölje

annak valószín¶ségét, hogy az

(n+1)

σi

=

X

(n+1)

pij

=

j∈T

XX

(n)

pik pkj =

j∈T k∈T

X

(n)

pik σk .

k∈T

Határértéket véve kapjuk (van szummábilis majoráns), hogy

σi =

X

i ∈ T.

pik σk

(6)

k∈T Azaz

σ

reguláris függvény a tranziens állapotok halmazán.

5.1. Állítás. Bizonyítás. ≤

(n) σi .

σ a legnagyobb nulla és egy közötti megoldása a (6) egyenletrendszernek. 0 ≤ xi ≤ 1

Ha

n = 0-ra

megoldás, akkor indukcióval megmutatható, hogy

n-re

a feltevés szerint igaz. Ha

(n+1)

σi

=

X

(n)

pik σk ≥

k∈T Ebb®l pedig határátmenettel

5.2. Állítás. jelölje

C -be

θi

Az

Xn

xi ≤

már tudjuk, akkor

X

pik xk = xi .

k∈T

xi ≤ σi .

Markov láncban legyen


nyel®dik el a lánc. Ekkor

θi

yi =

i

C

valahány rekurrens osztály uniója, és

(tranziens) állapotból indulva, el®bb-utóbb

a

X j∈T

pij yj +

X

pij ,

j∈C

egyenletrendszer minimális nemnegatív megoldása.

i∈T

(7)

5. ELNYELDÉSI VALÓSZíNSÉGEK

Bizonyítás.

Jelölje

(n)

θi

37


(i-b®l indulva). Ez a sorozat monoton növ®, határértéke

(n+1)

θi

=

X

X

pij +

j∈C

θi

amib®l határátmenettel kapjuk, hogy

yi ≥

n. lépésig beér θi . Ugyanakkor

a lánc

C -be

(n)

pij θj ,

j∈T

megoldása (7)-nek. Ha

X

yi

is megoldás, akkor

(1)

pij = θi ,

j∈C és az indukciós lépés :

(n+1)

θi

=

X

pij +

j∈C

5.3. Példa.

X

(n)

pij θj

X

≤

j∈T

pij +

j∈C

X

pij yj = yi .

j∈T

I = {0, . . . , a}. Tegyük fel, hogy a P lánc martingál, azaz E(Xn+1 |Xn ) = Xn , ami azt jelenti, hogy k kpik = i minden i-re. Legyen egy Markov lánc állapottere

Mivel

0=

a X

kp0k =

n X

k=0

p0k = 0,

ha

k ≥ 1,

azaz

lenyel®. Tegyük fel, hogy

kp0k ,

k=1

p00 = 1, a nulla elnyel® állapot. Hasonlóan az a állapot is az {1, . . . , a − 1} állapotok egy osztályt alkotnak, ez ekkor

szükségképpen tranziens (lényegtelen) osztály. Vizsgáljuk meg, mekkorák az elnyel®dési valószín¶ségek ! A martingáltulajdonság miatt

∈

(n) {1, . . . , a − 1}. Ezért lim pia

(és a komplementer

= i/a, azaz valószín¶séggel 0-ba).

P

k

(n)

kpik = i,

de

(n)

pik → 0,

ha

ekkora valószín¶séggel nyel®dik a lánc

k ∈ a-ba

Végül lássunk még egy tételt, melynek segítségével eldönthet®, hogy egy osztály rekurrens-e !

5.4. Állítás.

Legyen

Xn

irreducibilis Markov lánc. Az

i

állapot akkor és csak akkor

rekurrens, ha az

xj =

X

pjk xk

j 6= i

(8)

k6=i egyenletrendszer egyetlen nulla és egy közötti megoldása

xj = 0.

6. VÉGES ÁLLAPOTTER MARKOV LÁNCOK

Bizonyítás.

38

Készítsünk egy új Markov láncot, melyben

n¶ségek változatlanok. Ebben a láncban

i

pii = 1, és a pjk (j 6= i) valószí-

rekurrens, az összes többi állapot tranziens.

σj , ami annak σj = 1 − fji∗ . Ha

A korábbi állítás szerint (8) legnagyobb nulla és egy közötti megoldása

j -b®l indulva soha nem ér a lánc i-be, azaz ∗ ∗ ez minden j -re 0, akkor fji = 1 minden j 6= i-re, amib®l fii = 1. Fordítva, ∗ rekurrens, akkor fji = 1 minden j 6= i-re, azaz σj = 0. a valószín¶sége, hogy

ha a lánc

6. Véges állapotter¶ Markov láncok Ebben a szakaszban véges állapotter¶ Markov láncokkal foglalkozunk. Ilyenkor az átmenetmátrix egy véges, négyzetes sztochasztikus mátrix. Ezeket algebrai eszközökkel vizsgálva, újra levezethetjük a korábban kapott eredményeket, illetve megkaphatunk speciálisan erre az esetre érvényes állításokat.

6.1. Állítás.

Legyen

Xn

véges állapotter¶ Markov lánc. Ekkor (i) Minden rekurrens

osztály pozitív, (ii) minden tranziens osztály lényegtelen, és a lánc

1

valószín¶séggel

el®bb-utóbb elhagyja.

Bizonyítás.

(i) Legyen

C

rekurrens osztály. Ekkor minden

X

1=

i ∈ C -re

és

n ≥ 1-re

(n)

pij .

j∈C

Ha viszont az osztály nulla lenne, akkor

C

(n)

limn→∞ pij = 0

lenne minden

j ∈ C -re,

ami

végessége miatt ellentmond a fentieknek. (ii) Legyen

C

tranziens osztály. Minden

1=

X

i ∈ C -re

(n)

pij +

X

és

n ≥ 1-re

(n)

pij ,

j6∈C

j∈C amib®l

1=

X j∈C

(n)

lim pij + lim

n→∞

n→∞

X j6∈C

(n)

pij = lim P (Xn 6∈ C|X0 = i). n→∞

A fentiekb®l adódik, hogy ha a Markov láncirreducibilis, akkor pozitív rekurrens, valamint, hogy minden Markov láncnak van legalább egy pozitív osztálya.


A továbbiakban sajátértékét,

és

a

A

39

nemnegatív elem¶, négyzetes mátrix. A mátrix legnagyobb

hozzá

tartozó

sajátvektorokat

fogjuk

elemezni.

Összefoglalóan

nevezhetjük az itt szerepl® eredményeket Perron-Frobenius tételkörnek. Mátrixokra, illetve vektorokra a következ® jelöléseket alkalmazzuk :

≥:

> : minden koordináta nagyobb vagy egyenl®, és legalább egy koordináta nagyobb

:

minden koordináta nagyobb vagy egyenl®

minden koordináta nagyobb

6.2. Deníció.

Legyen

A ≥ 0,

ekkor

λ0 = λ0 [A] = sup{λ : ∃x > 0 : Ax ≥ λx}. A továbbiakban


1

jelöli azt a vektort, melynek minden koordinátája

1.

mini (A1)i ≤ λ0 ≤ maxi (A1)i . Legyen egyrészt

x > 0, λ

λxk ≤ (Ax)k =

X

(9)-beli pár, és

xk = maxi xi > 0.

λ ≤ maxi (A1)i .

Másrészt, a

Ekkor

akj xj ≤ xk (A1)k ≤ xk max(A1)i , i

j azaz

(9)

λ = mini (A1)i , x = 1

pár (9)-beli, hiszen minden

j -re (Ax)j = (A1)j ≥ min(A1)i = λ = λxj . i


λ0 = 0 akkor és csak akkor, ha létezik m, melyre Am = 0. (A nilpotens)

Egyrészt, ha az

x, λ

irány következik. Másrészt, tegyük fel, hogy ordinátáinak halmazát.

Cn

Am x ≥ λm x, amib®l az akkor λ0 = 0. Jelölje Cn az An 1 pozitív ko-

pár (9)-beli, akkor

nyilván csökken® halmazsorozat, megmutatjuk, hogy szig-

Cn+1 = Cn 6= ∅ lenne, létezik λ > 0, melyre

orúan csökken® (legalábbis amíg nem üres). Ha ugyanis

An 1

és

An+1 1

ugyanazon koordinátái pozitívak, tehát

A(An 1) ≥ λ(An 1), és itt

An 1 > 0,

ami ellentmondás.

akkor


40

6.1. Irreducibilis, aperiodikus mátrixok

6.5. Tétel. 1.

λ0

Legyen

A 0.

Ekkor

egyszeres sajátérték, melyhez tartozik

x0 0

2. Minden más sajátérték abszolút értéke kisebb

Bizonyítás. 0

sajátvektor.

λ0 -nál.

1. Minden nemnegatív elem¶ mátrix esetén létezik

0

x0 > 0,

melyre

k

Ax ≥ λ0 x , ugyanis válasszunk olyan λk , x (9)-beli párokat, melyekre λk → λ0 , kxk k = 1, ekkor kiválasztható olyan kn részsorozat, melyre xkn → x0 , azaz Ax0 ≥ λ0 x0 , és x0 > 0. Tegyük most fel, hogy Ax0 > λ0 x0 , ekkor az A 0 0 0 0 mártixszal rászorozva kapnánk, hogy A(Ax ) λ0 (Ax ), és mivel Ax > 0, így 0 0 ellentmondásra jutunk, mivel λ0 növelhet® lenne. Azt kaptuk, hogy Ax = λ0 x , 0 0 és mivel Ax 0, így x 0. Rátérve a sajátérték multiplicitására, tegyük fel, 0 hogy van egy másik sajátvektor, y , melyre tehát y 6= cx semmilyen komplex c-re. Ekkor y valós és képzetes része is sajátvektor, és legalább az egyikükre igaz, hogy x0 -nak nem valós konstansszorosa. Tegyük fel tehát, hogy y valós. Ekkor létezik c valós szám, melyre y − cx0 > 0, de y − cx0 6 0. A-val rászorozva, 0 A(y − cx0 ) = λ0 y − cλ0 x0 = λ0 (y − cx0 ), ami ellentmondás. 2. Az minden nemnegatív elem¶ mátrixra igaz, hogy a sajátértékek abszolút értéke

λ0 , ugyanis Az = λz -b®l A|z| ≥ |λ| · |z|, azaz |λ| ≤ λ0 . Tegyük most fel, hogy |λ| = λ0 . Legyen δ > 0 olyan, hogy A − δI 0 maradjon, erre könnyen látszik, hogy λ0 [A − δI] = λ0 [A] − δ . Viszont λ − δ sajátértéke A − δI -nek ((A − δI)z = (λ − δ)z ), tehát az el®z®ek szerint |λ − δ| ≤ λ0 − δ . A háromszögegyenl®tlenségb®l viszont |λ| ≤ |λ − δ| + δ . Ezért λ = λ0 . legfeljebb

Miel®tt a fenti tételt általánosítanánk, lássunk be egy lemmát !

6.6. Lemma.

Egy nemnegatív elem¶

tartozhat pozitív elem¶ sajátvektor.

A mátrixnak legfeljebb egy pozitív sajátértékéhez


Bizonyítás. c > 0,

Ax = λx, Ay = µy , x, y 0, x − cy > 0, de x − cy 6 0, erre

Legyen

melyre

41

és

µ > λ > 0.

Ekkor van olyan

0 ≤ A(x − cy) = λx − cµy = λ(x − cy) − c(µ − λ)y 6≥ 0, ami ellentmondás.

6.7. Tétel. Bizonyítás.

Az el®z® tétel akkor is igaz, ha van olyan

m,

melyre

Am 0.

x0 > 0, melyre Ax0 ≥ λ0 x0 . Tegyük most 0 0 m fel, hogy Ax > λ0 x , ekkor az A 0 mártixszal rászorozva kapnánk, hogy A(Am x0 ) λ0 (Am x0 ), és mivel Am x0 > 0, így ellentmondásra jutunk, mivel λ0 m 0 m 0 m 0 0 növelhet® lenne. Ezen kívül, mivel A x = λ0 x és A x 0, így x 0. A m m m multiplicitásra rátérve, el®ször belátjuk, hogy λ0 [A ] = λ0 [A] . Legyen λ0 [A ] = = µ. Frobenius els® tétele szerint létezik z 0 0, melyre Am z 0 = µz 0 , ugyanakkor 0 0 m Am x 0 = λ m 0 x , és x 0. A lemma szerint tehát µ = λ0 . Ezután, ha Az = λ0 z , m m m m akkor A z = λ0 z , de mivel Frobenius els® tétele szerint A -nek a λ0 egyszeres 0 sajátértéke, z = cx . 1. Az el®z®ek szerint létezik

λ sajátérték, azaz Az = λz . Tudjuk már, hogy |λ| ≤ λ0 , tegyük most fel, m m m m hogy |λ| = λ0 . Mivel λ sajátértéke A -nek (z sajátvektorral), és |λ | = λ0 , m m 0 Frobenius els® tételéb®l λ = λ0 , és az egyszeresség miatt z = cx . Tehát λ = λ0 .

2. Legyen

Ezt a tételt olyan Markov láncokra alkalmazhatjuk, melyek átmenetmátrixának valamelyik hatványa pozitív elem¶. Ezek éppen az irreducibilis, aperiodikus Markov láncok. Markov láncok esetén

λ0 [P ] = 1, ezekre tehát kijött, hogy egyértelm¶en létezik

stacionárius eloszlás, mely pozitív, valamint minden szuperreguláris függvény reguláris, és konstans.

6.2. Irreducibilis, periodikus mátrixok

6.8. Tétel. m

(A )ij > 0). 1.

λ0

Legyen

A ≥ 0

irreducibilis mátrix (azaz minden

i, j -re

létezik

Ekkor

egyszeres sajátérték, melyhez tartozik

x0 0

sajátvektor.

2. Minden más sajátérték abszolút értéke kisebb vagy egyenl®, mint

λ0 .

m,

hogy


42

Eszerint a tétel el®tt elmondottak minden irreducibilis láncra is teljesülnek.

Bizonyítás.

Csak az els® állítást kell bizonyítani. Azt, hogy

λ0

sajátérték valamilyen

pozitív sajátvektorral, az eddigiekhez hasonlóan bizonyítjuk, azaz keresünk egy olyan

A-val felcserélhet®. Ebben az esetben ez a mátrix (A + + I)m , ahol m olyan, melyre (A + I)m 0 (ilyen van az irreducibilitás miatt). Ezért az Ax0 > λ0 x0 feltételezésb®l rászorzással ellentmondásra jutunk. Ha már tudjuk, hogy λ0 sajátérték x0 sajátvektorral, akkor (A + I)m x0 = (1 + λ0 )m x0 miatt x0 0. Az m m egyszeresség belátásához megint azt kell látni, hogy µ = λ0 [(A + I) ] = (1 + λ0 [A]) . m m Ezt is ugyanúgy láthatjuk be, mint korábban : (A + I) -nek mind µ, mind (1 + λ0 ) pozitív elem¶ mátrixot, mely

olyan pozitív sajátértéke, melyhez tartozik pozitív sajátvektor, ezért egyenl®ek. Ha

Az = λ0 z , akkor (A + I)m z = (1 + λ0 )m z , de mivel (1 + λ0 )m egyszeres sajátértéke (A + I)m -nek, z = cx0 . tehát

6.9. Tétel. melyekre

Legyen

Frobenius els® tétele szerint

A ≥ 0 irreducibilis, d periódusú mátrix. Ekkor A azon sajátértékei,

|λ| = λ0 : λk = λ0 exp{2πik/d}, k = 0, . . . , d − 1.

Bizonyítás. x

0

Jelölje

A legnagyobb sajátértékét λ0 , a hozzá tartozó pozitív sajátvektort

. A periódus deníciója irreducibilis mátrixra : legyen

di = lnko{n > 0 : (An )ii > 0}. A ≥ 0 irreducibilis mátrix, akkor nincs benne csupa 0 sor, ezért minden sort 1-re normálva egy Markov lánc P átmenetmátrixát kapjuk, és A-ban és P -ben pontosan ugyanHa

ott vannak pozitív elemek. Emiatt a Markov láncokra kapott eredmények érvényben maradnak, azaz

di = d, és a sorok/oszlopok halmaza rész-osztályokra bomlik. A sorokat

és oszlopokat egyszerre alkalmasan átrendezve (ez a sajátértékeken nem változtat), egy

d × d-s blokkmátrixot kapunk, melyben a nem-nulla blokkok : B12 , B23 , . . . , Bd−1,d , Bd,1 . Az A mátrix d-dik hatványa pedig blokkdiagonális, melynek blokkjai : Ci = Bi,i+1 Bi+1,i+2 · · · Bi+d−1,i+d , i = 1, . . . , d, ahol az indexelés modulo

d

értend®.

Korábbi eredményeink szerint a

Ci

0, ezekre i legyen y 0 a

blokkok alkalmas hatványa már

tehát alkalmazható Frobenius második tétele. Jelölje

λ0 [Ci ] = µi ,

és


43

hozzá tartozó sajátvektor. Ezekre

µi (Bi−1,i y i ) = Bi−1,i (µi y i ) = Bi−1,i Ci y i = Ci−1 (Bi−1,i y i ). Bi−1,i y i 0, amib®l µi−1 ≥ µi minden i-re, azaz µi = µ minden i-re. Legyen y 0 i d az y -kb®l összef¶zött vektor, erre A y = µy . d d Belátjuk még, hogy λ0 [A ] = µ. Ha ugyanis a λ, x párra A x ≥ λx, és x > 0, akkor i i i i az x vektort feldarabolva az x részekre, van olyan i, melyre x > 0, és Ci x ≥ λx . Tehát λ ≤ µi = µ. d 0 d 0 d Mivel A x = λ0 x , a lemmából µ = λ0 . Tegyük most fel, hogy Az = λz , és |λ| = = λ0 . Ekkor Ad z = λd z , és λd mindazon Ci blokkoknak is sajátértéke, melyekre z i-dik darabja nem azonosan nulla, legalább egy ilyen Ci biztosan van. Frobenius második d d d d tétele szerint, mivel |λ | = λ0 = λ0 [Ci ], így λ = λ0 . Azaz λ valóban csak az állításbeli Itt

alakú lehet.

λi valóban sajátérték. Tekintsük az x0 vektor feldarabolását : x0 = (x1 , . . . xd ). Ax0 = λ0 x0 miatt Bj,j+1 xj+1 = λ0 xj . Ha most tekintjük a z = = (z 1 , . . . , z d ) vektort, melyre z j = exp{2πijk/d}xj , erre Be kell még látni, hogy

Bj,j+1 z j+1 = λ0 exp{2πi(j + 1)k/d}xj = λ0 exp{2πik/d}z j = λk z j .

6.3. Konvergencia és sebessége A következ® tétel

An

viselkedésér®l szól, ha

6.10. Tétel.

Legyen

Bizonyítás.

Könnyen felírható, hogy

n → ∞.

A irreducibilis, aperiodikus mátrix, x0 illetve f 0T

λ0 sajátértékhez 0T 0 tartozó pozitív elem¶ jobb- illetve baloldali sajátvektorok úgy normálva, hogy f x = 0 0T n n = 1, és legyen R = x f . Ekkor limn→∞ A /λ0 = R.

= λ0 R .

Legyen

B = A − λ0 R ,

a

R2 = R, Rx0 = x0 , f 0T R = f 0T , AR = RA =

erre az el®z®ek szerint

n−1 n−1 X X n k n n−k n B = (A−λ0 R) = A + A (−λ0 R) =A + (−1)n−k λn0 R = An −λn0 R. k k k=0 k=0 n

n

n

An /λn0 − R = B n /λn0 , err®l kell belátni, hogy nullához tart. Jelölje egy M mátrix sperktrálrádiuszát r(M ) = max{|λ| : λ az M sajátértéke}. Megmutatjuk, hogy

Ezért


44

r(B) < λ0 . Tegyük fel ugyanis, hogy Bz = λz valamilyen λ 6= 0-ra. Mivel RB = RA − − λ0 R2 = 0, ezért 0 = RBz = λRz , azaz Rz = 0. Emiatt λz = Bz = Az , azaz λ sajátértéke A-nak. Korábbi tételeink szerint tehát |λ| ≤ λ0 . Továbbá |λ| = λ0 csak úgy 0 0 0 lehetne, hogy λ = λ0 és z = cx . Ekkor viszont Rz = cRx = cx = z 6= 0 lenne, ami ellentmondás. Jelölje ρ = r(B/λ0 ) < 1 (vegyük észre, hogy ρ ≤ λ1 /λ0 , ahol λ1 jelöli A sajátértékeinek abszolút értékei közül a második legnagyobbat). Használjuk fel azt n 1/n a tételt a spektrálrádiuszról, hogy r(M ) = limn→∞ kM k (ahol k · k tetsz®leges norma, mivel véges dimenzióban minden norma ekvivalens), ebb®l kapjuk, hogy minden

> 0-ra,

elég nagy

n-re kAn /λn0 − Rk < (ρ + )n .

Ha ezt a tételt irreducibilis, aperiodikus Markov láncra alkalmazzuk, akkor

x0 =

= 1, f 0 a stacionárius eloszlás, R pedig az a mátrix, amelynek minden sora f 0T . Ha az kM k = max |mij | normát választjuk, akkor azt kapjuk, hogy minden > 0-ra, elég nagy n-re, minden i, j -re (n) |pij − πj | ≤ (λ1 + )n . 6.4. Perron-Frobenius tétel

6.11. Tétel. (Perron-Frobenius tétel.) 1.

λ0

sajátérték, melyhez tartozik

Legyen

x0 > 0

A>0

mátrix. Ekkor

sajátvektor.

2. Minden más sajátérték abszolút értéke kisebb vagy egyenl®, mint 3. Ha

|λ| = λ0

λ0 .

λ0 η m

is sajátérték minden

a csupa egyesb®l álló mátrixot, és legyen

Aδ = A + δE 0.

sajátérték, akkor

η = λ/λ0

egységgyök, és

m-re. 4. Ha

x0 0,

Bizonyítás.

akkor

Jelölje

E

1 n

Pn

k k=1 (A/λ0 ) konvergens.

Erre

λδ = λ0 [Aδ ] = sup{λ : ∃x > 0 : Aδ x ≥ λx}, melyb®l látható, hogy

= λδ x0δ ,

λ0 = limδ→0 λδ .

Mivel létezik

x0δ 0, kx0δ k = 1,

melyre

Aδ x0δ =

konvergens részsorozatot kiválasztva kapjuk az els® állítást.

A harmadik állításhoz feltehetjük, hogy állítás szerint van

f

0

, melyre

f

0T

A=f

0T

.

λ0 = 1 (az A/λ0

mátrixra áttérve). Az els®


45

f 0 0. Legyen |λ| = 1, λ 6= 1, és Ax = λx. Ekkor egyrészt A|x| ≥ |x|. Ha A|x| > |x| lenne, akkor f 0T |x| < f 0T A|x| = f 0T |x|, ami ellentmondás, azaz A|x| = |x|. Ebb®l minden i-re Tegyük fel el®ször, hogy

X

aij |xj | = |xi | = |

j

1X aij xj |, λ j

azaz a háromszög-egyenl®tlenség egyenl®séggel teljesül. Van tehát minden

|µi | = 1

egy

szám, hogy

aij xj /λ = µi |aij xj |, ∀j Adott

i-re

i-re j -ben

(1).

összegezve kapjuk, hogy

xi = µi |xi | (2). Tekintsük az

x·µr

r ≥ 0, ahol a szorzást koordinátánként értjük. Megmutatjuk, sajátértékkel. Ha r − 1-re már tudjuk, akkor a fenti (1), (2)

vektort

hogy ez sajátérték

λr+1

egyenleteket használva

X

aij xj µrj =

j

X

λµi aij |xj |µrj =

X

λµi aij xj µr−1 = λµi λr xi µr−1 = λr+1 xi µri . j i

j

j

f 0 6 0. Tegyük fel, hogy az = (f 1T , 0). Ekkor f 0T A = f 0T miatt

Térjünk rá arra az esetre, amikor pozitív, a többi nulla, azaz

f

0T

A= sajátértékeinek halmaza az

l

A1

r

koordináta

!

A2 sajátérték-halmazainak uniója. 1T Tegyük fel el®ször, hogy λ0 [A1 ] = 1. Ekkor, mivel f A1 = f 1T , és f 1 0, az el®z®ek 2 2T szerint készen vagyunk. Ha viszont λ0 [A2 ] = 1, akkor A2 -re van f > 0, hogy f A2 = 2T = f , amely megint vagy 0 (ebben az esetben készen vagyunk), vagy 6 0, ebben az esetben pedig A2 tovább bontható. A negyedik állításhoz a rövidség kedvéért vezessük be a T = A/λ0 jelölést. Belátjuk, 0 n n 0 0 hogy ha x 0, akkor T egyenletesen korlátos, ugyanis T x = x szerint minden i, j -re X max x0k ≥ x0i = (T n )il x0l ≥ (T n )ij x0j ≥ (T n )ij min x0k ,

alakú, és

A

A1 0 B A2

els®

és az


azaz

(T n )ij ≤ Legyen

1 n

Tn =

Pn

k=1

max x0k . min x0k

Azt kell belátni, hogy a

Tn

operátornak létezik

T0

limesze,

T0 x = limn→∞ Tn x határérték. 1 El®ször belátjuk, hogy Im(I − T ) = {x : lim Tn x = 0}. Ugyanis Tn (I − T ) = (T − n − T n+1 ), amib®l, ha w = (I − T )v ∈ Im(I − T ), akkor Tn w = n1 (T − T n+1 )v → 0, T n egyenletes korlátossága miatt. Fordítva, tegyük fel, hogy Tn x → 0. Vegyük észre, hogy

azaz minden

x-re

T k.

46

létezik a

n n X k−1 n−1 X X 1X 1 1 k j I − Tn = (I − T ) = (I − T ) ( T ) = (I − T ) (n − j)T j . n k=1 n n j=0 k=1 j=0

x − Tn x ∈ Im(I − T ), amib®l lim(x − Tn x) = x ∈ Im(I − T ). Minden x-re {Tn x : n ≥ 1} korlátos halmaz, azaz kiválasztható bel®le konvergens részsorozat : Tn0 x → x0 . Be kell látni, hogy Tn x → x0 . Mivel x − Tn0 x ∈ Im(I − T ), x − x0 ∈ Im(I − T ), ezért Tn (x − x0 ) → 0. Kell még, hogy Tn x0 konvergens, azt látjuk be, hogy x0 xpontja T -nek, és így Tn -nek is. Ugyanis Emiatt

T x0 = lim T Tn0 x = lim(T Tn0 x − Tn0 x) + lim Tn0 x = lim(Tn0 (T − I)x) + x0 = x0 . Emiatt

Tn x

is konvergál, és

Vegyük még észre, hogy

2 és T0

= T0 . Könnyen = Im(I − T0 ).

lim Tn x = x0 . T

és

T0

T T0 = T0 T = T0 . Ezért Tn T0 = T0 Im(T0 ) = Ker(I − T ) és Ker(T0 ) = Im(I − T ) =

felcserélhet®, és

belátható, hogy

A tétel els® pontját egy Markov lánc átmenetmátrixának transzponáltjára alkalmazva kapjuk, hogy véges állapottér esetén mindig van stacionárius eloszlás (mivel van legalább egy pozitív osztály). A negyedik pont tetsz®leges Markov lánc átmenetmátrixára alkalmazható, hiszen re konvergens, azaz tetsz®leges

1 n

P (k) x0 = 1 0. Megkaptuk, hogy n1 nk=1 pij minden i, j (n) p kezdeti eloszlásra, ha qp jelöli Xn eloszlását, akkor

(n) konvergens. Az is kijött, hogy ilyen határértékként éppen a stacionárius k=1 qp

Pn

eloszlások állnak el®.

6.5. A konvergenciasebesség becslése megállási id®kkel Legyen az

Xn

eloszlását jelölje

Markov lánc irreducibilis, aperiodikus, pozitív rekurrens, stacionárius

π.

Tegyük fel, hogy a

τ

ügyes megállási id® olyan, hogy ha tudjuk,


k -adik

hogy a lánc a

47

lépésben áll meg, akkor ebben az id®pontban az eloszlása épp a

stacionárius eloszlás, azaz minden

k -ra

és minden

i

állapotra

P (Xk = i|τ = k) = πi . Legyen továbbá

6.12. Tétel. = P (Xk = i)

k · kT V

Ha

τ

a teljes variáció.

ügyes megállási id®, akkor minden

p0

kezdeti eloszlásra a

pki =

eloszlás és a stacionárius eloszlás variációs távolságára

kpk − πkT V ≤ P (τ > k).

Bizonyítás. hogy

A ⊂ I , a variációs távolság |pk (A) − π(A)| ≤ P (τ > k). Mármost Legyen

pk (A) = P (Xk ∈ A) =

X

deníciója alapján azt kell belátni,

P (Xk ∈ A, τ = j) + P (Xk ∈ A, τ > k).

j≤k

P (Xk ∈ A|τ = j) = π(A), mivel a {τ = j} feltétel mellett Xj stacionárius eloszlás, ezért k ≥ j miatt Xk eloszlása is a stacionárius

Könnyen látszik, hogy eloszlása épp a eloszlás. Ezért

pk (A) =

X

π(A)P (τ = j)+P (Xk ∈ A, τ > k) = π(A)+P (τ > k)[P (Xk ∈ A|τ > k)−π(A)].

j≤k Ebb®l azonnal következik a bizonyítandó állítás.

Nézzünk egy alkalmazást a fenti módszerre. Egy

m

lapból álló kártyapaklit úgy kev-

erünk, hogy a legfels® lapot levesszük, és belekeverjük a többi közé (azaz

m

helyre

kerülhet a levett lap). Mivel az így meghatározott irreducibilis, aperiodikus Markov lánc átmenetmátrixa duplán sztochasztikus, a stacionárius eloszlás egyenletes lesz. Megmutatjuk, hogy a stacionárius eloszlás eléréséhez

6.13. Tétel. c>0

k = m(ln m + c).

Legyen

τ

Ekkor

keverés elég.

π az egyenletes kp − πkT V ≤ e−c .

Tekintsük a mondott példát, jelölje

tetsz®leges, és

Bizonyítás.

m ln m

eloszlást. Legyen

k

az az id®pont, amikor az eredetileg legalul lév® kártyát el®ször

keverjük bele a pakliba (mivel a pakli tetejére került). Ez megállási id®, s®t, ügyes megállási id®. Ez azért igaz, mert az eredetileg legalul lév® lap alá kerül® lapok minden

7. MCMC MÓDSZEREK

48

sorrendje egyformán valószín¶. Jelölje lév® lap alá bekerül az

n-edik

τn

azt az id®pontot, amikor az eredetileg alul

lap. Ekkor

τ = τ1 + (τ2 − τ1 ) + . . . + (τ − τm−1 ), ahol a tagok függetlenek, és ugyanaz,

mint

a

τi+1 − τi ∼

kupongy¶jtési

Geo(

problémában

i+1 ). Vegyük észre, hogy m (m-féle

kupont

kell

τ

eloszlása

összegy¶jteni),

csak ott egyre több és több kísérletre van szükség az újabb féle kuponok összegy¶jtéséhez, ahogy az id® telik, míg a mi feladatunkban egyre gyorsabban fognak gy¶lni a lapok az eredetileg legalul lév® lap alatt, ahogy az id® telik. Koncentráljunk tehát a kupongy¶jtési feladatra, és legyen kupont nem szereztük be

P (τ > k) =

k

Ai

az az esemény, hogy az

i-edik

típusú

kísérlet alatt.

P (∪m i=1 Ai )

≤

m X

P (Ai ) = m(1 − 1/m)k ≤ me−k/m = e−c .

i=1 Az el®z® tétel szerint kész vagyunk.

7. MCMC módszerek Markov lánc Monte Carlo (MCMC) módszer alatt olyan eljárást értünk, amikor egy adott eloszlású valószín¶ségi változó el®állításához, vagy az eloszlás vizsgálatához Markov láncot hívunk segítségül. Ebben a szakaszban csak néhány egyszer¶ példát tekintünk át.

7.1. A Hastings-Metropolis algoritmus Tegyük fel, hogy adottak a

b1 , . . . , b m > 0

retnénk olyan valószín¶ségi változót generálni, talában nagy,

B

nehezen számolható, tehát a

Pm B = i=1 bi . Szemelyre P (X = i) = bi /B . Itt m álgeneráláshoz csak a bi számokat sze-

számok, és legyen

retnénk felhasználni. Legyen

I = {1, . . . , m},

szeretnénk ezen az állapottéren egy irreducibilis, aperi-

odikus Markov láncot deniálni, melynek stacionárius eloszlása

πi = bi /B , és átmenet-

bi számok szerepelnek. Ekkor tetsz®leges kezdeti eloszlásból futtatva a láncot, Xn eloszlása exponenciális gyorsasággal tart a πi eloszláshoz. A nagy számok PN +n 1 törvénye miatt egyszersmint E(h(X)) is becsülhet® az k=N h(Xk ) átlaggal. n mátrixában csak a

7. MCMC MÓDSZEREK

49

Vegyünk el®ször egy tetsz®leges

P

átmenetmátrixot, mellyel a Markov lánc irre-

ducibilis, és állítsuk el® bel®le a következ®

qij = αij pij ,

ha

j 6= i,

Q

átmenetmátrixot :

qii = pii +

X

(1 − αij )pij .

j6=i Itt

0 ≤ αij ≤ 1

jelöli, hogy ha

P

szerint

n¶séggel fogadjuk el. Ahhoz, hogy

Q

i-b®l j -be

lépne a lánc, azt mekkora valószí-

pij > 0 esetén i, melyre pii > 0, vagy

irreducibilis legyen, elég pl., hogy

αij > 0 teljesüljön. Az aperiodicitáshoz legyen i 6= j , melyre pij > 0, αij < 1.

elég pl., hogy legyen

Vizsgáljuk most a stacionárius eloszlást ! Az is elérhet®, hogy legyen

πi

π

πj q stacionárius eloszlással, azaz πi ji

= qij

minden

i, j -re

Q

megfordítható

(ha ez igaz, akkor

már stacionárius eloszlás). Kell tehát, hogy

πi pij αij = πj αji pji

7.1. Állítás.

A fenti egyenl®ség teljesül, ha

αij = min

Bizonyítás.

∀i 6= j.

Ha

πj pji bj pji , 1 = min ,1 , πi pij bi pij

pij = pji = 0,

ha

pij > 0. pij > 0, pji = 0, akkor legyen pl. πj pji ≤ πi pij ,

akkor az egyenl®ség teljesül. Ha

αij = 0, és az egyenl®ség megint teljesül. πj pji ekkor αij = , és αji = 1, tehát πi pij

Ha

pij , pji > 0,

akkor

πi pij αij = πj pji = πj αji pji .

α-kkal vizsgáljuk meg, mi elég az irreducibilitáshoz ! A fentiek szerint elég, hogy pij > 0 esetén pji > 0 is teljesüljön. Az aperiodikussághoz elég, hogy pii > > 0 valamilyen i-re, vagy hogy legyen i 6= j , melyre pij > 0 (és ezért pji > 0), és pji /pij 6= πi /πj . (Ezek persze nem szükséges feltételek.) A fenti konstrukció egy speciális esete az, ha a P mátrix szimmetrikus, azaz pij = pji bj is minden i, j -re. Ekkor αij = min(bj /bi , 1). Ebben az esetben egyébként az αij = bi +bj Ezekkel az

jó választás, hiszen

πi pij αij =

bi bj 1 bi bj pij = pij = πj pji αji . B bi + bj B bi + bj

7. MCMC MÓDSZEREK

7.2. Példa.

50

G gráfból szeretnénk véletlen csúcsot kiválasztani, Jelölje egy s csúcs szomszédainak halmazát N (s), ekkor

Egy (nagy) összefügg®

bs = 1 minden s csúcsra. legyen a P mátrix a véletlen bolyongást azaz

pst =

1 , |N (s)|

leíró átmenetmátrix, azaz

t ∈ N (s),

ha

és

0

egyébként.

Ez irreducibilis Markov láncot határoz meg, és aperiodikus is, ha nem minden csúcsnak ugyanannyi szomszédja van. Ha viszont minden csúcsnak ugyanannyi szomszédja van, akkor a Tehát

P

mátrix duplán sztochasztikus, azaz már

αst = min(|N (s)|/|N (t)|, 1),

ha

P

stacionárius eloszlása egyenletes.

t ∈ N (s).

Ez alkalmazható pl. arra a konkrét feladatra, amikor egy olyan

n

elem¶ véletlen

x

permutációt szeretnénk el®állítani, melyre

x ∈ Pa = {x :

n X

jxj > a}

j=1 valamilyen nagy

a

számra. Ehhez szomszédsági relációt deniálunk az ilyen permutá-

ciókon : két permutáció akkor legyen szomszédos, ha transzpozícióval kaphatók egymásból. A gráf összefügg®, mert minden permutációból el lehet jutni az cióba az inverzióban álló elemek kicserélésével (mely a

Pn

j=1

jxj

(1, . . . , n) permutá-

összeget növeli).

N (s) meghatározása nem könny¶. Könnyen látszik azonban, hogy a HastingsMetropolis algoritmus akkor is m¶ködik, ha bizonyos bi -k nullával egyenl®k. Legyen pl. b1 , . . . , bk > 0, és bk+1 = · · · = bm = 0, és indítsuk a láncot az {1, . . . , k} halmazból. Ekkor végig itt is marad a lánc, hiszen i ≤ k , j > k , pij > 0-ra αij = 0. Tehát ha mi a teljes n! csúcsú gráfnak csak a Pa részhalmazából akarunk véletlenszer¶ csúcsot Persze

választani, akkor vehetjük a

pst =

1 n , s, t ∈ Sn 2

átmenetmátrixot, és az

αst = 1, módosítást.

ha

t ∈ Pa ,

és

0

egyébként

7. MCMC MÓDSZEREK

51

7.2. Gibbs mintavételez® Az el®z® algoritmust arra a feladatra alkalmazzuk, ha egy

n

dimenziós eloszlásból

kell valószín¶ségi változót generálni, és az egydimenziós feltételes eloszlásokból könnyen tudunk generálni. Itt két

n

dimenziós vektor akkor lesz szomszédos, ha csak egy

koordinátában különböznek. Legyen tehát

f (x) = f (x1 , . . . , xn ) = cb(x) n

dimenziós eloszlás,

c-t

esetleg nem

ismerjük. M¶ködtessük a következ® átmenetvalószín¶ség¶ Markov láncot :

pxy = ha

x

és

y

1 P (Xi = yi |Xj = xj , j 6= i) n

szomszédosak, és épp az

Megmutatjuk, hogy erre már

f (x)

i.

koordinátában különböznek (egyébként nulla).

stacionárius eloszlás. Ha

x

és

y

szomszédos, és az

i.

koordinátában különböznek, akkor

f (x)pxy = f (x)

1 f (y) 1 f (x) = f (y) = f (y)pyx . n P (Xj = xj , j 6= i) n P (Xj = yj , j 6= i)

Természetesen az irreducibilitást, aperiodikusságot vizsgálni kell.

7.3. Példa.

Nézzünk egy folytonos állapotter¶ példát ! Legyen az

(X, Y, Z)

vektor

s¶r¶ségfüggvénye

f (x, y, z) = C exp{−(x + y + z + xy + xz + yz}, Szeretnénk meghatározni az generálunk egy

(Xi , Yi , Zi )

x, y, z > 0.

E(XY Z) várható értéket. Ehhez a Gibbs mintavételez®vel

mintát, majd kiszámoljuk az

n+N 1 X Xi Yi Zi N i=n+1 átlagot. A mintavételezéshez a mintának mindig csak az egyik, véletlenszer¶en választott koordinátáját változtatjuk meg, a feltételes eloszlás szerint. Például eloszlása az

(Y, Z)

párra nézve Exp(1

+ Y + Z ).

X

feltételes

52

II. rész

Folytonos paraméter Az állapottér most is diszkrét, azaz

Xt : Ω → I

valószín¶ségi változók, és

t ≥ 0

valós szám. Legyen

pij (t) = P (Xs+t = j|Xs = i),

t > 0,

s-t®l. A pij (t) értékekb®l alkotott mátrixot jelölje P (t). Ekkor minden pozitív t-re P (t) sztochasztikus mátrix, és a Markov tulajdonság miatt teljesül a Chapman-Kolmogorov összefüggés, azaz P (s + + t) = P (s)P (t). Ha adottak a P (t) mátrixokat valamilyen (0, ε) intervallumon, akkor a Chapman-Kolmogorov egyenletek miatt P (t) tetsz®leges t > 0 értékre kiszámítható. ahol az átmenetvalószín¶ség megint nem függ

Azonban most nincs legrövidebb lépésköz, ezért bonyolultabb a helyzet, mint a diszkrét paraméter esetén, ahol elegend® volt az egylépéses átmenetmátrixot megadni. Vizsgáljuk az analízis eszközeivel, milyenek lehetnek a

pij (t)

átmenetvalószín¶ség-

függvények !

8. Innitezimális generátor 1. Feltevés. 8.1. Tétel.

Minden

i, j

t 7→ pij (t)

párra a

függvény mérhet®.

P i-re és h > 0-ra ∆(t, h) = j∈I |pij (t + h) − pij (t)| t-ben monoton csökken®. (ii) h → 0 esetén ∆(t, h) → 0 a t ∈ [δ, ∞) félegyenesen egyenletesen, minden δ > 0-ra.

Bizonyítás.

(i) Minden

(i) Ha

0 < s < t,

akkor

X X X ∆(t, h) = pik (s + h)pkj (t − s) − pik (s)pkj (t − s) ≤ j k k X X |pik (s + h) − pik (s)| pkj (t − s) = ∆(s, h). j

k (ii) Másrészt, ha

0 < h ≤ δ ≤ t, ∆(t, h) ≤

akkor (i) miatt

X1Z j

δ

0

δ

|pij (u + h) − pij (u)|du,

8. INFINITEZIMÁLIS GENERÁTOR

53

amib®l

lim ∆(t, h) ≤ lim

h→0

h→0

δ

X1Z δ

j

|pij (u + h) − pij (u)|du =

X1

0

δ

j

δ

Z

|pij (u + h) − pij (u)|du

lim

h→0

0

a dominált konvegencia szerint, ugyanis van összegezhet® majoráns :

1 δ

Z 0

δ

1 |pij (u + h) − pij (u)|du ≤ δ limh→0

Ugyanakkor

Rδ

0

2 pij (u + h) + pij (u)du ≤ δ

|pij (u + h) − pij (u)|du = 0,

0

8.2. Következmény. [δ, ∞)

δ

Z

Minden

i, j ∈ I

δ>0

és

mivel az eltolás

pij (t)

esetén

Z

2δ

pij (u)du. 0

L1 -ben

folytonos.

egyenletesen folytonos a

félegyenesen.

8.3. Tétel.

Minden

Bizonyítás.

i, j -re

létezik a

Tegyük fel, hogy

lemma szerint ekkor

P

tn , t0n → 0,

uij ≤ 1.

j

limt→0 pij (t) = uij és

határérték.

pij (tn ) → uij , pij (t0n ) → u0ij .

A Fatou

Másrészt dominált konvergenciát használva

X

pij (t) = lim pij (t + tn ) = lim n→∞

n→∞

pik (t)pkj (tn ) =

X

k

pik (t)ukj .

(10)

k

Ebb®l

1=

X

pij (t) =

X

j

X

ukj .

j

k

P

ukj < 1, akkor minden i-re és minden t > 0-ra pik (t) = = 0 kell legyen, azaz ekkor u0ik = 0 minden i-re. Ha (10)-ben a Chapman-Kolmogorov 0 egyenletet fordítva írjuk fel, és a tn sorozatra, akkor nem hivatkozhatunk a dominált Ezért, ha valamely

k -ra

pik (t)

j

konvergenciára, viszont a Fatou lemmából kapjuk, hogy

pij (t) ≥

X

u0ik pkj (t).

k Írjunk most

t

helyébe

tn -et,

és tartson

uij ≥ lim

X

n→∞

n

végtelenhez :

u0ik pkj (tn ) =

X

k

u0ik ukj ,

k

megint dominált konvergenciát használva. Hasonlóan, ha (10)-ben akkor határátmenettel

u0ij ≥

P

k

u0ik ukj .

Ezt

j -ben

t helyébe t0n -t írunk,

összegezve, a korábbi észrevételt


54

felhasználva

X

u0ij ≥

j azaz minden

j -re u0ij =

P

k

X

u0ik

X

X

j

k

u0ik ukj

ukj =

u0ik ,

k

kell teljesüljön. Ebb®l kapjuk, hogy

uij ≥ u0ij ,

és

szimmetria miatt készen vagyunk.

8.4. Deníció.

A

= δij ,

az egységmátrix.

azaz

P (0)

2. Feltevés.

P (t)

család standard, ha

limt→0 pij (t) = δij .

Legyen ekkor

pij (0) =

Mindig feltesszük, hogy a Markov láncunk átmenetvalószín¶sége standard.

8.5. Állítás.

Ha

P (t)

standard, akkor

|pij (t + h) − pij (t)| ≤ 1 − pii (h).

Bizonyítás. pij (t + h) − pij (t) =

X

pi k(h)pkj (t) − pij (t) = (pii (h) − 1)pij (t) +

k

X

pik (h)pkj (t).

k6=i

A második tagot felülr®l becsülhetjük a

X

pik (h) = 1 − pii (h)

k6=i összeggel. Tehát

|pij (t + h) − pij (t)| ≤ 1 − pii (h), mivel az abszolút értékben álló kifejezés két

8.6. Állítás.

Legyen

P

elég nagy

1 − pii (h)

pii (t) mennyiségnek esetleg +∞.

El®ször belátjuk, hogy minden

n-re

és

standard. A

deriváltja, mely nemnegatív, de

Bizonyítás.

0

közé es® tag különbsége. létezik a

t-re pii (t) > 0.

Mivel

−p0ii (0)

jobboldali

limt→0 pii (t) = 1,

a Chapman-Kolmogorov egyenl®ségb®l

pii (t) ≥ pii (t/n)n > 0. φ(t) = − log pii (t), az el®z®ek szerint ez jól deniált nemnegatív, folytonos függvény a [0, ∞) félegyenesen, és φ(0) = 0. A pii (s+t) ≥ pii (t)pii (s) Ch-K egyenl®tlenségb®l φ(s + t) ≤ φ(s) + φ(t). Legyen Legyen most

qi = sup t>0

φ(t) ≤ +∞. t


55

qi = limt→0 φ(t)/t. Legyen el®ször qi < ∞, és t0 olyan, hogy φ(t0 )/t0 > > qi − ε. Legyen most t tetsz®leges (kicsi) szám, írjuk fel t0 -t t0 = nt + δ alakban, ahol 0 ≤ δ < t. φ(t0 ) nφ(t) + φ(δ) nt φ(t) φ(δ) qi − ε < ≤ = · + . t0 t0 t0 t t0 Belátjuk, hogy

Tartson

t

nullához :

qi − ε ≤ lim inf t→0

mivel

nt/t0 → 1

és

φ(δ)/t0 → 0.

= ∞, akkor hasonlóan látható log(1 + h) = h(1 + o(1)), qi = lim t→0


nt φ(t) φ(δ) · + t0 t t0

= lim inf t→0

φ(t) , t

limt→0 φ(t)/t = qi . Ha qi = felhasználva, hogy h → 0 esetén

Azaz megkaptuk, hogy

be az állítás. Végül

− log(1 − (1 − pii (t))) (1 − pii (t))(1 + o(1)) = lim = −p0ii (0). t→0 t t

Ha

i 6= j ,

Legyen

h-vázát : Yn = Xnh .

h

akkor a

p0ij (0)

jobboldali nemnegatív derivált létezik, és véges.

tetsz®leges, és vizsgáljuk a folytonos paraméter¶ Markov lánc

Ez diszkét paraméter¶ Markov lánc lesz, átmenetmátrixa

i-b®l j -be érünk. Ennél sz¶kebb az az esemény, hogy úgy érünk n lépés alatt i-b®l j -be, hogy j -be el®ször i-b®l lépünk (jelölje ezen lépés indexét k + 1). Felírhatjuk, hogy Tegyük fel, hogy ebben a láncban

pij (nh) ≥

n−1 X

n

P (h).

lépés alatt

(k) j pii (h)pij (h)pjj ((n

− k − 1)h).

k=0 Továbbá

pii (kh) =

(k) j pii (h)

+

k−1 X

(m)

fij (h)pji ((k − m)h).

m=1 Mivel

Pk−1

m=1

(m)

fij (h) ≤ 1,

így

(k) j pii (h)

≥ pii (kh) − max pji ((k − m)h). 1≤m≤k−1


ε>0

Ha most

x, és

t0

56

elég kicsi, akkor

max pji (t) < ε, min pii (t) > 1 − ε, min pjj (t) > 1 − ε.

0≤t≤t0 Ezért, ha

nh < t0 ,

0≤t≤t0

0≤t≤t0

akkor az összegben szerepl®

(k) j pii (h)

> 1 − 2ε,

k

értékekre

pjj ((n − k − 1)h) > 1 − ε,

amib®l

pij (nh) > (1 − 2ε)(1 − ε)

n−1 X

pij (h) ≥ (1 − 3ε)npij (h).

k=0 Átrendezve,

pij (nh) pij (h) > (1 − 3ε) . nh h Jelölje qij = lim supt→0 pij (t)/t, továbbá válasszunk egy x 0 < t < t0 végezzük el az el®z® képletben a h → 0, nh → t határátmenetet :

számot, és

pij (t) ≥ (1 − 3ε)qij . t qij < ∞

Ebb®l azonnal következik, hogy

lim inf t→0

és

pij (t) ≥ qij , t

vagyis létezik a mondott határérték. A továbbiakban használjuk a

Q.

A

Q

mátrix elnevezése : a Markov lánc innitezimális generátora.


Tartson

qij = p0ij (0) jelölést, az ezekb®l alkotott mátrix legyen

t

Minden

i-re

P

j

qij ≤ 0. X pij (t) 1 − pii (t) = . t t j:j6=i

nullához, és használjuk a Fatou lemmát :

−qii = −p0ii (0) ≥

X j:j6=i

p0ij (0) =

X j:j6=i

qij .

9. KOLMOGOROV-FÉLE DIFFERENCIÁLEGYENLETEK

57

9. Kolmogorov-féle dierenciálegyenletek A következ® kérdés, hogy a

9.1. Tétel. ciálható a

Tegyük fel, hogy

[0, ∞)

pij (t)

függvények máshol is deriválhatók-e ?

−qii < ∞

minden i-re. Ekkor

pij (t) folytonosan

dieren-

félegyenesen.

Ezt a tételt nem bizonyítjuk, a bizonyítása meglehet®sen hosszadalmas és technikás. Vázlatosan arról van szó, hogy el®ször

t pii (t) ≥ pii (t/n)n = pii (h)1/h , ahol

h = t/n.

Mivel

pii (h) = 1 − h így

pii (h)1/h → eqii .

1 − pii (h) h

Ebb®l kapjuk, hogy

= 1 − h(−qii + o(h)),

pii (t) ≥ etqii ≥ 1 + tqii .

A 8.5 Állítás miatt

kijön, hogy

|pij (t + h) − pij (t)| ≤ −hqii , pij (t) minden t-re, vagyis

Lipschitz-folytonos. Vegyük rögtön észre, hogy vagyis

i

qii = 0

esetén

pii (t) = 1

elnyel® állapot ; ez az eset triviális.

Könnyen megkapjuk, hogy

pij (t + h) − pij (t) ≥ pii (h)pij (t) − pij (t) = (pii (h) − 1)pij (t) ≥ hqii pij (t), ahol a ChapmanKolmogorov azonosságot, majd a pár sorral feljebb kiszámolt becslést használtuk. Legyen

D+ f (t) = lim inf h→0 (f (t + h) − f (t))/h

az

f

függvény alsó Dini

deriváltja. Ekkor

D+ (e−tqii pij (t)) = e−tqii (D+ pij (t) − qii pij (t)) ≥ 0. Dini tétele szerint

e−tqii pij (t)

monoton növ®, és ezért majdnem mindenütt deriválható.

Innent®l további technikai jelleg¶ meggondolásokkal adódik, hogy

pij

mindenütt de-

riválható. Ebben a szakaszben feltesszük, hogy az innitezimális generátor konzervatív, azaz

−qii < ∞

minden

i-re,

továbbá minden

i-re

P

k qik

= 0.

Láttuk, hogy létezik a

P 0 (t)

9. KOLMOGOROV-FÉLE DIFFERENCIÁLEGYENLETEK

58

derivált.

pij (t + h) =

X

pik (h)pkj (t),

k∈I átrendezve

X pik (h) X pij (t + h) − pij (t) pii (h) − 1 = pij (t) + pkj (t) → qik pkj (t), h h h k6=i k ha

h → 0,

az alábbi lemma szerint.

9.2. Lemma. h → 0,

s®t

ck (h) ≥ 0 és 0 ≤ ak ≤ 1 P k ck (h) → k ck < ∞. Ekkor Legyenek

X

ck (h)ak →

X

k

Bizonyítás.

ha

(h → 0).

c k ak

A Fatou lemma szerint

X

h→0

Másrészt, feltehetjük, hogy

h→0

k -ra ck (h) → ck ,

k

lim inf

lim sup

adottak, minden

P

X

ck (h)ak ≤

k

N X

I = N,

ck (h)ak ≥

X

k

c k ak .

k

ekkor

ck ak + lim sup h→0

k=0 ∞ X

∞ X

ck (h)ak ≤

k=N +1

ck ak + lim sup h→0

k=0 és a második tag tetsz®legesen kicsi, ha

N

∞ X

ck (h) =

k=N +1

∞ X

c k ak +

k=0

∞ X

ck ,

k=N +1

elég nagy.

Mátrix alakba írva kaptuk, hogy

P 0 (t) = QP (t) Mi történik, ha a

Kolmogorov hátrafelé (backward) egyenletei.

(0, t + h) intervallumot a (0, t) és (t, t + h) intervalumokra osztjuk

fel ?

pij (t + h) =

X k∈I

pik (t)pkj (h),

10. SZÜLETÉSI-HALÁLOZÁSI FOLYAMATOK

59

átrendezve

pkj (h) pij (t + h) − pij (t) pjj (h) − 1 X pik (t) = pij (t) + . h h h k6=j Itt már nem feltétlenül tudjuk az összegzést felcserélni a limesszel, csak ha további pkj (h) feltételeket teszünk, például azt, hogy rögzített j esetén a → qkj konvergencia h

k -ban

egyenletes. Ha most

h → 0,

P 0 (t) = P (t)Q

akkor azt kaptuk, hogy

Kolmogorov el®refelé (forward) egyenletei.

A f® kérdés az, hogy adott konzervatív

Q

mátrix esetén a Kolmogorov-féle dif-

ferenciálegyenleteknek mikor létezik megoldásuk, és a megoldás mikor egyértelm¶ (a

P (0) = I

kezdeti feltétel mellett). Miel®tt ezt tovább vizsgálnánk, nézzünk konkrét

példákat !

10. Születési-halálozási folyamatok A továbbiakban olyan folytonos paraméter¶ Markov láncokat vizsgálunk, melyek állapottere

N,

továbbá az állapot mindig csak eggyel n® vagy csökken.

10.1. A Poisson folyamat

Zi ∼ Exp(λ) független változók, i = 1,2, . . ., és Xt = max{k ≥ 0 : : i=1 Zi ≤ t}. Képzelhetjük azt, hogy id®nként valami történik, és két egymás utáni történés között exponenciális id® telik el. Ekkor Xt azt fejezi ki, hogy a [0, t] intervallumban hány történés volt. Könny¶ megmutatni, hogy Xt folytonos paraméter¶ Markov lánc az N állapottéren, mégpedig Legyenek

Pk

pij (t) = e−λt

(λt)j−i , (j − i)!

ha

j ≥ i.

t hosszú intervallumba es® történések száma Poisson(λt) eloszlású. Az így kapott P (t) átmenetmátrixokról könnyen ellen®rizhetjük, hogy P (t+s) = = P (t)P (s), és a család standard, limt→0 P (t) = I . Hogy fog kinézni az innitezimális Ez azt jelenti, hogy egy

generátor ?

1 − pii (t) 1 − e−λt = lim = λ. t→0 t→0 t t

qi = −p0ii (0) = lim


Nyilván

i>j

esetén

qij = 0,

ha pedig

60

i < j,

e−λt (λt)j−i pij (t) = lim = qij = lim t→0 t(j − i)! t→0 t

(

λ j =i+1 0 j >i+1

10.2. Születési folyamatok A Poisson folyamat enyhe általánosítása, ha a

Q

innitezimális generátorban csak

a f®átló és a fölötte lév® elemek nem nullák, azaz

qi = qi,i+1 = λi , λi

az

i

i = 0,1, . . . .

állapothoz tartozó születési intenzitás, ezekr®l feltesszük, hogy mind pozitívak.

pij (t) = 0, ha j < i. Tegyük fel, hogy X0 = 0, és legyen rn (t) = = P (Xt = n) = p0n (t), valamint r(t) = (r0 (t), r1 (t), . . .). Ismerjük r(0)-t, kérdés, hogy meg tudjuk-e határozni r(t)-t ? Tudjuk, hogy rn (t) deriválható, s®t, az általános tételb®l Feltesszük továbbá, hogy

rögtön fel is írhatnánk a deriváltat. Talán érdemes azonban közvetlenül meghatározni : nézzük a jobb oldali deriváltat, legyen el®ször

rn (t + h) =

n X

n ≥ 1:

ri (t)pin (h) = rn−1 (t)(λn−1 h + o(h)) + rn (t)(1 − λn (h) + o(h))+

i=0

+ o(h) = rn−1 (t)λn−1 h + rn (t)(1 − λn h) + o(h). Ebb®l

rn (t + h) − rn (t) = λn−1 rn−1 (t) − λn rn (t). h→0 h Ha n = 0, akkor teljesen hasonlóan kapjuk, hogy limh→0 (r0 (t+h)−r0 (t))/h = −λ0 r0 (t). A baloldali deriváltak pedig megegyeznek a jobboldaliakkal, mivel tudjuk, hogy rn (t) folytonos, ezért limh→0 rn (t − h) = rn (t). lim

A következ® rendszert kell tehát megoldanunk :

r00 (t) = −λ0 r0 (t), rn0 (t) = −λn rn (t) + λn−1 rn−1 (t), r(0) = (1,0,0, . . .). Próbáljunk rekurzívan haladni ! Az els® dierenciálegyenletnek az egyértelm¶ megoldása

r0 (t) = e−λ0 t ,


61

0 állapotban Exp(λ0 ) ideig tartózkodik = eλn t λn−1 rn−1 (t). Ennek megoldása

(ebb®l rögtön látszik, hogy a

λn t

vn (t) = e

rn (t), erre vn0 (t)

λn t

vn (t) = e

Z rn (t) = λn−1

a lánc). Legyen

t

eλn x rn−1 (x)dx,

0 azaz

−λn t

t

Z

eλn x rn−1 (x)dx.

rn (t) = λn−1 e

(11)

0 Kérdés, hogy vajon sztochasztikus mátrixot kapunk-e a megoldásból ? Nem feltétlenül !

10.1. Tétel. teljesül, ha

i-re és t > 0-ra, P∞ n=0 1/λn = ∞.

Bizonyítás. =

Minden

A bizonyítást az

P

a

j

pij (t) = 1

egyenl®ség akkor és csak akkor

i = 0 esetre végezzük el, ez nyilván elég. Legyen Sk (t) =

Pk

i=0 ri (t). Erre

Sk0 (t)

=

k X

ri0 (t) = −λk rk (t),

i=0 mivel a teleszkópos összegb®l a többi tag kiesik. Ebb®l integrálással kapjuk, hogy

Z

t

1 − Sk (t) = λk

rk (s)ds,

mivel

Sk (0) = 1.

0 Azonnal látszik, hogy

1 − Sk (t) ≥ 0,

azaz a

µ(t) = limk→∞ (1 − Sk (t))

(monotonitás

miatt létez®) határérték nemnegatív. A

µ(t) ≤ 1 − Sk (t) ≤ 1 egyenl®tlenségb®l

λ−1 k µ(t)

Z

t

rk (s)ds ≤ λ−1 k .

≤ 0

Összegezzük ezeket

0-tól n-ig : µ(t)

n X k=0

P∞

λ−1 k

Z ≤

t

Sn (s)ds ≤ 0

n X

λ−1 k .

k=0

λ−1 = ∞, akkor a baloldali egyenl®tlenségre tekintettel µ(t) = 0 minden k P −1 t-re. Fordítva, ha ∞ k=0 λk < ∞, akkor a jobboldali egyenl®tlenség miatt nem lehet µ(t) = 0 minden t-re (lásd a következ® lemmát). Ha

k=0


10.2. Lemma.

A

P

j

pij (t) = 1

62

egyenl®ség vagy minden

i

és

t > 0

esetén teljesül,

vagy egyre sem.

Bizonyítás.

Tegyük fel, hogy

P∞

j=i

pij (t) = 1,

pij (t) =

j X

és legyen

0 < s < t.

pik (s)pkj (t − s).

k=i Ebb®l összeadással

1=

∞ X j=i

pij (t) =

∞ X

pik (s)

k=i

∞ X

pkj (t − s).

j=k

1,

Mivel azt már láttuk, hogy minden sorösszeg legfeljebb

i≤k

és

s>0

továbbá

pik (s) > 0

minden

esetén, a fenti egyenl®ség csak akkor teljesülhet, ha

∞ X

pkj (t − s) = 1

és

j=k

∞ X

pik (s) = 1.

k=i

0 < s < t esetén a P (s) mátrix sztochasztikus. Mivel sztochasztikus mátrixoknak szorzata is az, ezért az állítás kiterjed minden t-re.

Tehát a

Ha a

P (t)

mátrix nem sztochasztikus, az szemléletesen azt jelenti, hogy a lánc véges

id® alatt kimegy a végtelenbe, azaz felrobban. Ezt a jelenséget kés®bb részletesebben is tárgyaljuk. Nézzük példaként a Yule-folyamatot. Ez egy populáció méretét írja le, melyben minden egyed

λ

intenzitással szaporodik. Ez azt jelenti, hogy

nincs értelme nullából indítani a folyamatot, helyette

1

λn = nλ,

ha

n ≥ 1.

Itt

egyedb®l induljunk ki ! A (11)

p1n (t) valószín¶ségek kifejezésére, melyek az el®z® tétel szerint −λt sztochasztikus mátrixot adnak majd. El®ször is, p11 (t) = e . Ha elkezdjük a rekurziót képletet használhatjuk a

kiszámolni, láthatóvá válik, hogy a megoldás

p1n (t) = e−λt (1 − e−λt )n−1 . t id® elteltével a populáció mérete Geo(e−λt ) eloszlású. Ha k egyedb®l indulunk, akkor ®k egymástól függetlenül szaporodnak, vagyis a P (t) átmenetmátrix k -adik sorában a Negbin(k, e−λt ) eloszlás jelenik meg. Azt kaptuk, hogy


63

Feladat : hogyan tudnánk számolás nélkül kihozni ezt az eredményt, felhasználva az exponenciális eloszlású minta rendezett mintájáról szóló ismereteket ?

10.3. Születési-halálozási folyamatok A

qi,i−1

Q olyan konzervatív mátrix, melyben qi,i+1 = λi > 0 a születési intenzitások, és = µi > 0 a halálozási intenzitások, qii = −(λi + µi ), és minden más elem nulla.

10.3. Tétel.

Legyen

ρ0 = 1, ρn =

Qn

i=1

λi−1 . Ha µi

∞ X

n X 1 ρn = ∞, λ k ρk n=0 k=0

akkor

Q

meghatározza a Markov láncot, azaz csak egy olyan

család van, melynek generátora

10.4. Példa. λ, µ, a > 0.

Markov-átmenet

Q. λn = nλ + a, µn = nµ,

lineáris növekedés bevándorlással. Legyen

Legyen

P (t)

M (t) = (M0 (t), M1 (t), . . .),

ahol

ahol

Mi (t) = E(X(t)|X(0) = i) =

∞ X

jpij (t)

j=0

t id® múlva várhatóan hány tagú lesz. Legyen 1 a csupa egyesb®l álló vektor, és f = (0,1,2, . . .). Ezzel a jelöléssel M (t) = P (t)f . Ha teljesülnek a Kolmogorov-féle el®re egyenletek, akkor P 0 (t) = P (t)Q, jelöli, hogy ha kezdetben

i

tagú volt a populáció, akkor

azaz

M 0 (t) = (P (t)f )0 = P 0 (t)f = P (t)Qf . Számítsuk ki

(Qf )i =

Qf i-edik

X

koordinátáját :

qij fj = µi (i − 1) − (λi + µi )i + λi (i + 1) = λi − µi = a + (λ − µ)i.

j Mátrixos alakban,

Qf = a1 + (λ − µ)f .

Kaptuk tehát, hogy

M 0 (t) = P (t)Qf = P (t)(a1 + (λ − µ)f ) = a1 + (λ − µ)M (t).

11. VISSZATÉRSÉG

64

A dierenciálegyenlet kezdeti feltétele

( M (t) =

M (0) = f ,

a megoldás pedig

at1 + f , − 1)1 + e(λ−µ)t f ,

a (e(λ−µ)t λ−µ

ha ha

λ = µ, λ 6= µ.

11. Visszatér®ség 11.1. Az állapotok osztályozása Folytonos idej¶ Markov láncoknál is mondhatjuk, hogy a mégpedig akkor, ha van

j

állapot elérhet®

i-b®l,

t ≥ 0, melyre pij (t) > 0. Két állapot akkor érintkezik, ha kölc-

sönösen elérhet®k egymásból. Ez nyilván ekvivalenciareláció, mely osztályokra bontja az állapotteret.

11.1. Lemma. pij (t) > 0

minden

Bizonyítás.

P (t) t ≥ t0 .

Ha

standard, akkor

pii (t) > 0

minden

t-re,

és

pij (t0 ) > 0

esetén

Az els® állítás már szerepelt, a második pedig triviális a

pij (t) ≥ pij (t0 )pjj (t − t0 ) > 0 egyenl®tlenség miatt. Megjegyezzük, hogy ennél több is igaz : ha minden pozitív

pij (t0 ) > 0

valamely

t0 -ra,

Ha a folytonos idej¶ Markov láncban i-b®l elérhet®

j , akkor a h > 0 számra

h-diszkretizáltjában is, minden h > 0 esetén. Fordítva, ha valamely lánc h-diszkretizáltjában i-b®l elérhet® j , akkor a folytonos idej¶ Markov

lánc

Tehát az állapotok osztályozása és lényegessége megegyezik az összes és a folytonos idej¶ láncban. Továbbá a odikus (pii (h)

pij (t) > 0

t-re.

11.2. Következmény. a

akkor

h-diszkretizáltakban

láncban is.

h-diszkretizáltban

minden állapot aperi-

> 0).

11.2. A Markov lánc trajektóriái Eddig csak a

P (t) átmenetmátrixok családjával foglalkoztunk, vizsgáljuk most meg

a Markov lánc trajektóriáit. A Kolmogorov alaptétel segítségével bizonyítható, hogy

P (t) családhoz és kezdeti eloszláshoz létezik Markov lánc (ezt nem részletezzük). továbbiakban tegyük fel, hogy I ⊂ R, az állapotok kiterjesztett valós számok.

adott A

11. VISSZATÉRSÉG

11.3. Tétel.

65

P (t) család standard. Ekkor van olyan Xt Markov lánc, melynek átmenetmátrixa P (t), és Xt sztochasztikusan folytonos, jól-szeparálható, Tegyük fel, hogy a

és mérhet®.

A tételt nem bizonyítjuk, viszont tisztázzuk a benne szerepl® fogalmakat ! Mérhet®ség alatt azt értjük, hogy az

(ω, t) 7→ Xt (ω)

hozzárendelés mérhet® (a szorzatmérték sz-

erint). A sztochasztikus folytonosság jelentése, hogy tart

t → t0

esetén

Xt

sztochasztikusan

Xt0 -hoz.

11.4. Deníció.

Az

Xt

folyamat jól-szeparálható, ha minden

R ⊂ [0, ∞) megszámlál-

N ⊂ Ω esemény, hogy a következ® teljesül : minden G nyílt intervallumra

ható s¶r¶ halmazhoz van olyan nullmérték¶ Minden

A⊂R

zárt részhalmazra és

{ω : Xt (ω) ∈ A ∀t ∈ G ∩ R} \ {ω : Xt (ω) ∈ A ∀t ∈ G} ⊂ N. Egy jól-szeparálható folyamat majdnem minden realizációja teljesül, hogy ha megszámlálható s¶r¶ halmaz, akkor

Xt (ω)

R

torlódási pontja az

{Xr (ω) : r ∈ R ∩ (t − 1/n, t + 1/n), r 6= t} halmaznak, minden

n-re.

Jelölje

Si (ω) = {t : Xt (ω) = i} i állapotban tartózkodik. Rögzített i állapotra jelölje a számegyenesen a Lebesgue-mértéket µ. Ha

azokat az id®pontokat, amikor a lánc az

ζ(t, ω) = I(Xt (ω) = i), feltesszük, hogy X0 = i, akkor legyen

Z

és

Z Z µ(Si (ω))dP =

E(µ(Si )) =

Ω

Ω

0

∞

ζ(t, ω)dµdP = Z ∞Z

Z ζ(t, ω)dP dµ =

0

11.5. Tétel.

Ha az

Xt

Ω

Markov lánc jól-szeparálható, akkor

P (Xs = i ∀0 ≤ s ≤ t|X0 = i) = e−qi t .

∞

pii (t)dt. 0

11. VISSZATÉRSÉG

Bizonyítás.

66

A feltétel miatt n

P (Xs = i ∀0 ≤ s ≤ t|X0 = i) = lim pii (t/2n )2 = eqii t . n→∞

qi = ∞ esetre is érvényes. Ha most feltesszük, hogy qi < ∞, akkor megkaptuk, hogy az i-ben való tartózkodás ideje Exp(qi ) eloszlású. Az észrevétel lehet®séget teremt arra, hogy adott Q konzervatív mátrixhoz megkonstruáljuk a minimális Markov láncot : a lánc realizációját a Z0 , Z1 , . . . iid. egységnyi paraméter¶ exponenciális változók Ez a tétel a

segítségével építjük fel. A kiinduló állapotot a kezdeti eloszlás szerint választjuk (jelölje ezt i), majd ott tartózkodunk

ideig. Ekkor átugrunk valamelyik másik állapotba,

qij /qi valószín¶séggel választjuk. Ha az n-edik ugrás után a k állapotba jutottunk, ott Zn /qk ideig tartózkodunk. Ugyanezt a konstrukciót elmondhatjuk úgy is, hogy ha egy ugrás az i állapotba vitt, akkor az összes többi állapotban azonnal ketyegni kezd egy-egy óra, a j állapot órája Exp(qij ) eloszlású id® után csörög. Amikor az els® óra megszólal, átugrunk a hozzá tartozó állapotba. A qi < ∞ feltétel méghozzá a

j

Z0 /qi

állapotot

biztosítja, hogy az esetleg végtelen sok csörgés között biztosan lesz els®.

11.3. Visszatér®ség

11.6. Tétel.

R∞ P Q mátrix esetén (i) ∃h > 0 : n pii (nh) = ∞ ⇒ 0 pii (t)dt = P = ∞ ⇒ ∀h > 0 : n pii (nh) = ∞. R∞ (ii) A Pi (µ(Si ) = ∞) valószín¶ség 0 vagy 1 aszerint, hogy pii (t)dt véges vagy 0 Konzervatív

végtelen.

Bizonyítás.

(i) Tetsz®leges

h > 0-ra

legyen

δ(h) = min0≤s≤h pii (s).

δ(h) > 0. min nh≤t≤(n+1)h Ugyanakkor, ha

pii (t) = min pii (nh + s) ≥ pii (nh)δ(h).

nh ≤ t ≤ (n + 1)h,

0≤s≤h

akkor

pii ((n + 1)h) ≥ pii (t)pii ((n + 1)h − t) ≥ pii (t)δ(h), amib®l

pii ((n + 1)h) ≥

max nh≤t≤(n+1)h

pii (t)δ(h).

Tudjuk, hogy

11. VISSZATÉRSÉG

67

Összerakva kapjuk, hogy

δ(h)h

N −1 X

Z pii (nh) ≤ 0

n=0

Nh

N 1 X pii (t)dt ≤ h pii (nh). δ(h) n=1

R∞

pii (t)dt véges, akkor E(µ(Si )) véges, tehát µ(Si ) 1 valószín¶séggel véges. Ha viszont az integrál végtelen, akkor az (i) pont szerint i rekurrens állapot az Xn diszkrét paraméter¶ Markov láncban, ezért 1 valószín¶séggel Xn = i végtelen sok n egészre. Legyen τn az i-be való n-edik visszatérés ideje az Xn láncban, és (ii) Ha

0

An = {Xt = i, τn ≤ t ≤ τn + h}, ahol

h < 1.

Mivel az

An

események függetlenek (er®s Markov tulajdonság) és valószí-

n¶ségük nullánál nagyobb konstans, 1 valószín¶séggel végtelen sok teljesül közülük.

11.7. Következmény.

Az

i állapot vagy az összes h-diszkretizáltban visszatér®, vagy

egyben sem.

A folytonos idej¶ Markov láncban azt mondjuk, hogy az

R∞ 0

i

állapot visszatér®, ha

pii (t)dt = ∞.


11.8. Tétel.

Legyen

P (t)

standard. Minden

i, j -re

létezik a

limt→∞ pij (t) = πij

határérték.

Bizonyítás.

Nézzük a lánc

h-diszkretizáltját, ebben minden állapot aperiodikus, ezért

létezik a

lim pij (nh) =

n→∞ határérték. Belátjuk, hogy hogy

t, t0 > t0

pij (t)

fij∗ (h) = πij (h) mj (h)

Cauchy sorozat, azaz minden

ε > 0

esetén van

t0 ,

esetén

|pij (t) − pij (t0 )| < ε. A 8.5 Állítás szerint

pij (t) egyenletesen folytonos, azaz létezik h, hogy |s−u| < h esetén |pij (s) − pij (u)| < ε/3.

11. VISSZATÉRSÉG

Rögzítsük ezt a

h-t,

ekkor

68

t = nh + s, t0 = n0 h + s0 ,

és

|pij (t) − pij (t0 )| ≤ |pij (t) − pij (nh)| + |pij (nh) − pij (n0 h)| + |pij (n0 h) − pij (t0 )|. n, n0 > n0 (h), akkor a középs® tag kisebb, Tehát a t0 = n0 (h)h választás megfelel®. Ha

Megkaptuk, hogy

πij (h) = πij .

ε/3,

mint

így a baloldal kisebb, mint

Tegyük most fel, hogy a folytonos idej¶ Markov lánc

irreducibilis, és rekurrens. Ekkor ez minden diszkretizáltra is teljesül, azaz minden

i, j, h

ε.

esetén. Ebb®l kapjuk, hogy az

mj (h)

fij∗ (h) = 1

átlagos visszatérési id® nem függ

h-tól ! Tehát vagy minden diszkretizált pozitív, vagy mindegyik nulla rekurrens. Pozitív rekurrens esetben tehát

lim pij (t) = πj ,

t→∞ ahol

πj

az összes diszkretizált közös stacionárius eloszlása. Hogyan tudjuk vajon a

stacionárius eloszlást a generátor mátrixból kiszámítani ? A

πi =

P

j

πj pji (t)

egyenletet átrendezve kapjuk, hogy

0 = πi (pii (t) − 1) +

X

πj pji (t),

j6=i majd

0 = πi Tegyük fel, hogy minden i-re a

pii (t) − 1 X pji (t) + πj . t t j6=i

limt→0 pji (t)/t = qji

konvergencia

j -ben

egyenletes (ezt

a feltételt már a Kolmogorov el®remen® egyenleteknél is láttuk), ekkor érvényes a

0=

X

πj qji

j

πQ = 0. Ezt az összefüggést a Kolmogorov el®re egyen0 letekb®l is megkaphatjuk, ha a P (t) = P (t)Q egyenletben t → ∞ határértéket veszünk. Megjegyezzük, hogy ha találunk olyan πi mennyiségeket, melyekre πi qij = πj qji , akkor πQ = 0. Ezt például a születési-halálozási folyamatokra felírva, πi λi = πi+1 µi+1 Qn λi−1 adódik, melynek megoldása πi = ρi π0 . (Emlékeztet® : ρ0 = 1, ρn = i=1 µi .) Q n µi Legyen most még ρ ˜0 = 1, ρ˜n = i=1 λi összefüggés, mátrix alakban

11.9. Tétel. (Karlin-McGregor tétel) atot a természetes számokon, és legyen

Tekintsünk egy születési-halálozási folyam-

λi , µi > 0

minden szóbajöv®

i-re.

12. A KOLMOGOROV-EGYENLETEK MEGOLDHATÓSÁGÁRÓL

69

(i) A Kolmogorov-egyenleteknek akkor és csak akkor létezik egyértelm¶ megoldása, ha

S=

∞ X

ρi = ∞

vagy

S˜ =

i=0

∞ X

ρ˜i = ∞.

i=0

Ebben az esetben a lánc

S = ∞ és S˜ < ∞, ˜ = ∞, (iii) nulla rekurrens, ha S = ∞ és S ˜ = ∞. (iv) pozitív rekurrens, ha S < ∞ és S (ii) tranziens, ha

11.10. Példa. (M/M/1 sor)

Egy rendszerbe

λ-Poisson

folyamat szerint érkeznek

igények, melyeket egy kiszolgáló egység szolgál ki (érkezési sorrendben). A kiszolgálási id® eloszlása Exp(µ). Ha

Xt

jelöli azt, hogy a

t

id®pontban hány igény tartózkodik a

rendszerben, születési-halálozási folyamatot kapunk, melyre digiek alapján

λ>µ

esetén a lánc tranziens,

λ=µ

λ i = λ , µi = µ.

esetben nulla rekurrens,

Az ed-

λ<µ

esetén pozitív rekurrens. Utóbbi esetben a stacionárius eloszlás

i λ λ 1− , πi = µ µ

i = 0,1, . . . .

Stacionaritás esetén a rendszerben tartózkodó igények várható száma

11.11. Példa. (M/M/∞ sor)

λ . µ−λ

Az el®z® példán annyit módosítsunk, hogy végtelen

sok kiszolgáló egység van, tehát minden beérkez® igényt azonnal elkezdhetünk kiszolgálni. Most a

λi = λ, µi = iµ

paraméterek szerepelnek a generátor mátrixban. Ez a

lánc pozitív rekurrens lesz, stacionárius eloszlása Poisson(λ/µ).

12. A Kolmogorov-egyenletek megoldhatóságáról Q konzervatív. Ebben a szakaszban megkonstruáljuk a Kolmogorov-féle egyenletek P (t) minimális megoldását. Ez olyan standard szubsztochasztikus átmenetmátrix-család lesz, mely kielégíti mindkét egyenletrendszert, továbbá ha a P (t) szubsztochasztikus család generátora szintén Q, akkor pij (t) ≥ pij (t) minden i, j, t-re. Ebb®l Legyen

az is következik, hogy ha a minimális megoldás sztochasztikus, akkor a kétféle egyenletrendszernek nincs más (szubsztochasztikus) megoldása. Nézzük példaként a születési folyamatot ! Láttuk, hogy az el®refelé egyenlet megoldása egyértelm¶. Ha

P

1 λi

= ∞,

akkor ez a megoldás sztochasztikus, és ez az egyetlen


P

megoldása mindkét egyenletrendszernek. Ha viszont

1 λi

< ∞,

70

akkor az el®refelé

egyenletek megoldása szubsztochasztikus, de a hátrafelé egyenleteknek vannak sztochasztikus megoldásaik is (melyek nem elégítik ki az el®refelé egyenleteket).

pij (t)

Szemléletesen jut a lánc

i-b®l j -be.

annak valószín¶sége lesz, hogy

Vagyis

pij (t) =

∞ X

t

id® alatt véges sok ugrással

hni

pij (t),

n=0 hni

pij (t) annak valószín¶sége, hogy t id® alatt pontosan n ugrással hni j -be. A pij (t) mennyiségek rekurzívan kaphatók (a Q mátrixból) : ahol

jut a lánc

i-b®l

h0i

pij (t) = δij e−qi t , i

hiszen nulla ugrással csak úgy juthatunk az

állapotból

j -be,

ha

i = j,

és végig

i-ben

voltunk, melynek esélye az exponenciális tartózkodási id®b®l számolható. A rekurziós képlet pedig

hn+1i pij (t)

=

k

hni

e−qi (t−s) qik pkj (s)ds,

jelöli azt az állapotot, ahová el®ször ugrott a lánc, és

ugrásnak az id®pontját. A fenti képlet gyenletet kapjuk

n

pij (t) = δij e

jelöli ennek az els®

szerinti összegzésével a következ® integrále-

+

XZ k6=i

t

e−qi (t−s) qik pkj (s)ds.

(13)

0

12.1. Tétel.

P

Bizonyítás.

A denícióból azonnal világos, hogy

n

t−s

p-ra : −qi t

Másrészt

(12)

0

k6=i ahol

t

XZ

szubsztochasztikus mátrix minden

t-re. hni

pij (t),

és így

pij (t)

nemnegatív.

szerinti indukcióval megmutatjuk, hogy

X

hni

σij (t) ≤ 1,

j hni

Pn

hmi

pij (t). Ebb®l az n → ∞ határátmenettel kapjuk, hogy

ahol

σij (t) =

≤ 1.

Az indukciót elkezdhetjük, mivel

m=0

X j

h0i

σij (t) = e−qi t ≤ 1.

P

j

pij (t) ≤


Az indukciós lépéshez el®ször fel kell írnunk a ziót :

hn+1i σij (t)

−qi t

= δij e

+

hni

σij (t)

mennyiségekre vonatkozó rekur-

t

XZ

71

hni

e−qi (t−s) qik σkj (s)ds.

0

k6=i Ezt felhasználva,

X

hn+1i σij (t)

−qi t

=e

+

j

A

P

j

hni

σkj (s) ≤ 1 X

t

XZ k6=i

e−qi (t−s) qik

0

X

hni

σkj (s)ds.

j

indukciós feltevést beírva, és az integrálást elvégezve kapjuk, hogy

hn+1i

σij

(t) ≤ e−qi t +

j

12.2. Tétel.

A

P (t)

Bizonyítás.

A

P (t)

1 1 qik (1 − e−qi t ) = e−qi t + (1 − e−qi t )qi = 1. qi qi k6=i

X

család megoldása a Kolmogorov-féle hátrafelé egyenleteknek.

családra vonatkozó (13) integrálegyenletet deriváljuk le ! Em-

lékeztet® : ha

Z F (u, v) =

v

e−qi (u−s) pkj (s)ds,

0 akkor

∂ ∂ F + F . F (t, t) = ∂u u=t,v=t ∂v u=t,v=t 0

p0ij (t)

−qi t

= −qi δij e

+

X

Z t −qi (t−s) qik pkj (t) + −qi e pkj (s)ds = 0

k6=i

= qii pij (t) +

X

qik pkj (t) =

X

k6=i (Felhasználtuk, hogy

−qi = qii .)

qik pkj (t).

k

Az összeget az egyenletes konvergencia miatt lehetett

tagonként deriválni.

12.3. Tétel.

A

Bizonyítás.

Ezt a tételt csak vázlatosan bizonyítjuk. El®ször is, fel kellene írnunk

P (t)

család megoldása a Kolmogorov-féle el®refelé egyenleteknek.

újra annak valószín¶ségét, hogy

t

id® alatt pontosan

n

ugrással jutunk

i-b®l j -be,

de


72

most aszerint bontjuk fel ezt az eseményt, hogy az utolsó ugrásnál melyik állapotból jutottunk

j -be.

Legyen tehát

(0)

pij (t) = δij e−qj t , és

(n+1) pij (t)

=

XZ k6=j

t

(n)

pik (s)qkj e−qj (t−s) ds.

0

valószín¶séget deniáltuk kétféleképp. Így letet :

−qi t

pij (t) = δij e

+

hni

(n)

Megmutatható (n szerinti indukcióval), hogy

pij (t) = pij (t), azaz tényleg ugyanazt a P (t)-re kapunk egy második integrálegyen-

XZ

t

pik (s)qkj e−qj (t−s) ds.

(14)

0

k6=j

Ezt lederiválva pont a Kolmogorov-féle el®re-egyenleteket kapjuk (illetve itt kicsit trükközni kell az összeg tagonkénti deriválásával).

12.4. Tétel.

A

P (t)

szubsztochasztikus család standard, és teljesíti a Chapman-

Kolmogorov egyenleteket.

Bizonyítás.

A család standardságát könny¶ belátni :

h0i

lim inf pii (t) ≥ lim pii (t) = 1. t→0

Azaz

limt→0 pii (t) = 1,

t→0

amib®l már következik, hogy

limt→0 pij (t) = 0,

ha

i 6= j .

A Chapman-Kolmogorov egyenletekre rátérve, azt fogjuk belátni, hogy

hni

pij (s + t) =

n X X m=0

hmi

hn−mi

pik (s)pkj

(t).

(15)

k

Vagyis aszerint bontjuk fel a baloldali valószín¶séghez tartozó eseményt, hogy az

s

id®pontban melyik állapotban van a lánc, és addig hányat ugrott. Ha a (15) egyenl®séget

n

szerint összegezzük, épp a

egyenletet kapjuk.

pij (t + s) =

P

k

pik (s)pkj (t)

Chapman-Kolmogorov


Könnyen ellen®rizhet®, hogy (15) teljesül

n+1 X X m=0

hmi

hn+1−mi

pik (s)pkj

n = 0-ra.

73

Az indukciós lépés pedig :

(t) =

k

X

h0i hn+1i pik (s)pkj (t)

+

n+1 X X Z X m=1

k

k

hm−1i

e−qi u qi` p`k

hn+1−mi

(s − u)pkj

(t)du =

0

`6=i

=

s

hn+1i e−qi s pij (t)

+

XZ

s

hni

e−qi u qi` p`j (s − u + t)du

0

`6=i

az indukciós feltétel szerint. Az els® tag másképp (az integrálban az

u

helyébe

u + s-et

írva) :

hn+1i e−qi s pij (t)

−qi s

=e

t

XZ `6=i

−qi u

e

hni qi` p`j (t

− u)du =

0

XZ `6=i

s+t

hni

e−qi u qi` p`j (t + s − u)du.

s

Ezért

n+1 X X m=0

hmi hn+1−mi pik (s)pkj (t)

`6=i

k

12.5. Tétel. generátora

=

XZ

Q.

Bizonyítás.

Legyen Ekkor

s+t

hni

hn+1i

e−qi u qi` p`j (s − u + t)du = pij

(s + t).

0

P (t) olyan szubsztochasztikus pij (t) ≥ pij (t) minden i, j, t-re.

A korábbi tételek alapján

pij (t)

p0ij (t) ≥ −qi pij (t) +

átmenetmátrix család, melynek

folytonosan dierenciálható, és

X

qik pkj (t).

(16)

k6=i Ezt ugyan csak sztochasztikus családra láttuk be, de az eredmények igazak szubsz-

P (t) szubsztochasztikus mátrix, akkor vezessünk ezt ∞ (azaz p∞∞ (t) = 1). Legyen még

tochasztikus esetben is. Ha ugyanis a be egy új, elnyel® állapotot, jelölje

pi∞ (t) = 1 −

∞ X

pij (t).

j=0 Az így kiterjesztett egyenleteket.

P (t) család már sztochasztikus, és teljesíti a Chapman-Kolmogorov


74

A (16) becslés alkalmazásával

(eqi t pij (t))0 = qi eqi t pij (t) + eqi t p0ij (t) ≥ eqi t

X

qik pkj (t),

k6=i amib®l integrálással kapjuk, hogy

qi t

e pij (t) − δij ≥

A

pij (t)

XZ k6=i

0

XZ

t

t

eqi s qik pkj (s)ds.

mennyiségre átrendezéssel a

−qi t

pij (t) ≥ e

δij +

k6=i

e−qi (t−s) qik pkj (s)ds

(17)

0

becslést kapjuk. Mivel a jobboldalon csupa nemnegatív tag áll, rögtön adódik, hogy

P hmi h0i pij (t) ≥ e−qi t δij = pij (t). Indukcióval bizonyítjuk, hogy pij (t) ≥ nm=0 pij (t) minden n-re igaz, tehát pij (t) ≥ pij (t). A (17) egyenl®tlenség jobboldalára alkalmazva az indukciós feltevést :

−qi t

pij (t) ≥ e

δij +

XZ k6=i

0

t −qi (t−s)

e

qik

n X

hmi pkj (s)ds

m=0

ahol a második lépésben el®revettük az használtuk.

=

h0i pij (t)+

n X m=0

m

hm+1i pij (t)

=

n+1 X

hmi

pij (t),

m=0

szerinti összegzést, és a (12) összefüggést

Diszkrét és folytonos paraméter Markov láncok. Csiszár Vill

Recommend Documents