A Markov-láncokat nagyon sok tudományágban használnak. A Markovi rendszerek a statisztikus

5. fejezet Markov-lánc

Gyakran találkozunk olyan problémákkal, hogy egy valószín½uségi változóval jellemzett mennyiség miként alakul az id½o múlásával. Például megvizsgálhatjuk, hogy egy cég piaci részesedése, vagy egy részvény árfolyama hogyan alakul az elkövetkez½o id½operiodusban. Az id½oben véletlenszer½uen változó folyamatokat sztochasztikus folyamatoknak nevezzük. Ebben a részben a sztochasztikus folyamatok egy szpeciális részterületét az úgynevezett Markov-láncokkal kapcsolatos feladatokat tárgyaljuk. A Markov-lánc egy olyan diszkrét sztochasztikus folyamatot jelent, amely Markov-tulajdonságú. Nevét egy orosz matematikusról, Andrej Markovról () kapta, aki hírnevét a tudomány ezen ágában végzett kutatásaival szerezte. Markov-tulajdonságúnak lenni röviden annyit jelent, hogy egy folyamat korábbi állapotai a kés½obbi állapotokra csak a jelen állapoton keresztül gyakorolhatnak befolyást. Adott jelen mellett, tehát a jöv½o feltételesen független a múlttól. Semmi, ami a múltban történt, nem hat, nem ad el½orejelzést a jöv½ore nézve, a jöv½oben minden lehetséges. Alapvet½o példa erre az érmedobás –ha fejet dobunk els½ore, másodikra ugyanúgy 50/50%-kal dobhatunk írást vagy fejet egyaránt. Ha pedig 100-szor dobunk fejet egymás után, akkor is ugyanannyi a valószín½usége, hogy fejet kapunk 101.-re, mint annak, hogy írást, az el½oz½oekhez hasonlóan-a múlt tehát nem jelzi el½ore a jöv½obeli eredményt. A jelen állapot az, hogy van egy érménk (nem cinkelt), fejjel és írással a két oldalán. Szabályos kereteket feltételezve semmi más nem befolyásolhatja a jöv½obeni dobás alakulását. A Markov-láncokat nagyon sok tudományágban használnak. A Markovi rendszerek a statisztikus mechanikának és a dinamikus makroökonómiának is nélkülözhetetlen eszközei. A statisztika egyes folyamatainak modellezésére is Markov-láncokat alkalmaznak. Úgyszintén hatékonyak lehetnek az állapot értékelés, és a minta felismerésben is. A világ mobil telefon rendszereinek hibaelhárítása a Viberth-algoritmustól függ, míg rejtett Markov modellek állnak a beszédfelismerés és a bioinformatika (például, a gének el½orejelzésében) illetve a tanulás egyes folyamatainak hátterében is. A Markov-láncok újabb felhasználási területe a biológiai modellezés. Kiváltképp a népesedési folyamatoké. A Leslie mátrix is egy alkalmas példa erre, annak ellenére, hogy egyes értékei nem valószín½uségek (lehetnek 1-nél is nagyobbak). Másik fontos példa a sejtek osztódása közbeni alakok modellezése. Az alakok eloszlása, hosszú ideig rejtély volt, mind addig, míg azt meg nem határozták egy egyszer½u Markov-modell segítségével. Ebben a modellben egy sejt állapota, annak oldalainak számát jelenti. A békákon, legyeken és hidrákon tapasztalati úton szerzett információk azt sug1

2

5. Markov-lánc

allják, hogy a sejt alakjának stacionárius eloszlása bizonyíthatóan minden többsejt½u állatra ugyanaz. Az emberi agy m½uködése a tanulási folyamatok során is Markov-láncokkal magyarázható. Egy honlap PageRank mutatója, amelyet a Google is használ, is Markov-lánc által van értelmezve. Markov-láncokat használunk egyes szerencsejátékok és társasjátékok modellezésére is. Markov-láncokat alkalmaznak az úgynevezett algoritmikus zenei összeállítások készítésére. Markov folyamatokat arra is használhatjuk, hogy egy minta dokumentum alapján látszólag értelmesnek t½un½o szövegeket generáljunk. Ezeket különböz½o szórakoztatási célú szoftvereknél, úgynevezett "paródia generátoroknál" használják

5.1.

Alapfogalmak

Tételezzük fel, hogy tetsz½oleges id½opontban a sztochasztikus folyamat véges számú állapotok egyikében lehet. A lehetséges állapotokat jelöljük 1; 2; :::; N -nel. Ekkor egy X1 ; X2 ; X3 ; : : : valószín½uségi változó sorozatot Markov-láncnak nevezünk, ha P (Xt+1 = it+1 jXt = it ; Xt

1

= it 1 ; :::; X1 = i1 ) = P (Xt+1 = it+1 jXt = it ) :

Az összefüggés azt állíja, hogy a t + 1 id½oponthoz tartozó állapot valószín½uségi eloszlása csak a t id½oponthoz tartozó valószín½uségi eloszlástól függ, és nem függ azoktól az állapotoktól amelyen kereszt½ul a folyamat eljutott a t id½opontbeli állapotba. A Markov-láncok típusai: Stacionárius átmenet-valószín½uség½u (homogén) Markov-láncról beszélünk, ha az átmenetvalószín½uségek nem függnek az id½ot½ol, azaz: P (Xt+1 = jjXt = i) = pij ; ahol pij olyan 0 és 1 közötti állandók, amelyre pi1 + pi2 ::: + piN = 1: m-edrend½u Markov-láncok az olyan Markov-láncok, melyekre (véges m esetén): P (Xt+1 = it+1 jXt = it ; Xt = P (Xt+1 = it+1 jXt = it ; Xt

1 1

= it 1 ; :::; X1 = i1 ) = it 1 ; :::; Xt m 1 = it

m 1)

minden t-re. Az m = 1 esetén a sztochasztikus folyamatot egyszer½u Markov-láncnak nevezzük. Mi a továbbiakban csak a stacionárius átmenet-valószín½uség½u (homogén) Markov-láncok tárgyalásával foglalkozunk. Itt a pij annak valószín½usége, hogy a folyamat egy id½operiódus alatt az i állapotból a j állapotba lép át, ezért ezeket átmenet-valószín½uségeknek nevezzük. Egy homogén Markov-lánc id½obeli viselkedését csak akkor tudjuk megadni, ha ismerjük a folyamat kezdeti eloszlását az X1 -et, és a pij értékeket összefoglaló P = (pij )i;j=1;N átmenetvalószín½uség mátrixot. 5.1. mintapélda (piaci részesedés) Egy terméket egy adott helyszínen három márkanév alatt forgalmazzák. Jelöljük ezeket A-val, B-vel és C-vel. A terméket összesen 1500-an vásárolják és ezek megoszlását a januári hónapra az alábbi táblázat tartalmazza: Cég A B C Összesen

A vásárlók megoszlása januárban Abszolut Relatív 720 48% 350 24% 430 28% 1500 100%

5. Markov-lánc

3

Egy piackutatás során felmért márkah½uséget az alábbi táblázat tartalmazza: Cég A B C

A 60% 15% 10%

B 30% 80% 40%

C 10% 5% 50%

