Legyen adott a P átmenetvalószín¶ség mátrix és a ϕ0 kezdeti eloszlás. Kérdés, hogy miként lehetne meghatározni az egyes állapotokban való tartózkodás valószín¶ségét az n-edik lépés múlva. De niáljuk az n-lépéses átmenetvalószín¶ségeket az alábbi módon :
pn (i, j) = P (Xn = j|X0 = i) = P (Xn+k |Xk = i) , ahol az utolsó egyenl®séget a homogenitás indokolja. A teljes valószín¶ség tétele alapján ekkor X P (Xn = j) = ϕ0 (i)P (Xn = j|X0 = i) . i∈S
Megmutatjuk, hogy az n-lépéses átmenetvalószín¶ség tulajdonképpen a P n mátrix (i, j) eleme. Ez n = 1 esetén triviális. Tegyük fel most, hogy n-re is igaz. Megmutatjuk, hogy ekkor n + 1-re is teljesül : X X P (Xn+1 = j|X0 = i) = P (Xn = k|X0 = i)P (Xn+1 = j|Xn = k) = pn (i, k)p(k, j) . k∈S
k∈S
Mivel pn (i, k) a P n mátrix (i, k) eleme, ezért a mátrixszorzás szabályai miatt a kapott összeg a P n P = P n+1 mátrix (i, j) eleme. A kezdeti ϕ0 eloszlás egy N hosszúságú vektor, mely az egyes állapotokban való tartózkodás valószín¶ségeit adja meg a 0 id®pontban. Adott ϕ0 esetén n lépés múlva az eloszlás :
ϕn = ϕ0 P n .
Példa
Legyen a kétállapotú Markovláncra vonatkozó példában p = 1/4 és q = 1/6, továbbá legyen n = 6. Ekkor 6
P =
3/4 1/6
1/4 5/6
6
≈
0,424 0,576 0,384 0,616
.
Tegyük fel, hogy a telefonvonal szabad volt a 0 id®pontban. Ekkor a kezdeti eloszlás ϕ0 = [1 0]. Az n = 6 id®pontban az eloszlás tehát : 0,424 0,576 ϕ6 = ϕ0 P 6 = 1 0 = 0,424 0,576 . 0,384 0,616 Vagyis az n = 6 id®pontban a vonal kb. 0,424 valószín¶séggel lesz szabad és 0,576 valószín¶séggel lesz foglalt. Feladatok
1. Egy Markovlánc lehetséges állapotai 1,2,3. 0,2 0,2 P = 0,5 0 0,4 0,4
Átmenetvalószín¶ség mátrixa és kezdeti eloszlása az alábbi : 0,6 0,5 ϕ0 = 0,5 0,5 0 . 0,2
Határozzuk meg a 2 és 3 lépéses átmenetvalószín¶ség mátrixokat, és az alábbi valószín¶ségeket !
a) P (X1 = 2|X0 = 1)
f ) P (X2 = 3)
b) P (X3 = 2|X2 = 1)
g) P (X3 = 1)
c) P (X2 = 1|X0 = 2)
h) P (X4 = 1 vagy 2 |X2 = 2)
d) P (X4 = 1|X2 = 2)
i) P (X7 = 3, X4 = 1, X2 = 2|X0 = 2)
e) P (X3 = 2|X0 = 3)
j) P (X7 = 3, X4 = 1, X2 = 2)
Megoldás :
A két- és háromlépéses átmenetvalószín¶ségmátrixok : 0,38 0,28 0,34 0,352 P 2 = 0,30 0,30 0,40 P 3 = 0,370 0,36 0,16 0,48 0,344
a) P (X1 = 2|X0 = 1) a P mátrix (1,2) eleme, azaz 0,2.
0,212 0,436 0,220 0,410 . 0,264 0,392
b) Mivel a Markov-lánc homogén, ezért csak az számít, hogy egy lépés alatt melyik állapotból melyik állapotba vált a rendszer, de az nem, hogy mikor, ezért P (X3 = 2|X2 = 1) = P (X1 = 2|X0 = 1) = 0,2. c) A P (X2 = 1|X0 = 2) valószín¶ség a P 2 mátrix (2,1) eleme, azaz 0,5. d) P (X4 = 1|X2 = 2) = P (X2 = 1|X0 = 2) = 0,5. e) A P (X3 = 2|X0 = 3) valószín¶ség a P 3 mátrix (3,2) eleme, azaz 0,264. 3 P f ) P (X2 = 3) = P (X2 = 3|X0 = i)P (X0 = i). Itt P (X2 = 3|X0 = i) értékei a P 2 mátrix harmadik i=1
oszlopából származnak, P (X0 = i) értékei pedig ϕ0 megfelel® koordinátái. Így P (X2 = 3) = 0,34 · 0,5 + 0,40 · 0,5 + 0,48 · 0 = 0,37. Vegyük észre, hogy a kérdéses valószín¶ség tulajdonképpen a ϕ0 P 2 vektor harmadik eleme.
g) Ez pedig a ϕ0 P 3 vektor els® eleme. Hasonlóan az el®z®höz, 3 P P (X3 = 1) = P (X3 = 1|X0 = i)P (X0 = i) = 0,352 · 0,5 + 0,370 · 0,5 + 0,344 · 0 = 0,361. i=1
h) P (X4 = 1 vagy 2 |X2 = 2) = P (X4 = 1|X2 = 2) + P (X4 = 2|X2 = 2) = 0,30 + 0,30 = 0,6. i) P (X7 = 3, X4 = 1, X2 = 3|X0 = 2) = P (X7 = 3|X4 = 1) · P (X4 = 1|X2 = 3) · P (X2 = 3|X0 = 2) = = 0,436 · 0,36 · 0,40 = 0,062784. 3 P j) P (X7 = 3, X4 = 1, X2 = 3) = P (X7 = 3, X4 = 1, X2 = 3|X0 = i) · P (X0 = i) = i=1
=
3 P
P (X7 = 3|X4 = 1) · P (X4 = 1|X2 = 3) · P (X2 = 3|X0 = i) · P (X0 = i) =
i=1
= P (X7 = 3|X4 = 1) · P (X4 = 1|X2 = 3) ·
3 P
P (X2 = 3|X0 = i) · P (X0 = i) =
i=1
= P (X7 = 3|X4 = 1) · P (X4 = 1|X2 = 3) · P (X2 = 3) = 0,436 · 0,36 · 0,37 = 0,0580752. 4.2. Hosszútávú viselkedés és invariáns eloszlás
Egy véges állapotter¶ Markovlánc hosszútávú viselkedésének vizsgálata a fentiek szerint tulajdonképpen P n vizsgálatát jelenti nagy n-ek esetén. Nézzük például a kétállapotú Markovláncra vonatkozó példában az átmenetvalószín¶ség mátrixot p = 1/4 és q = 1/6 esetén : 3/4 1/4 P = . 1/6 5/6 Bármely matematikai szoftverrel (pl. Matlab, Scilab, Maple, Mathematica, stb.) könnyedén kiszámíthatjuk pl. az ezredik hatványát is, és kapjuk a következ®t : 0,4 0,6 n P ≈ . 0,4 0,6 Nézzük most az egyszer¶ sorbanállási modellre vonatkozó példát p = 1/4 és q = 1/6 esetén. Ekkor az átmenetvalószín¶ség mátrix : 3/4 1/4 0 P = 1/8 2/3 5/24 . 0 1/6 5/6 Elegend®en nagy n esetén pedig
0,182 0,364 0,455 P n ≈ 0,182 0,364 0,455 . 0,182 0,364 0,455
Láthatólag mindkét esetben létezik P n határértéke (határmátrixa) és ennek minden sora megegyezik, azaz π lim P n = Π = ... . n→∞
π
Az els® példában π = [0,4, 0,6], a másodikban pedig π = [2/11, 4/11, 5/11]. Könnyen látható, hogy ezekben az esetekben tetsz®leges ϕ0 kezdeti eloszlás esetén
lim ϕ0 P n = ϕ0 Π = π ,
n→∞
tehát a kezdeti eloszlás id®vel elveszti jelent®ségét. Legyen most π határeloszlás, azaz valamely ϕ0 kezdeti eloszlás esetén lim ϕ0 P n = π . n→∞
Ekkor
π = lim ϕ0 P n = lim ϕ0 P n+1 = lim ϕ0 P n P = πP . n→∞ n→∞ n→∞ | {z } π
A π eloszlást invariáns (vagy stacionárius, vagy egyensúlyi, vagy állandósult) eloszlásnak nevezzük, ha
π = πP . Figyeljük meg, hogy ekkor π az 1 sajátértékhez tartozó baloldali sajátvektora P -nek. Az invariáns eloszlással kapcsolatban a következ® kérdések merülnek fel : Minden P sztochasztikus mátrix esetén létezik invariáns eloszlás ? Az invariáns eloszlás egyértelm¶ ? Milyen esetekben mondhatjuk azt, hogy
lim P n = n→∞
π π .. .
,
π és így tetsz®leges ϕ0 kezdeti eloszlás esetén
lim ϕ0 P n = π ?
n→∞
Legyen P egy olyan sztochasztikus mátrix, melynek minden eleme pozitív. Ekkor a PerronFrobenius tétel alapján az 1 egyszeres sajátértéke P -nek, az 1-hez tartozó baloldali sajátvektorok között van olyan, melynek minden eleme pozitív (és így egy megfelel® konstans szorzóval valószín¶ség eloszlás készíthet® bel®le), P -nek minden más sajátértékének az abszolút értéke kisebb, mint egy. A fentekb®l következik, hogy ilyenkor az invariáns eloszlás egyértelm¶ és tetsz®leges ϕ0 kezdeti eloszlás esetén lim ϕ0 P n = π . n→∞
A sorbanállási modellnél láttuk azonban, hogy nem csak ilyen tulajdonságú sztochasztikus mátrixok esetén létezik határeloszlás. Az ottani átmenetvalószín¶ség mátrixra nem igaz, hogy minden eleme pozitív, de mégis létezik határeloszlás. Tekintsük viszont az átmenetvalószín¶ség mátrix négyzetét : 0,594 0,354 0,052 P 2 = 0,177 0,510 0,312 . 0,021 0,250 0,729 Láthatólag P 2 már kielégíti a tétel feltételeit, ebb®l következ®en az 1 egyszeres sajátértéke P 2 -nek a π invariáns eloszlással, mint a hozzá tartozó baloldali sajátvektorral, továbbá P 2 minden más sajátértékének abszolút értéke kisebb egynél. Megállapíthatjuk tehát a következ®t :
Legyen P egy sztochasztikus mátrix. Ha van olyan k ∈ N, melyre P k minden eleme pozitív, akkor létezik invariáns eloszlás,
az invariáns eloszlás egyértelem¶, a határmátrix pedig
lim P n = n→∞
π π .. .
.
π
Feladatok
1. Tekintsük az el®z® részben meghatározott átmenetvalószín¶ség mátrixokat.
a) Melyek tesznek eleget a fentebb meghatározott feltételnek ? b) Vizsgáljuk P n viselkedését nagy n-ek esetén ! c) Ahol csak tudjuk, határozzuk meg az invariáns eloszlást ! 2. Egy Markovlánc állapottere legyen S = {1,2,3}, átmenetvalószín¶ség mátrixa pedig az alábbi : 0,4 0,2 0,4 P = 0,6 0 0,4 . 0,2 0,5 0,3
a) Határozzuk meg az invariáns eloszlást ! b) Hosszú id® alatt mi a valószín¶sége, hogy a lánc az 1 állapotban lesz ? Megoldás :
a) Megoldandó a π = πP egyenlet. Koordinátánként kiírva : π1 = 0,4π1 + 0,6π2 + 0,2π3 π2 = 0,2π1 + 0,5π3 π3 = 0,4π1 + 0,4π2 + 0,3π3 Nullára rendezve és tízzel szorozva :
0 = −6π1 + 6π2 + 2π3 0 = 2π1 − 10π2 + 5π3 0 = 4π1 + 4π2 − 7π3
Az els®höz hozzáadva a második háromszorosát, továbbá a másodikhoz hozzáadva a harmadik 2,5szeresét :
0 = −24π2 + 17π3
⇒
0 = 12π1 − 12,5π3
⇒
17 π3 24 25 π1 = π3 24
π2 =
Ne felejtsük el, hogy van még egy egyenletünk : π1 + π2 + π3 = 1, hiszen π valószín¶ség eloszlás. Tehát azt kapjuk, hogy 25 17 25 17 66 1 = π1 + π2 + π3 = π3 + π3 + π3 = + + 1 π3 = π3 24 24 24 24 24 24 17 25 ⇒ π3 = ≈ 0,3636 , π1 = ≈ 0,2576 , π2 = ≈ 0,3788 . 66 66 66
b) Ezt a valószín¶séget π1 adja meg, tehát kb. 0,2576. 3. Tegyük fel, hogy a holnapi id®járás csupán a mai nap id®járásától függ. Ha ma esik az es®, akkor holnap 0,4 valószín¶séggel fog ismét esni, míg ha ma nem esik, akkor holnap 0,2 valószín¶séggel kapunk es®t.
a) Modellezzük az id®járást Markovlánc segítségével, és írjuk fel a folyamat átmenetvalószín¶ségeit ! b) Hosszú távon mekkora az es®s napok aránya ? Körülbelül mennyi az es®s napok száma egy évben ? 4. Barátn®nk (barátunk) minden egyes napon lehet vidám, átlagos hangulatú vagy szomorú. A holnapi hangulatát csak a mai hangulata befolyásolja. Ha ma vidám, akkor holnap rendre 0,4, 0,5 és 0,1 valószín¶séggel lehet vidám, átlagos vagy szomorú. Ha közepes hangulata van, akkor 0,3, 0,4 és 0,3 a megfelel® valószín¶ségek, ha pedig szomorú, akkor 0,1, 0,3 és 0,6.
a) Adjuk meg a barátn®nk (barátunk) hangulati ingadozásait leíró átmenetvalószín¶ség mátrixot ! b) Hosszú távon mennyi a vidám napok aránya? c) Feltéve, hogy ma vidám, akkor mekkora valószín¶séggel lesz holnapután is vidám ? d) Ha ma vidám, akkor mekkora valószín¶séggel lesz holnapután vidám és három nap múlva szomorú ? e) Mekkora annak a valószín¶sége, hogy a mai vidám napot három szomorú követi ? Megoldás :
a) Az állapotok sorrendje legyen vidám (1), átlagos hangulatú (2), szomorú (3). Így az átmenetvalószín¶ség mátrix : 0,4 0,5 0,1 P = 0,3 0,4 0,3 . 0,1 0,3 0,6 b) A válaszhoz meg kell határoznunk az invariáns eloszlászt (π ), azaz a π = πP egyenlet olyan megoldását keressük, melyre π1 + π2 + π3 = 1. Hasonlóan járhatunk el, mint a 2. feladatban, s így kapjuk a következ®ket : 23 21 15 ≈ 0,2542 , π2 = ≈ 0,3898 , π3 = ≈ 0,3559 . π1 = 59 59 59 15 Tehát a vidám napok aránya az összeshez viszonyítva . 59 c) A válasz formálisan a P (X2 = 1|X0 = 1) = valószín¶ség meghatározását kéri. Ehhez kell a kétlépéses átmenetvalószín¶ség mátrix : 0,32 0,43 0,25 P 2 = 0,27 0,40 0,33 . 0,19 0,35 0,46 A keresett valószín¶ség a P 2 mátrix (1,1) eleme, tehát 0,32.
d) A mai nap legyen a kezdeti (0) id®pont. Így a holnapután a 2., a három nap múlva pedig a 3. id®pillanat. P (X3 = 3 és X2 = 1|X0 = 1) = P (X3 = 3, X2 = 1|X0 = 1) = P (X3 = 3|X2 = 1) · P (X2 = 1|X0 = 1) = = 0,1 · 0,32 = 0,032. e) P (X3 = 3, X2 = 3, X1 = 3|X0 = 1) = P (X3 = 3|X2 = 3) · P (X2 = 3|X1 = 3) · P (X1 = 3|X0 = 1) = = 0,6 · 0,6 · 0,1 = 0,036. 4.3. Állapotok osztályozása
Egy Markovlánc i és j állapota kapcsolódó (jelölése : i ↔ j ), ha léteznek olyan n, m ≥ 0 egészek, melyekre teljesül pm (i, j) > 0 és pn (j, i) > 0 is. Más szavakkal két állapot kapcsolódó, ha az egyikb®l a másik pozitív valószín¶séggel elérhet®, és ez fordítva is igaz. Az így de niált ↔ reláció ekvivalencia reláció az állapottéren, azaz re exív : i ↔ i, hiszen p0 (i, i) = 1 > 0, szimmetrikus : i ↔ j -b®l a de níció alapján következik, hogy j ↔ i,
tranzitív : ha i ↔ j és j ↔ k , akkor i ↔ k . Ez is teljesül, hiszen ha pm1 (i, j) > 0 és pm2 (j, k) > 0, akkor
pm1 +m2 (i, k) = P (Xm1 +m2 = k|X0 = i) ≥ P (Xm1 +m2 = k, Xm1 = j|X0 = i) = = P (Xm1 = j|X0 = i)P (Xm1 +m2 = k|Xm1 = j) = pm1 (i, j)pm2 (j, k) > 0 , azaz pm1 +m2 (i, k) > 0. Ez az ekvivalencia reláció az állapotteret diszjunkt halmazokra osztja fel, melyeket kapcsolódó osztályoknak nevezünk. Az i és a j állapot akkor és csak akkor tartozik ugyanabba az osztályba, ha i ↔ j . Ha csak egyetlen osztály van, akkor a Markovlánc irreducibilis (felbonthatatlan), egyébként reducibilis (felbontható). Példák
1. Tekintsük a szimmetrikus véletlen bolyongást visszaver® falakkal. Könnyen látható, hogy ekkor bármely állapotból eljuthatunk bármely állapotba, tehát a lánc egyetlen osztályból áll, tehát irreducibilis. 2. Tekintsük a szimmetrikus véletlen bolyongást elnyel® falakkal. A lánc ekkor három osztályból áll : {0}, {1,2, . . . , N − 1} és {N }. Ekkor, ha a kezdeti állapot az 1,2, . . . , N − 1 állapotok valamelyike, akkor a Markovlánc 1 valószín¶séggel elhagyja ezt az osztályt és nem tér vissza. Az ilyen tulajdonságú állapotokat tranziensnek (átmenetinek) nevezzük, a többit pedig rekurrensnek (visszatér®nek). Vagyis itt az {0} és az {N } állapot rekurrens, a többi tranziens. Ha egy Markovlánc egy rekurrens osztályból indult, akkor sohasem fogja elhagyni azt az osztályt. Feladatok
1. Egy Markovlánc állapottere legyen S = {0,1,2,3,4,5}, átmenetvalószín¶ség mátrixa pedig az alábbi : 0,5 0,5 0 0 0 0 0,3 0,7 0 0 0 0 0 0 0,1 0 0,9 0 . P = 0 0,25 0,25 0,25 0,25 0 0 0 0,7 0 0,3 0 0 0,2 0 0,2 0,2 0,4
a) Melyek a kapcsolódó osztályok ? Melyek rekurrensek és melyek tranziensek ? b) Tegyük fel, hogy a lánc a 0-ból indul. Mi a valószín¶sége, hogy hosszú id® elteltével ismét a 0-ban lesz ? c) Tegyük fel, hogy a lánc az 5-b®l indul. Mi a valószín¶sége, hogy hosszú id® elteltével ismét az 5-ben lesz ? d) Módosítsuk úgy az átmenetvalószín¶ség mátrixot, hogy a lánc csak egyetlen osztályból álljon ! Megoldás :
a) A kapcsolódó osztályok : {0,1} rekurrens, {2,4} rekurrens, {3,5} tranziens. b) Az invariáns eloszlást kellene megtalálni, de tudjuk, hogy a 0-ból indultunk, továbbá azt is, hogy a 0 rekurrens állapot, ezért elegend® a {0,1} rekurrens osztály viselkedését leíró P 0 mátrixszal dolgozni. 0,5 0,5 P0 = . 0,3 0,7 Megoldandó tehát a π = πP 0 egyenlet. A megoldás : π1 = 3/8 = 0,375, c) Mivel az 5 tranziens állapot, ezért a kérdéses valószín¶ség 0. d) Itt nyilván nagyon sokféle helyes megoldás lehet. Egy viszonylag kevés 0,5 0,5 0 0 0 0 0,3 0,6 0,1 0 0 0 0 0 0,1 0 0,9 0 P = 0,25 0,25 0 0 0,25 0,25 0 0 0,6 0,1 0,3 0 0 0,2 0,1 0,2 0,2 0,3
π2 = 5/8 = 0,625. változtatást igényl® megoldás :
.
