Vizuálisan elmagyarázva
By Victor Powell
with text by Lewis Lehe
Az Andrej Markovról elnevezett Markov-láncok olyan matematikai rendszerek, amelyek egyik “állapotból” (helyzet vagy értékkészlet) a másikba ugranak. Ha például egy csecsemő viselkedésének Markov-lánc-modelljét készítenénk, akkor állapotokként szerepelhetne a “játék”, az “evés”, az “alvás” és a “sírás”, amelyek más viselkedésekkel együtt egy “állapottér”: az összes lehetséges állapot listája. Ezenkívül az állapottér tetején egy Markov-lánc megmondja az egyik állapotból bármelyik másik állapotba való átugrás valószínűségét – például, annak az esélyét, hogy az éppen játszó kisbaba a következő öt percben elalszik anélkül, hogy előbb sírna.
Egy egyszerű, két állapotból álló Markov-láncot mutatunk az alábbiakban.
sebesség
Az állapottérben két állapot (A és B) esetén 4 lehetséges átmenet van (nem 2, mert egy állapot visszaalakulhat önmagába). Ha “A”-ban vagyunk, akkor átmehetünk “B”-be, vagy maradhatunk “A”-ban. Ha ‘B’-ben vagyunk, akkor átmehetünk ‘A’-ba, vagy maradhatunk ‘B’-ben. Ebben a kétállapotú diagramban bármelyik állapotból bármelyik másik állapotba való átmenet valószínűsége 0,5.
A valódi modellezők természetesen nem mindig rajzolnak Markov-lánc diagramokat. Ehelyett egy “átmeneti mátrixot” használnak az átmeneti valószínűségek összeszámlálására. Az állapottér minden állapota egyszer soronként, egyszer pedig oszlopként szerepel, és a mátrix minden egyes cellája megmondja, hogy milyen valószínűséggel lehet átmenni az adott sor állapotából az adott oszlop állapotába. A mátrixban tehát a cellák ugyanazt a feladatot látják el, mint a nyilak a diagramon.
A B
Ha az állapottér egy állapottal bővül, akkor egy sort és egy oszlopot adunk hozzá, minden meglévő oszlophoz és sorhoz hozzáadva egy cellát. Ez azt jelenti, hogy a cellák száma négyzetesen nő, ahogy a Markov-láncunkhoz állapotokat adunk hozzá. Így az átmeneti mátrix elég gyorsan jól jön, hacsak nem akarunk egy dzsungel tornatermi Markov-lánc diagramot rajzolni.
A Markov-láncok egyik felhasználási módja az, hogy a számítógépes szimulációkba valós jelenségeket vonjunk be. Például ellenőrizni szeretnénk, hogy milyen gyakran fog egy új gát túlcsordulni, ami az egymás utáni esős napok számától függ. A modell felépítéséhez az esős (R) és napos (S) napok következő mintázatából indulunk ki:
Az időjárás szimulálásának egyik módja az lenne, hogy egyszerűen azt mondjuk: “A napok fele esős. Ezért a szimulációnkban minden nap ötven százalék esélye lesz az esőnek”. Ez a szabály a következő szekvenciát generálná a szimulációban:
Észrevetted, hogy a fenti szekvencia nem egészen úgy néz ki, mint az eredeti? A második szekvencia mintha ugrálna, míg az első (a valós adatok) mintha “ragadós” lenne. A valós adatokban, ha az egyik nap napos (S), akkor a következő nap is sokkal valószínűbb, hogy napos lesz.
Ezt a “ragaszkodást” egy kétállapotú Markov-lánccal minimalizálhatjuk. Amikor a Markov-lánc az “R” állapotban van, akkor 0,9 valószínűséggel marad a helyén, és 0,1 valószínűséggel távozik az “S” állapotba. Hasonlóképpen, az “S” állapotnak 0,9 valószínűsége van a helyben maradásra és 0,1 esélye az “R” állapotba való átmenetre.
A metereológusok, ökológusok, informatikusok, pénzügyi mérnökök és más, nagy jelenségeket modellezni kívánó emberek kezében a Markov-láncok igen nagy és nagy teljesítményűek lehetnek. Például a Google által a keresési találatok sorrendjének meghatározására használt PageRank nevű algoritmus egyfajta Markov-lánc.
Fentebb mellékeltünk egy Markov-lánc “játszóteret”, ahol saját Markov-láncokat készíthetünk, ha egy átmeneti mátrixszal babrálunk. Itt van néhány, amiből példaként dolgozhatsz: ex1, ex2, ex3 vagy generálj egyet véletlenszerűen. Az átmeneti mátrix szövege pirosra változik, ha a megadott mátrix nem érvényes átmeneti mátrix. Az átmeneti mátrix sorainak összege 1 kell, hogy legyen, és ugyanannyi sornak kell lennie, mint oszlopnak.
A teljes képernyős változatot is elérheti a setosa.io/markov
oldalon.