A táblázatban feltüntetett százalékos arányokat úgy kell érteni, hogy az A márkához az eddigi A márkát vásárlók továbbra is h½uek maradnak, de a következ½o hónapban 30%-a átpártol a B márkához és 10%-a a C márkához. Úgyanígy értelmezhet½o a táblázat B illetve C sora is, amelyek szerint a következ½o id½oszakban a vásárlók 80%-a h½u marad a B-hez, 15%-a az A-hoz és 5%-a a C-hez pártol. A C márka vásárlói 50%-a h½u marad a C-hez, 10%-a az A-hoz és 40%-a pedig a B-hez pártol. a. Adjuk meg a feladat átmenet-valószín½uség mátrixát és rajzoljuk meg az átmenet-valószín½uségi gráfját. b. Határozzuk meg a február hónap eleji piaci részesedéseket. c. Hogyan alakul a piaci részesedés az elkövetkez½o egy évben? d. Határozzuk meg a piaci részesedés egyensúlyi eloszlását? e. Várhatóan mennyi id½o elteltével pártol át az egyik márka vev½oinek 1% egy másik márkára? Megoldás a. A példa márkah½uséget megadó táblázata egyben a folyamat átmenet-valószín½uségi mátrixa is, mivel megmutatja, hogy egyik hónapról a másikra milyen valószín½uséggel marad h½u egy vásárló a márkához, vagy pártol át egy másikhoz, tehát ebben az esetben az átmenetvalószín½uség mátrix: 0 1 0:6 0:3 0:1 P = @ 0:15 0:8 0:05 A 0:1 0:4 0:5 Az átmenet-valószín½uségi mátrix felépítése olyan grá¤al szemléltethet½o, amelyben minden csúcs egy-egy állapotnak feleltethet½o meg, s az (i; j) él a pij átmeneti valószín½uséget szemlélteti. Az 5.1. mintapélda átmenet-valószín½uségi gráfját tartalmazza 5.1. ábra. b. Mivel a januári piaci eloszlás Cég Q (0)

A 0:48

B 0:24

C 0:28

ezért a február elején az eloszlás így alakul: Q (1) = Q (0) P =

0:48 0:24 0:28

=

0:352 0:448 0:2

0

1 0:6 0:3 0:1 @ 0:15 0:8 0:05 A 0:1 0:4 0:5

:

Tehát február elején a piaci részesedés Cég Q (0)

A 0:352

B 0:448

C 0:2

4

5. Markov-lánc

5.1. ábra. A 5.1. mintapélda átmenet-valószín½uségi gráfja. c. Az el½obbiekben bevezetett P ámenet-valószín½uségi mátrix jól használható, ha annak a valószín½uségét akarjuk kiszámítani, hogy a folyamat az i állapotból n lépésben a j állapotba jusson. A Chapman-Kolmogorov-egyenletek szerint számíthatjuk ki ezeket az n lépéses valószín½uségeket: pij (n) =

N X

pik (t) pkj (n

t) ; minden i; j; n és 1

t

n esetén.

(5.1)

k=1

Ezek az egyenletek azt mutatják, hogy az i állapotból n lépésben a j állapoba való jutás közben a folyamat pontosan t lépés után valamely k állapotban lesz. Tehát a pik (t) pkj (n t) éppen annak a feltételes valószín½usége, hogy a folyamat az i állapotból indulva t lépés után a k állapotba jut. Sajátos esetben, ha n = 1, akkor pij (1) = pij . A pij (2) kiszámítására alkalmazzuk az (5.1) Chapman-Kolmogorov-egyenletet: pij (2) =

N X

pik pkj ,

(5.2)

k=1

azaz összeszorozzuk a P mátrix i-edik sorát a P mátrix j-edik oszlopával, tehát a pij (2) a P 2 mátrix i-edik sorának j-edik eleme. A gondolatmenetet folytatva kapjuk, hogy pij (n) = a P n mátrix i-edik sorának j-edik eleme.

(5.3)

Ha az 5.1. mintapélda átmenet-valószín½uség mátrixára alkalmazzuk a fenti összefüggést, akkor 0 1 0 1 0:6 0:3 0:1 0:6 0:3 0:1 P 2 = P P = @ 0:15 0:8 0:05 A @ 0:15 0:8 0:05 A 0:1 0:4 0:5 0:1 0:4 0:5 0 1 0:415 0:46 0:125 @ 0:215 0:705 0:08 A . = 0:17 0:55 0:28

5. Markov-lánc

5

Tehát két hónapra el½orevetítve (március elején) a márkah½uséget mutató táblázat: Cég A B C

A 41.5% 21.5% 17%

B 46% 70.5% 55%

C 12.5% 8% 28%

A gondolatmenetet folytatva, három hónapra el½orevetítve a márkah½uség alakulását az alábbi P 3 mátrix adja meg: 0 1 0 1 0:415 0:46 0:125 0:6 0:3 0:1 P 3 = P 2 P = @ 0:215 0:705 0:08 A @ 0:15 0:8 0:05 A 0:17 0:55 0:28 0:1 0:4 0:5 0 1 0:330 5 0:542 5 0:127 @ 0:242 75 0:660 5 0:096 75 A . = 0:212 5 0:603 0:184 5 Több hónapra el½orevetítve az alábbi márkah½uség (átmenet-valószín½uségi) mátrixokat kapjuk: P3

P5

P7

P9

P 11

0

0:330 5 0:542 5 @ 0:242 75 0:660 5 = 0:212 5 0:603 0 0:275 39 0:604 34 = @ 0:259 20 0:630 53 0:249 20 0:624 34 0 0:264 66 0:618 89 = @ 0:261 88 0:624 4 0:259 15 0:624 34 0 0:262 69 0:622 11 = @ 0:262 26 0:623 21 0:261 59 0:623 45 0 0:262 35 0:622 78 @ 0:262 30 0:622 99 = 0:262 14 0:623 09

1 0 1 0:127 0:292 38 0:583 95 0:123 68 0:096 75 A ; P 4 = @ 0:254 4 0:639 93 0:105 68 A 0:184 5 0:236 4 0:619 95 0:143 65 1 0 1 0:120 27 0:267 91 0:614 20 0:117 89 0:110 27 A ; P 6 = @ 0:261 12 0:626 29 0:112 58 A 0:126 46 0:255 82 0:624 82 0:119 37 1 0 1 0:116 45 0:263 28 0:621 09 0:115 63 0:113 72 A ; P 8 = @ 0:262 16 0:623 57 0:114 27 A 0:116 51 0:260 79 0:623 82 0:115 39 1 0 1 0:115 20 0:262 45 0:622 57 0:114 97 0:114 53 A ; P 10 = @ 0:262 29 0:623 06 0:114 65 A 0:114 96 0:261 97 0:623 22 0:114 81 1 0 1 0:114 86 0:262 32 0:622 88 0:114 81 0:114 71 A ; P 12 = @ 0:262 30 0:622 97 0:114 73 A 0:114 76 0:262 23 0:623 02 0:114 75

Észrevehet½o, hogy nagy n értékekre a mátrixok már nem sokat változnak és a sorokban lassan úgyanazon számokat kapjuk. Például, ha az els½o sor els½o elemét három tizedes pontossággal tekintjük, akkor az alábbi sorozatot kapjuk: n p11 (n)

1 0:6

2 0:415

3 0:330

4 0:292

5 0:275

6 0:267

7 0:264

8 0:263

9 0:262

10 0:262

11 0:262

12 0:262

Ez azt jelenti, hogy a kezdeti eloszlástól függetlenül 0:262 az esélye annak, hogy az A céghez h½u személyek hosszabb távon is h½uek maradjanak az A márkához. Most vizsgáljuk meg az 5.1. mintapélda c. alpontjában felvetett kérdést: ismerve a januári piaci eloszlást határozzuk meg, hogyan alakul a piaci részesedés az elkövetkez½o egy évben?

