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 osztályok tagjai egymásutáni sorszámokat kapjanak és a legnagyobb sorszámúak legyenek a lényegtelen á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 illusztrá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 10 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 algoritmus 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.)