SZTAKI Közlemények 7. (1971)

Tankó József: Egyszerű algoritmus véges állapotú Markov-lánc ergodikus osztályainak meghatározására

- 3 - EGYSZERŰ ALGORITMUS VÉGES ÁLLAPOTÚ MARKOV-LÁNC ERGODIKUS OSZTÁLYAINAK MEGHATÁROZÁSÁRA Írta: Tankó József Az alábbiakban ismertetünk egy egyszerű algoritmust véges állapotú homogén Markov-lánc ergodikus osztályainak meghatározására és igazoljuk az algoritmus helyességét. Az algoritmus kevés állapot esetén egyszerű grafikus formában is végrehajtható. Nagyobb állapotszám esetén a megadott ALGOL vagy FORTRAN program lehetővé teszi az algoritmus számológéppel törté­nő végrehajtását. Az algoritmus eredményét egy jelölő vektorral ábrázolhatjuk, amelyből kiolvasható, hogy mely állapotok tartoznak ugyanabba az ergodikus osztályba és mely állapotok lényegtelenek. Ennek alapján a Markov-lánc állapotai könnyen átszámozhatók úgy is, hogy az ergodikus osz­tályok tagjai egymásutáni sorszámokat kapjanak és a legnagyobb sorszámúak legyenek a lényeg­telen állapotok. Ily módon elérhető a Markov-lánc egylépéses átmenetmátrixának szokásos kvá­­zi-diagonális szupermátrixszá való átrendezése. Az algoritmus alkalmas irányított gráf erősen összefüggő* zárt (amelyből nem vezet ki nyíl) komponenseinek megkeresésére is, ha a csúcsoknak a Markov-lánc állapotait, irányított éleinek pedig az átmenetmátrix pozitív elemeit (a hiányzó éleknek 0 elemeket) feleltetünk meg. 1. AZ ALGORITMUS ÉS IGAZOLÁSA Ebben a részben ismertetjük és igazoljuk a grafikus algoritmust, majd egy példán illuszt­ráljuk azt. Előzőleg azonban néhány definíciót adunk. 1.i. definíciók és előkészítés Legyen {Xt} egy n állapotú homogén Markov-lánc Р = {р^, ij= l,2,...,n} egylépéses átmenet valószínűségekkel. Az állapotok számozási sorrendje tetszőleges és a P mátrix p.. 3* 0 eleme annak valószínűségét adja meg, hogy X... = j legyen, feltéve, hogy X = i = t + 1 , 2 Ри = 1 , j=­ 4 egy u.n. sztochasztikus mátrix, ahol ^t+1 = j legyen, feltéve, hogy X­ = i volt. P i = 1,2,. . ., n (bár az algoritmusban ez nincs kihasználva!). A szemléltetés céljából a Markov-láncot ábrázolhatjuk egy irányított gráf formájában is, amelynél a csúcsok a Markov-lánc állapotainak felelnek meg, a szereplő nyilak pedig a Pjj 1­0 pozitív egylépéses átmenetvalószínűségeket reprezentálják. Az erősen összefüggő (és zárt) komponensek meghatározására ismeretesek egyéb algoritmusok is, de az itt ismertetett algo­ritmus számológépi végrehajtása jóval egyszerűbb. (1. pl. B. Roy: Algèbre moderne et théorie des graphes, Dunod, Paris, Paris, 1969.)

Next