6

5. Markov-lánc

A b. pontban, a piaci részesedésre megadott képlet általában is igaz, azaz ha ismerjük a kezdeti id½oszakban a Q (0) eloszlást és a P valószín½uség-átmenet mátrixot, akkor az n-edik lépésben az eloszlás Q (n) = Q (0) P n : (5.4) Felhasználva a (5.4) képletet (három tizedes pontossággal) a piaci részesedésre az alábbi táblázatot kapjuk: n 0 1 2 3 4 5 6 7 8 9 10 11

A 0.48 0.352 0.298 0.276 0.268 0.264 0.263 0.262 0.262 0.262 0.262 0.262

B 0.24 0.448 0.544 0.588 0.607 0.616 0.620 0.622 0.623 0.623 0.623 0.623

C 0.28 0.2 0.158 0.136 0.125 0.120 0.117 0.116 0.115 0.115 0.115 0.115

A táblázatból kiolvasható, hogy a piaci eloszlás a nyolcadik hónap elejét½ol kezd½od½oen lényegesen nem változik. Azt lehet mondani, hogy ha a m½urkah½uség állandó, akkor hosszabb távon a piaci részesedés A: 26.2%, B: 62.3%, C: 11.5% eloszlásnál stabilizálódik. d. Ebben a mintapéldában az n-lépéses átmeneti valószín½uségek megtalálásával foglalkoztunk és megállapítottuk, hogy hosszabb távon ezen valószin½uségek alig változnak. Felvet½odik az a kérdés, hogy ez mindig így van-e? A kérdés emezéséhez szükség van néhány fogalom bevezetésére. Az i-b½ol j-be vezet½o úton olyan átmenetek sorozatát értjük, amelyek i-b½ol indulnak és j-be érkeznek, és a köztes átmenetek során minden valószín½uség pozitív. Például az 5.1. 0:1 0:3 0:05 mintapéldában 1-b½ol a 3-ba vezet½o utak (lásd a 5.1. ábrát): 1 ! 3, vagy 1 ! 2 ! 3, vagy 0:3 0:8 0:05 1 ! 2 ! 2 ! 3, stb. A nyílak feletti szám az átmenet-valószín½uségeket mutatja. A j állapotot az i állapotból elérhet½onek mondjuk, ha megadható olyan út, amely az i-b½ol indul és a j-be érkezik. Az i és j állapotok kommunikálnak egymással, ha i-b½ol elérhet½o a j és j-b½ol is elérhet½o az i. A 5.1. grafon meg…gyelhet½o, hogy minden állapot minden állapottal kommunikál, mivel az állapotok bármelyikéb½ol bármelyikbe vezet egy út. A Markov-lánc állapotainak S halmaza zárt halmaz, ha az S halmazon kívüli egyetlen állapt sem érhet½o el az S-b½ol. Ha belépünk egy zárt halmazba, akkor azt már nem tudjuk elhagyni. Az i elnyel½o állapot, ha pii = 1. Ha elnyel½o állapotba jutunk, akkor örökké ott maradunk. Minden elnyel½o állapot egyben zárt halmaz is. A mintapéldában csak az összes állapotot tartalmazó S = f1; 2; 3g halmaz zárt. Az i állapot tranziens, ha létezik olyan j állapot, amely elérhet½o az i-b½ol, de az i állapot nem érhet½o el a j-b½ol. Más szavakkal az i tranziens, ha ki lehet oly módon lépni az ib½ol, hogy soha oda vissza nem térhetünk. Ha az állapot nem tranziens, akkor visszatér½o állapotnak nevezzük. A mintapéldában minden állapot visszatér½o. Az i állapot periodikus k > 1 periódussal, ha k az a legkisebb szám, hogy az i-b½ol kilép½o lánc visszatérési idejének hossza a k egész számú többszörösse. Más szavakkal i állapot

5. Markov-lánc

7

periodikus k > 1 periódussal, ha a k az a legkisebb szám, amelyre a P k mátrix i-edik sorában minden elem nulla, kivéve a pii -t, amelynek értéke 1. A nem periodikus visszatér½o állapotot aperiodikusnak nevezzük. Másképpen megfogalmazva, egy i állapot aperiodikus, ha létezik egy olyan n szám, amelyre a P n mátrix i-dik sorának egyetlen eleme sem nulla. Ha az összes állapot visszatér½o aperiodikus, és az állapotok kommunikálnak egymással, akkor a láncot ergodikusnak mondjuk. Az 5.1. mintapélda (5.1) gráfját elemezve láthatjuk, hogy minden állapot minden állapottal komunikál, minden állapot visszatér½o (azaz bármely állapotból ha kilépünk vissza is tudunk jutni oda) és aperiodikus, mivel P mátrix egyetlen eleme sem nulla. Következésképpen a P átmenet-valószín½uség mátrix ergodikus. Tétel Ha P egy N állapotból álló ergodikus Markov-lánc átmenet-valószín½uség mátrixa, akkor létezik egy olyan x = [x1 ; x2 ; :::; xN ] vektor, hogy 0 1 x1 x2 xN B x1 x2 xN C B C lim P n = B .. .. . . .. C : n!1 @ . . . A . xN x1 x2

A Tétel azt mondja ki, hogy a P n mátrix határértéke egy olyan mátrix, amelynek sorai azonosak. Ez a tulajdonság meg…gyelhet½o az 5.1. mintapélda esetében is. Ez másképpen fogalmazva azt jelenti, hogy hosszú id½o elteltével a Markov-lánc viselkedése kiegyenlít½odik, és annak valószín½usége, hogy a rendszer valamely j állapotba lesz xj , ahol xj értéke nem függ az i kezdeti állapottól. A x = [x1 ; x2 ; :::; xN ] vektort a Markov-lánc stacionér eloszlásának vagy egyensúlyi eloszlásnak nevezzük. Ha a (5.1) Chapman-Kolmogorov-egyenletekben a t paramétert n 1-nek választjuk, akkor pij (n) =

N X

pik (n

1) pkj :

k=1

Feltételezve, hogy a P ergodikus és a fenti egyenletben határértékre térve kapjuk: lim pij (n) =

n!1

ahonnan következik, hogy

N X

pkj lim pik (n

k=1

xj =

N X

n!1

pkj xk :

1) ;

(5.5)

k=1

Mátrix jelölést használva a (5.5) a következ½o alakot ölti: x = xP:

(5.6)

Mivel x1 + x2 + ::: + xN = 1 és a xj 0 (minden j = 1; 2; :::; N esetén), ezért az ergodikus Markov-láncok esetén az egyensúlyi eloszlások az 8 N X > > > pkj xk ; ahol j = 1; 2; :::; N < xj = k=1 (5.7) > x + x + ::: + x = 1; > 1 2 N > : xj 0 minden j = 1; 2; :::; N esetén

8

5. Markov-lánc

egyenletrendszer megoldásai. Amint már megállapítottuk a P átmenet-valószín½uség mátrix ergodikus. Így alkalmazható a tétel kijelentése, azaz a folyamatnak van egyensúlyi eloszlása, ami egyben a (5.7) egyenletrendszer egyetlen megoldása. Tehát

8 x1 = 0:6x1 + 0:15x2 + 0:1x3 > > > > < x2 = 0:3x1 + 0:8x2 + 0:4x3 x3 = 0:1x1 + 0:05x2 + 0:5x3 > > x1 + x2 + x3 = 1 > > : x 1 ; x2 ; x3 0 Az egyenletrendszer megoldása: x1 = 0:262; x2 = 0:623; x3 = 0:115: Meg…gyelhet½o, hogy ez megegyezik az el½obb kiszámított hosszú távú piaci részesedéssel ( A: 26.2%, B: 62.3%, C: 11.5%). Ezek alapján azt mondhatjuk, ha a folyamatot jellemz½o valószín½uség-átmenet mátrix ergodikus, akkor a folyamat nagy számú lépés után az egyensúlyi eloszláshoz tart, függetlenül a kezdeti valószín½uség-eloszlástól. Például, az 5.1. mintapéldában ha nem a kezdeti (48%, 24%, 28%) kezdeti eloszlásból indultunk volna ki, akkor is több lépés után az ( A: 26.2%, B: 62.3%, C: 11.5%) egyensúlyi piaci részesedéshez jutottunk volna. e. Az el½oz½oekben az egyensúlyi valószín½uségek meghatározásával foglalkoztunk, azonban igen gyakran szükséges, hogy valószín½uségi kijelentést tegyünk arra vonatkozóan, hogy a folyamat az i állapotból indulva hány lépésben éri el el½oször a j állapotot. Ezt a lépésszámot (id½otartamot) a j állapot i állapotból való elérési idejének nevezzük. Ha i = j, akkor az i állapotba való visszatérési id½or½ol beszélünk. Általában az elérési id½ok valószín½uségi változók, így valószín½uségi eloszlások tartoznak hozzájuk. A továbbiakban jelölje fij (n) annak valószín½uségét, hogy az i állapotból a j állapot elérési ideje n. Kimutatható, hogy ezen valószín½uségek eleget tesznek a következ½o rekurzív összefüggéseknek:

fij (1) = pij (1) = pij ; fij (2) = pij (2) fij (1) pij fij (3) = pij (3) fij (1) pij (2) .. . fij (n) = pij (n) fij (1) pij (n

(5.8) fij (2) pij (1) 1)

fij (2) pij (n

2)

fij (n

1) pij

Ilusztrációként számítsuk ki az 5.1. mintapéldában az 1-es állapotból a 3-as állapotba való elérési id½oket az n = 1; 2; 3; 4; 5; 6 értékekre. Alkalmazzuk a (5.8) rekurzív képleteket és a

5. Markov-lánc

9

feladat P n valószín½uség-átmeneti mátrixait: f13 (1) = p13 (1) = p13 = 0:1 f13 (2) = p13 (2) f13 (1) p13 = 0:125 0:1 0:1 = 0:115 f13 (3) = p13 (3) f13 (1) p13 (2) f13 (2) p13 = 0:127 0:1 0:125 0:115 0:1 = 0:103 f13 (4) = p13 (4) f13 (1) p13 (3) f13 (2) p13 (2) f13 (3) p13 = 0:123 68 0:1 0:127 0:115 0:125 0:103 0:1 = 0:0863 f13 (5) = p13 (5) f13 (1) p13 (4) f13 (2) p13 (3) f13 (3) p13 (2) f13 (4) p13 = 0:120 27 0:1 0:123 68 0:115 0:127 0:103 0:125 0:123 68 0:1 = 0:068 f13 (6) = p13 (6) f13 (1) p13 (5) f13 (2) p13 (4) f13 (3) p13 (3) f13 (4) p13 (2) = 0:117 89 0:1 0:120 27 0:115 0:123 68 0:103 0:127 0:0863 0:125 0:068 0:1 = 0:06097

f13 (5) p13

Észrevehet½o, hogy ezek a számok mind pozitívak és az is igazolható, hogy 1 X

fij (n)

1:

n=1

Ha ez az összeg szigorúan kisebb mint 1, akkor azt jelenti, hogy az i állapotból nem érhet½o el a j álapot, ha pedig az összeg értéke pontosan 1 akkor az fij (n) (n = 1; 2; :::) úgy tekinthet½o, mint egy valószín½uségi változó eloszlása. Ez a valószín½uségi változó az elérési id½o. Látható, hogy nehézségbe ütközik az fij (n) nagyon sok értékének a kiszámítása, ezért az elemzésekben inkább az elérési id½o mij várható értékét szokták meghatározni, amelyet a 8 1 X > > fij (n) < 1 1; ha > < mij =

n=1

1 1 X X > > > nfij (n) ; ha fij (n) = 1 : n=1

n=1

kifejezés értelmez. Tegyük fel, jelenleg az i-dik állapotban vagyunk és pij a valószín½usége, hogy átlépjünk a j állapotba. Ennek várható értéke mij . Ha k 6= j, akkor pik valószín½uséggel átlépünk a k állapotba, majd innen a j állapotba. Ez utobbi várható értéke mkj . Ilyenkor átlagban 1 + mkj lépés szükséges ahhoz, hogy az i állapotból a j állapotba érjünk. A várható értékek közti összefüggés alapján X mij = pij + pik (1 + mkj ) : k6=j

Mivel pij +

X k6=j

pik = 1;

10

5. Markov-lánc

ezért az mij várható elérési id½ok megoldásai az X mij = 1 + pik mkj minden i; j = 1; 2; :::N esetén

(5.9)

k6=j

egyenletrendszernek. llusztrációként kiszámítsuk az 5.1. mintapéldában a várható elérési id½oket. Felírjuk a (5.9) egyenletrendszert a P valószin½uség-átmeneti mátrixra 8 m11 = 1 + p12 m21 + p13 m31 > > > > m12 = 1 + p11 m12 + p13 m32 > > > > m13 = 1 + p11 m13 + p12 m23 > > > > < m21 = 1 + p22 m21 + p23 m31 m22 = 1 + p21 m12 + p23 m32 > > m23 = 1 + p21 m13 + p22 m23 > > > > m31 = 1 + p32 m21 + p33 m31 > > > > m = 1 + p31 m12 + p33 m32 > > : 32 m33 = 1 + p31 m13 + p32 m23 azaz 8 m11 = 1 + 0:3 m21 + 0:1 m31 > > > > m12 = 1 + 0:6 m12 + 0:1 m32 > > > > m13 = 1 + 0:6 m13 + 0:3 m23 > > > > < m21 = 1 + 0:8 m21 + 0:05 m31 m22 = 1 + 0:15 m12 + 0:05 m32 > > m23 = 1 + 0:15 m13 + 0:8 m23 > > > > m31 = 1 + 0:4 m21 + 0:5 m31 > > > > m32 = 1 + 0:1 m12 + 0:5 m32 > > : m33 = 1 + 0:1 m13 + 0:4 m23 Az egyenletrendszer megoldásai: m11 = 3:8168; m12 = 3:1579; m13 = 14:286; m21 = 6:875; m22 = 1:6051; m23 = 15:714; m31 = 7:5; m32 = 2: 631; m33 = 8:6957: Meg…gyelhet½o, hogy az m11 , m22 , m33 várható visszatérési id½ok reciprokai az x1 ; x2 ; x3 egyensúlyi eloszlásoknak: azaz 1 1 = = 3:8168; m11 = x1 0:262 1 1 m22 = = = 1:6051; x2 0:623 1 1 m33 = = = 8:6957: x3 0:115 Kimutatható, hogy ez a tulajdonság általában is érvényes, azaz ha P egy ergodikus valószin½uség-átmeneti mátrix akkor a Markov-lánc átlagos visszatérési idejei és az egyensúlyi eloszlások között fennáll az alábbi összefüggés: 1 mii = : xi Mit is mutatnak meg ezek a számok? Például az m11 azt, hogy egy olyan vásárló aki az A cég termékéb½ol vásárolt várhatóan még 3:8168 hónapig ennél a cégnél fog vásárolni, miel½ott áttérne a B vagy a C termék vásárlására.. Az m12 = 3:1579 pedig azt mutatja, hogy

5. Markov-lánc

5.2.

11

Markov-láncok tanulmányozása a WinQSB segítségével

Az el½obbi paragrafusban bemutatott számításokat a WinQSB Markov-folyamat eszköztára (Markov Process) automatikusan elvégzi. Alkalmazásképpen tanulmányozzuk az alábbi feladatot a WinQSB segítségével. 5.2. mintapélda (Részvényárfolyam) Részvényárfolyam elemzésekor nagyon sokszor csak az érdekel, hogy az illet½o részvény árfolyama n½o vagy csökken. Egy általunk vizsgált részvény árfolyama az elmúlt 30 napon a következ½o változást mutatta: N C C N N C C N C C N C C C N C N C C N C N N C N C C N C C, ahol az N azt mutatja, hogy az illet½o napon n½ot, a C pedig, hogy csökkent az árfolyam. a. Adjuk meg a feladat átmenet-valószín½uség mátrixát és rajzoljuk meg az átmenet-valószín½uségi gráfját feltéve, hogy csak a legutolsó változás befolyásolja a következ½o napi árfolyamot. Ergodikus-e az átmenet-valószín½uségi mátrix? Tegyünk becslést az árfolyam következ½o napi és hosszú távú változásával kapcsolatosan. Határozzuk meg a várható elérési id½oket és magyarazzuk meg az eredményt. b. Adjuk meg a feladat átmenet-valószín½uség mátrixát és rajzoljuk meg az átmenet-valószín½uségi gráfját feltéve, hogy az utolsó két napi változás befolyásolja a következ½o napi árfolyamot. Ergodikus-e az átmenet-valószín½uségi mátrix? Tegyünk becslést az árfolyam következ½o napi és hosszú távú változásával kapcsolatosan. Határozzuk meg a várható elérési id½oket és magyarazzuk meg az eredményt. Megoldás a. Meg…gyelhetjük, hogy az utolsó állapotot leszámítva összesen 12 darab "N" és 17 darab "C" állapotunk van, amib½ol N ! N átmenet, azaz "NN" szekvencia 2 darab, N ! C, azaz "NC" szekvencia 10 darab, C ! C átmenet, azaz "CC" szekvencia 8 darab és C ! N , azaz "CN" szekvencia 9 darab található. Ezért az átmenet-valószín½uségeket (átmenetgyakoriságokat) megadó táblázat: N C

N

C

2 12 9 17

10 12 8 17

Az átmenet-valószín½uségi mátrix P =

2 12 9 17

10 12 8 17

=

0:166 67 0:833 33 0:529 41 0:470 59

:

Tudjuk a mai napon az árfolyam csökken½o ugrást mutatott (mivel a sorozatban az utolsó bet½u C). Tehát a kezdeti eloszlás Q (0) = (0; 1) : A mátrix alapján elkészített átmenet-valószín½uségi gráfot tartalmazza a 5.2 ábra. Az (5.2) átmenet-valószín½uségi gráfot elemezve láthatjuk, hogy minden állapot minden állapottal komunikál, minden állapot visszatér½o (azaz bármely állapotból ha kilépünk vissza is tudunk jutni oda) és aperiodikus, mivel P mátrix egyetlen eleme sem nulla. Következésképpen a P átmenet-valószín½uség mátrix ergodikus. A WinQSB Markov-folyamat (Markov Process) eszköztárát használva az Új alkalmazás (New Problem) menupont kiválasztásával betöltjük az eszköztár 5.3 kezd½otábláját. Itt megadjuk a feladat megnevezését (Problem Title) és az állapotok számát (Number of States). Az OK gombra való kattintás után betölt½odik a feladat 5.4 adattáblája. Itt megadjuk a P

12

5. Markov-lánc

5.2. ábra. A 5.2. mintapélda átmenet-valószín½uségi gráfja.

5.3. ábra. A Részvényárfolyam mintapélda a. alpontjának kezd½otáblája.

5.4. ábra. A Részvényárfolyam mintapélda a. alpontjának adattáblája.

átmenet-valószín½uségi mátrixot, a Q (0) kezdeti eloszlást (Initial Prob.) és az egyes állapotokhoz rendelt költséget (State Cost). Mivel ebben a feladatban az állapotok költségei nem érdekelnek, ezt a sort ½uressen hagyjuk. Az els½o feladatunk meghatározni, hogy a következ½o napon milyen valószín½uséggel fog n½oni, illetve csökkeni az árfolyam. A lépcs½o ikkonra kattintás után megjelenik az eszköztár elemz½o 5.5 ablaka. Itt beírjuk a Kezdeti állapottól való lépés számát (The number of time periods from initial) mez½obe, hogy melyik napra szeretnénk becslést tenni. Mivel minket a következ½o nap érdekel, ezért ide 1-et írunk. Az OK-ra kattintva megkapjuk a következ½o hónapi becslést. Ez a Becsült állapot valószín½uségek (Resulted State Probability) oszlopból olvashatók ki. Ennél a lépésnél a WinQSB tulajdonképpen a Q (1) = Q (0) P = (0:529410; 0:470590) mátrixszorzást végzi el. A kapott eredmények azt mutatják, hogy a következ½o nap az árfolyam 52.941% valószín½uséggel n½oni, és 47.059% valószín½uséggel pedig csökkenni fog. Ha a két napra el½ore becslést akarunk tenni, akkor a Következ½o lépés (Next Period) gombra kattintunk, ha pedig az egyensúlyi eloszlást szeretnénk meghatározni, akkor a Egyensúlyi állapot (Steady State) gombra kell kattintani. Hosszabb periódusra is becslést tudunk tenni, és egy el½orejelz½o gar…kont is el tudunk készíteni, ha tarpéz vonalat mutató ikonra kattintunk. Ekkor megjelenik a 5.6 ábra, ahonnan kiválasztjuk, hogy melyik állapot érdekel minket. Mondjuk, ha a növekv½o állapot (N-State 1), akkor az 1-es állapot valószín½uségi eloszlását (Probability of State State1) választjuk ki.

5. Markov-lánc

13

5.5. ábra. A részvényárfolyam mintapélda a. alpontjának lépésenkénti elemz½o ablaka.

5.6. ábra. A részvényárfolyam mintapélda a. alpontja állapotainak valószín½uség változását elemz½o ablak.

14

5. Markov-lánc

5.7. ábra. A részvényárfolyam mintapélda a. alpontja növekv½o állapotainak valószín½uségeit tartalmazó eredménytábla.

5.8. ábra. Becslés a részvényárfolyam a. alpontja mintapélda növekv½o állapot valószín½uségeinek változására az elkövetkez½o 10 napra.

Az OK-ra kattintva betölt½odik az 5.7 eredménytábla. A táblázatból kiolvasható, hogy a következ½o 10 napban milyen valószín½uséggel fog n½oni az árfolyam. Ennek a táblázatnak az elkészítéséhez a 4.1. mintapélda c. alpontjában bemutatott számításokat végzi el a WinQSB, azaz kiszámítja a Q (n) = Q (0) P n mátrixszorzat els½o elemét, amikor n = 1; 2; 3; :::10: A táblázat harmadik oszlopa (Probability of State State1) az árfolyam növekedés valószín½uségeit tartalmazza az elkövetkez½o 10 napra. Ha a változás gra…konját is meg akarjuk jeleníteni, akkor az Eredmények (Results) menupontból kiválasztjuk a Jelenítsd meg az id½o szerinti elemzés gra…konját (Show Time Parametric Analysis-Graph). A WinQSB által készített gra…kont tartalmazza az 5.8 ábra. Az 5.8 gra…konról leolvasható, hogy az árfolyam növekedés valószín½usége az elkövetkez½o 5 napban nagyobb ingadozásokat mutat. Hosszabb távon látható, hogy ez a valószín½uség a 0:3885 állandó értéket veszi fel. Ez természetes is, mivel az átmenet-valószín½uség mátrix ergodikus tulajdonságú.

5. Markov-lánc

15

5.9. ábra. A részvényárfolyam mintapélda a. alpontja csökken½o állapotainak valószín½uségeit tartalmazó eredménytábla.

5.10. ábra. Becslés a részvényárfolyam mintapélda a. valószín½uségeinek változására az elkövetkez½o 10 napra.

alpontja csökken½o állapot

Úgyanez a vizsgálat elvégezhet½o a csökkenés valószín½uségeinek a megállapítására is. Ebben az esetben a 5.6. ablakból a 2-es állapot valószín½uségi eloszlását (Probability of State State2) választjuk ki. Az eredménytáblát a 5.9 ábra tartalmazza. A csökken½o állapot valószín½uségeinek 5.10 gra…konját hasonlóan jelenítsük meg ahogyan az el½obbiekben a növekv½o állapotoknál eljártunk. Az 5.10 gra…konról leolvasható, hogy az árfolyam csökkenés valószín½usége az elkövetkez½o 5 napban nagyobb ingadozásokat mutat. Hosszabb távon látható, hogy ez a valószín½uség a 0:6115 állandó értéket veszi fel. Mivel az átmenet-mátrix ergodikus van a folyamatnak egyensúlyi eloszlása. Amint már a 4.1. mintapélda d. alpontjában láttuk, ennek meghatározására meg kell oldani a (5.7) egyenletrendszert. A WinQSB meghatározza az egyenletrendszer megoldásait, és az eredményt a 5.11 táblában jeleníti meg ha a síz½o emberke ikonra kattintunk.

16

5. Markov-lánc

5.11. ábra. A részvényárfolyam mintapélda a. alpontja egyensúlyi eloszlásai és várható visszatérési idejei.

5.12. ábra. A részvényárfolyam mintapélda a. alpontja várható elérési idejeit tartalmazó eredménytábla.

Az egyensúlyi eloszlások a táblázat harmadik oszlopából (State Probability) olvashatók ki: x = (0:3885; 0:6115) : Ezek a számok megmutatják, hogy ha az átmenet-valószín½uségi mátrix a következ½o id½operiódusban is állandó marad, akkor hosszabb távon (7-8 nap után) annak valószín½usége, hogy a részvény ára n½ojön 38.85% és annak valószín½usége, hogy csökkenjen 61.15%. Ha meg…gyeljük ugyanezt az erdeményt mutatják a 5.8., 5.10. gra…konok illetve a 5.7., 5.9 eredménytáblák is. A 5.11. tábla utolsó oszlopa az m11 = 2:5741; m22 = 1:6353 várható visszatérési id½oket tartalmazza. Amint már a 4.1. mintapélda e. alpontjában bemutattuk az egyensúlyi eloszlások és a várható visszatérési id½ok között az mii = 1=xi (i = 1; 2) összefüggés áll fenn. Ezek a számok azt mutatják meg, hogy ha a mai napon az árfolyam n½o, akkor várhatóan legközelebb 2.5741nap után fog újra n½oni, ha pedig az árfolyam a mai napon csökken, akkor várhatóan legközelebb 1.6353 nap után fog újra csökkenni. A többi várható elérési id½oket az m12 -t és m21 -t megkapjuk ha megoldjuk a 4.1. mintapélda e. pontjában megadott (5.9) egyenletrendeszert. A WinQSB meghatározza ennek az egyenletrendszernek a megoldásait, és az eredményt a 5.12 táblában jeleníti meg, ha az Eredmények (Results) menupont Add meg az els½o elérési id½oket (Show First Passage Times) fejlécére kattintunk. A 5.12 táblából kiolvasható, hogy az m11 = 2:5741; m12 = 1:2, m21 = 1:6353; m22 = 1:6353: Az m11 és m22 jelentését már az el½obb bemutattuk. Az m12 jelentése, hogy ha a mai napon az árfolyam n½o, akkor várhatóan legközelebb 1.2 nap múlva fog csökkenni. Az m21 jelentése pedig, hogy ha a mai napon az árfolyam csökken, akkor várhatóan legközelebb 1.6353 nap múlva fog n½oni. b. Az 4.2. mintapélda b. pontjában a pontosabb el½orejelzés érdekében feltesszük, hogy az utolsó két változás eredménye befolyásolja a kimenetelt. Ekkor négy állapotot veszünk fel: NN (2 darab), NC (10 darab), CN (9 darab), CC (7 darab). A 28 vizsgált átmenetben 2-szor fordult el½o az N N C szekvencia, ami azt jelenti, hogy az N N ! N C átmenet relatív gyakorisága 22 :Úgyszintén például a CN C szekvencia a sorozatban 7-szer fordul el½o, ezért a CN ! N C átmenet relatív gyakorisága 79 . Az átmenet-valószín½uségi mátrix a következ½o:

5. Markov-lánc

17

5.13. ábra. A 5.2. mintapélda b. alpontjának átmenet-valószín½uségi gráfja.

NN NC CN CC

NN 0 0

NC 1 0

CN 0

CC 0

2 9

7 9

3 10

7 10

0

0

0

0

6 7

1 7

A mátrixok alapján elkészíthetett átmenet-valószín½uségi gráfokat tartalmazza a 5.13 ábra. Tudjuk a mai és a tegnapi napon az árfolyam csökken½o ugrást mutatott (mivel a sorozatban az utolsó két bet½u C). Tehát a kezdeti eloszlás Q (0) = (0; 0; 0; 1) : Legel½oször is meg kell vizsgéljuk, hogy az átmenet-valószín½uségi mátrix ergodikus-e. Az (5.13) átmenet-valószín½uségi gráfot elemezve láthatjuk, hogy minden állapot minden állapottal komunikál, minden állapot visszatér½o (azaz bármely állapotból ha kilépünk vissza is tudunk jutni oda). Az ergodikusság érdekében még azt kell megnézni, hogy a P aperiodikuse? Itt már nem azonnal látszik ennek a tulajdonságnak a teljesülése, mert a mátrix soraiban vannak nulla elemek. Az elemzés érdekébe számítsuk ki a P 2 ; P 3 mátrixokat.Azt találjuk, hogy 1 1 0 1 0 7 3 1 3 7 0 0 10 15 30 5 10 10 8 109 373 C B 2 B 1 7 3 1 C 3 2 15 15 700 2100 15 30 5 10 C: C B B P =@ 49 8 7 7 49 A ; P = @ 7 A 0 29 30 135 270 15 30 90 4 21

2 3

6 49

1 49

4 147

2 7

373 1715

2416 5145

Az aperiodikusság értelmezése szerint ha találunk egy olyan n hatványkitev½ot, amelyre P n mátrix egyetlen eleme sem nulla, akkor a P aperiodikus. A mi esetünkben P 3 egyetlen eleme sem nulla, következésképpen a P valószín½uség-átmenet mátrixa aperiodikus lesz. Összegezésként kijelenthetjük, hogy a P ergodikus tulajdonságú. A továbbiakban hasonlóan járunk el mint az a. alpontban. A WinQSB Markov-folyamat (Markov Process) eszköztárát használva az Új alkalmazás (New Problem) menupont kiválasztásával betöltjük az eszköztár 5.3 kezd½otábláját. Itt megadjuk a feladat megnevezését (Problem Title: Részvényárfolyam b. ) és az állapotok számát (Number of States). Ebben az esetben ez 4. Az OK gombra való kattintás után betölt½odik a feladat 5.14 adattáblája. Itt megadjuk a P átmenet-valószín½uségi mátrixot, a Q (0) kezdeti eloszlást (Initial Prob.) és az

18

5. Markov-lánc

5.14. ábra. A Részvényárfolyam mintapélda b. alpontjának adattáblája.

egyes állapotokhoz rendelt költséget (State Cost). Mivel ebben a feladatban az állapotok költségei nem érdekelnek, ezt a sort ½uressen hagyjuk. Az állapotok megnevezéseit (State1, State2,State3, State4) könnyebben felismerjük, ha a Szerkesztés (Edit) menupont Állapotok megnevezése (State Names) ablakban ezeket lecseréljük az általunk megadott (NN, NC, CN, CC) azonosítókra.Az els½o feladatunk meghatározni, hogy a következ½o napon milyen valószín½uséggel fog n½oni, illetve csökkeni az árfolyam. Hasonlóan mind az a. alpontban a lépcs½o ikkonra kattintás után megjelenik az eszköztár elemz½o 5.5 ablaka. Itt beírjuk a Kezdeti állapottól való lépés számát (The number of time periods from initial) mez½obe, hogy melyik napra szeretnénk becslést tenni. Mivel minket a következ½o nap érdekel, ezért ide 1-et írunk. Az OK-ra kattintva megkapjuk a következ½o hónapi becslést. A Becsült állapot valószín½uségek (Resulted State Probability) oszlopának tartalma Q (1) = (0; 0; 0:857140; 0:142860). Mivel jelenlegi állapotunk C, ezért minket csak a holnapi napi eloszlás a Q (1) harmadik és negyedik eleme érdekel. Tehát a CN állapot bekövetkezésének valószín½usége 0:857140 a CC állapoté 0:142860: Következésképpen a holnapi becslésünk: 85.71%-os valószín½uséggel az árfolyam n½oni és 14.28%-os valószín½uséggel pedig csökkenni fog. Emlékezzünk, az el½oz½o alpontban, amikor csak a mai napi árfolyam alapján becsültük a holnapi árfolyamot azt találtuk, hogy a holnapi az árfolyam 52.941% valószín½uséggel n½oni, és 47.059% valószín½uséggel pedig csökkenni fog. Látható, hogy az utolsó két napi változás eredményére alapozott becslés jóval nagyobb esélyt ad az árfolyam növekedésének. Ha több napra el½ore szeretnénk becsülni, és egy el½orejelz½o gra…kont is szeretnénk készíteni a trapéz vonalat mutató ikonra kell kattintanunk. Ekkor megjelenik a 5.6 ábrán bemutatott ablak, csak itt már négy állapot lesz felsorakoztatva. Innen szere kiválasztjuk az állapotokat és az utolsó id½opontot (Ending time period). Legyen ez a mi esetünkben 15 nap. A következ½o napokra kapott valószín½uségi eloszlásokat az alábbi táblázatba foglaltuk össze:

5. Markov-lánc

19

5.15. ábra. Valószín½uségi becslés a részvényárfolyam NN állapotának (egymásután két nap növekszik az árfolyam) változására a következ½o 15 napra.

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

NN 0 0 0.1905 0.0272 0.0483 0.1085 0.0640 0.0620 0.0840 0.0719 0.0688 0.0763 0.0733 0.0716 0.0734 0.0734

NC 0 0 0.6667 0.2857 0.1964 0.4281 0.3324 0.2809 0.3560 0.3356 0.3126 0.3358 0.3328 0.3237 0.3305 0.3307

CN 0 0.8571 0.1225 0.2175 0.4882 0.2878 0.2789 0.3780 0.3235 0.3095 0.3433 0.3298 0.3220 0.3329 0.3301 0.3267

CC 1 0.1429 0.0204 0.4696 0.2671 0.1756 0.3247 0.2790 0.2365 0.2830 0.2753 0.2582 0.2719 0.2718 0.2655 0.2693

A táblázat által megadott adatok alapján a WinQSB által készített gra…konokat mutatják a 5.15, 5.16, 5.17, 5.18ábrák. A gra…konokról leolvasható, hogy az árfolyam állapotainak valószín½uségei az elkövetkez½o 15 napban nagyobb ingadozásokat mutatnak, de ezután már kiegyensulyózodnak és egy bizonyos értékhez konvergálnak. Ez természetes is, mivel a P átmenet-valószín½uség mátrix ergodikus tulajdonságú. Mivel az átmenet-mátrix ergodikus van a folyamatnak egyensúlyi eloszlása. Amint már a 4.1. mintapélda d. alpontjában láttuk, ennek meghatározására meg kell oldani a (5.7) egyen-

20

5. Markov-lánc

5.16. ábra. Valószín½uségi becslés a részvényárfolyam NC állapotának (egyik nap n½o s a rákövetkez½o nap csökken az árfolyam) változására a következ½o 15 napra.

5.17. ábra. Valószín½uségi becslés a részvényárfolyam CN állapotának (egyik nap csökken s a rákövetkez½o nap n½o az árfolyam) változására a következ½o 15 napra.

letrendszert. Ha a síz½o emberke ikonra kattintunk a WinQSB kiszámítja az egyenletrendszer megoldásait, és az eredményt a 5.19 táblában jeleníti meg . Az egyensúlyi eloszlások a táblázat harmadik oszlopából (State Probability) olvashatók ki: x = (0:0731; 0:3291; 0:3291; 0:2678) : Ezek a számok megmutatják, hogy ha az átmenetvalószín½uségi mátrix a következ½o id½operiódusban is állandó marad, akkor hosszabb távon annak valószín½usége, hogy a részvény árfolyama egymásután kétszer n½ojön 7.31%, hogy irányt

5. Markov-lánc

21

5.18. ábra. Valószín½uségi becslés a részvényárfolyam NN állapotának (egymásután két nap csökken az árfolyam) változására a következ½o 15 napra.

5.19. ábra. A részvényárfolyam mintapélda egyensúlyi eloszlásai és várható visszatérési idejei.

váltson 32.91%, és hogy egymásután két nap csökkenjen 26.78% Meg…gyelhetjük ugyanezt az erdeményt mutatják a 5.15., 5.16., 5.17., 5.6. gra…konok illetve az összefoglaló táblázat is. A 5.7. tábla utolsó oszlopa (Rekurence Time) az m11 = 13:6751; m22 = 3:0389; m33 = 3:0389; m44 = 3:7211 várható visszatérési id½oket tartalmazza. Amint már a 4.1. mintapélda e. alpontjában bemutattuk az egyensúlyi eloszlások és a várható visszatérési id½ok között az mii = 1=xi (i = 1; 2; 3; 4) összefüggés áll fenn. Ezek a számok azt mutatják meg, hogy ha a tegnapi és a mai napon az árfolyam n½ot, akkor várhatóan legközelebb 13.6751 nap után fog újra egymásután kétszer n½oni, ha az árfolyam a tegnapi napon n½ot a mai napon pedig csökkent, akkor várhatóan legközelebb 3.0389 nap után fog újra ez az állapotváltozás lejátszani, ha pedig a tegnapi és a mai napon az árfolyam csökkent, akkor várhatóan legközelebb 3.7211 nap után fog újra egymásután kétszer csökkenni. A többi várható elérési id½oket az m12 -t, m13 -t, m14 -t, m21 -t, m23 -t, m24 -t, m31 -t, m32 t, m34 -t, m41 -t, m42 -t és m43 -t, megkapjuk ha megoldjuk a 4.1. mintapélda e. pontjában megadott (5.9) egyenletrendeszert. Ha az Eredmények (Results) menupont Add meg az els½o elérési id½oket (Show First Passage Times) fejlécére kattintunk a WinQSB meghatározza ennek az egyenletrendszernek a megoldásait és az eredményt a 5.20 táblában jeleníti meg, .

22

5. Markov-lánc

5.20. ábra. A részvényárfolyam mintapélda várható elérési idejeit tartalmazó eredménytábla.

A 5.20 táblából kiolvasható, hogy:m11 = 13:6751 m12 = 1, m13 = 2:8176, m14 = 2:9524, m21 = 12:6751, m22 = 3:0389, m23 = 1:8167, m24 = 1:9524, m31 = 10:8585, m32 = 1:2222, m33 = 3:0389, m34 = 3:1746, m41 = 12:0251, m42 = 2:3889, m43 = 1:1667, m44 = 3:7211: Az mii jelentését már az el½obb bemutattuk. Az m12 jelentése, hogy ha a tegnapi és a mai napon az árfolyam n½ot, akkor várhatóan legközelebb 1 nap múlva fog újra árfolyam n½oni. Az m41 jelentése pedig, hogy ha a tegnap és a mai napon az árfolyam csökkent, akkor várhatóan legközelebb 12:0251 nap múlva fog egymásután két nap n½oni.

5.3.

Kit½uzött feladatok

5.1. Egy tejtermékeket termel½o és forgalmazó cég részesedése a helyi piacból 25%. A cég marketing osztálya egy felmérés alapján megállapította, hogy az elmúlt évhez viszonyítva a vásárlók 88% h½uséges maradt a céghez ebben az évben is, 12%-a pedig elpártolt másik, hasonló termékeket forgalmazó cégekhez. Úgyszintén azt is megállapították, hogy a konkurens cégekhez is a vásárlók 88%- h½uséges maradt és csak 15% pártolt át hozzájuk. Ha ez a tendencia fennmarad, akkor egy év múlva, két év múlva és hosszú távon milyen piaci részesedéssel számolhat a cég? 5.2. A székelyföldi lakosság három csoportba sorolható, aszerint, hogy városban, falún vagy a városok vonzáskörzetében élnek. Egy adott évben a városlakó családok 10%-a átköltözik vonzáskörzetébe, és 5%-a falúra költözik. Ugyanakkor a városok vonzáskörzetében él½ok 3%a városokba és 4%-a falúra költözik. Végezetül a falusi lakósok 2%-a városokba és 4%-a a városok vonzáskörzetébe költözik. Ha valaki városban lakik, mi annak a valószín½usége, hogy két év múlva szintén városban fog lakni? Ha ez a tendencia megmarad 10 év múlva a székelyföldi lakosság hány százaléka fog városban élni, tudva azt, hogy jelenleg a lakosság 30%-a városokban, 55%-a falún és 15%-a a városok vonzáskörében él? 5.3. Három személy közül szeretnénk egyet igazságosan kiválasztani. E célból mindhárman feldobnak egy szabályos kockát. Ha a legnagyobb számot közülük csak egy dobja, akkor ½ot választjuk ki. Ha mindhárman egyforma számot dobnak, akkor megismételjük a dobásokat. Ha a legnagyobb számot ketten dobják, akkor a harmadik személy kiesik a választásból; a másik kett½o addig folytatja, amíg különböz½ot nem dobnak, és ekkor az nyer, aki a nagyobbat dobja. Igazságos-e ez a sorsolás? Várhatóan hány dobássorozatra kerül sor?

5. Markov-lánc

23

5.4. Egy országban a választásokon mindig csak két párt gy½ozhet: vagy az A, vagy a B. Az utolsó 30 választás eredményei a következ½ok: A A B A A B B A B B A B B B A B A B B A B A A B A B B A B B. a. Tegyünk becslést a választások kimenetelével kapcsolatosan feltéve, hogy csak a legutolsó választás eredménye befolyásolja a következ½o választás kimenetét. b. Tegyünk becslést a választások kimenetelével kapcsolatosan feltéve, hogy az utolsó két választási eredmény befolyásolja a kimenetelt. 5.5. Három herceg, A, B és C egyaránt szerelmes Bergengócia királylányába. Elhatározzák, hogy egyetlen pisztolypárbajban eldöntik, melyikük legyen a kér½o. Egyszerre körbeállnak és bármelyikük l½ohet bármelyikükre. Tudják egymásról, hogy ha l½o, akkor A 1, B 0,8 és C 0,5 valószín½uséggel talál, ezért abban állapodnak meg, hogy el½oször l½o C, utána (ha életben van) B, végül A. Ha nincs vége a párbajnak, akkor még egy kört l½onek azonos sorrendben. Mikor a királylány meghallotta a feltételeket, a párbaj el½otti este titokban kicserélte C els½o golyóját vaktöltényre. Kibe szerelmes a királylány? 5.6. Egy patkány kezdetben az ábra szerinti A ketrecben van. A patkányt beidomították: ha cseng½oszót hall, egy járaton keresztül átmegy valamelyik szomszédos ketrecbe. Amikor tehát a cseng½o megszólal, a patkány véletlenszer½uen, egyforma valószín½uséggel kiválaszt egy járatot; a döntését nem befolyásolja az sem, hogy el½oz½oleg merre ment. Mekkora a valószín½usége annak, hogy 23 cseng½oszó után a patkány a B ketrecben lesz?

5.7. Egy Chumpi nev½u csimpánz leül a számítógép elé, és elkezdi lelkesen püfölni a billenty½uzetet. A billenty½uzet az angol ábécé 26 nagybet½ujét tartalmazza; Chumpi pedig teljesen rendszertelenül (véletlenszer½uen) üti le egymás után a bet½uket. a) Igazoljuk, hogy ha Chumpi elég kitartó, akkor el½obb-utóbb leírja a nevét! b) Ehhez átlagosan hány leütésre van szüksége? (El½oször becsüljük meg, hogy ha egy leütés átlagosan 1 másodpercig tart, akkor várhatóan mennyi id½o alatt írja le Chumpi a nevét!) c) Chumpi stratégiát változtat. Most is véletlenszer½u a bet½uválasztása, de arra ügyel, hogy az éppen leütött karaktert nem ismétli (bár két lépés múlva persze már megint leütheti). Ezzel a módosítással átlagosan hány leütésre van szüksége, amíg a nevét véletlenszer½uen kiírja? (Több vagy kevesebb leütés kell, mint a b) esetben?)