A matematikában 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 adott jelenbeli állapot mellett, a rendszer jövőbeni állapota nem függ a múltbeliektől. Másképpen megfogalmazva ez azt is jelenti, hogy a jelen leírása teljesen magába foglalja az összes olyan információt, ami befolyásolhatja a folyamat jövőbeli helyzetét. Vegyünk például egy olyan fizikai rendszert, amelynek lehetséges állapotai . Az S rendszer az idő múlásával állapotait véletlenszerűen változtatja; vizsgáljuk a rendszer állapotait a diszkrét időpontokban, és legyen egyenlő k-val, ha S az n időpontban az állapotban van. Ezzel a terminológiával a Markov-tulajdonság így is megfogalmazható: A rendszer korábbi állapotai a későbbi állapotokra csak a jelen állapoton keresztül gyakorolhatnak befolyást.
Adott jelen mellett tehát a jövő feltételesen független a múlttól. Semmi, ami a múltban történt, nem hat, nem ad előrejelzést a jövőre nézve, a jövőben minden lehetséges. Alapvető példa erre az érmedobás – ha fejet dobunk elsőre, 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űsége, hogy fejet kapunk 101.-re, mint annak, hogy írást, az előzőekhez hasonlóan-a múlt tehát nem jelzi előre a jövőbeli 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őbeni dobás alakulását.
Minden egyes pillanatban a rendszer az adott valószínűségi változó eloszlása alapján vagy megváltoztatja az állapotát a jelenbeli állapotától, vagy ugyanúgy marad. Az állapotváltozásokat átmenetnek nevezzük, és azokat a valószínűségeket, melyek a különböző állapotváltozásokra vonatkoznak, átmenet-valószínűségeknek nevezzük. Ez a fogalom megtalálható a véletlen analízisben is.
Formális definíció A nem független valószínűségi változók egy jelentős osztálya a Markov-láncok. Egy X1, X2, X3, ... valószínűségi változó sorozatot Markov-láncnak nevezzük, ha az alábbi feltétel teljesül rá minden n természetes számra és minden x, x1, x2,..., xn valós számrendszerre 1 valószínűséggel:
Ezt a feltételt szokás Markov-tulajdonságnak is nevezni. Jelen esetben az Xi lehetséges értékei egy megszámlálható S halmazból valóak. Ezt az S halmazt állapothalmaznak nevezzük. A Markov-láncokat ábrázolhatjuk irányított gráfokkal is, ahol a csúcsok az egyes állapotok, a két csúcsot összekötő élre írt érték (felfogható súlyokként is) pedig az egyik állapotból a másikba kerülés valószínűsége (iránynak megfelelően).
Típusai Stacionárius átmenetvalószínűségű (homogén) Markov-láncról beszélünk, ha az átmenet-valószínűségek nem függnek az időtől, azaz:
n-től függetlenül.
m-edrendű Markov-láncok az olyan Markov-láncok, melyekre (véges m esetén):
minden n-re, vagyis a rendszer csak m időszakra emlékszik vissza, a korábbiak állapotok nem befolyásolják a jövőt.
m=1 esetén egyszerű Markov-láncnak nevezzük.
Példa Legyen egy dolog két állapota A és E, azaz az S állapothalmaz kételemű, S = {A, E}. center|200px Ha a dolog egy t időpontban A állapotban van, akkor annak a valószínűsége, hogy (t+1)-ben E állapotba kerül, legyen 0,4. Annak a valószínűsége, hogy továbbra is A-ban marad, 0,6 lesz (mivel a két feltételes valószínűség összege szükségszerűen 1 kell legyen). Ha a dolog ugyanebben a t időpontban E állapotban van, akkor annak a valószínűsége, hogy (t+1)-ben A állapotba kerül, legyen 0,7. Annak a valószínűsége, hogy továbbra is E-ben marad, 0,3 lesz.
Ezt ábrázolja a bal oldali irányított gráf, ahol A és E állapotokat egy-egy kör szemlélteti, az egyes körökből kimenő nyilak mellé írt számok pedig az átmenet-valószínűségek.
Gyakran csak az állapotváltozások nyilait rajzolják fel az ilyen ábrákon, mivel annak az valószínűsége, hogy egy állapot változatlan marad, kiszámolható úgy, hogy 1-ből levonjuk az állapotot szemléltető körből kimenő nyilak fölé írt valószínűségek összegét. Ez egy stacionárius, egyszerű (elsőrendű) Markov-lánc.
Valamely véges állapotú gép jól reprezentálhatja a Markov-láncokat. Feltételezzük, hogy a masinánk lehetséges inputjai egymástól függetlenek és egyenletes eloszlásúak. Ekkor, ha a gépezet egy tetszőleges y állapotban van az n-edik időpillanatban, akkor annak valószínűsége, hogy az n + 1-edik pillanatban az x állapotban lesz, csak a jelenlegi állapottól függ.
Markov-láncok tulajdonságai Először szükséges bevezetnünk az egy-lépéses átmenet-valószínűség:
és az n-lépéses átmenet-valószínűség fogalmát:
Előbbi az i állapotból egy lépéssel a j állapotba kerülés, utóbbi az n. lépés után a j állapot valószínűségét fejezi ki, feltéve, hogy .
Az n-lépéses átmenet-valószínűségekre teljesül a Chapman–Kolmogorov-egyenlőség, amely 0 < k< n esetén minden k-ra az alábbi:
Egy Markov-lánc kezdeti eloszlása egy (sor)vektor, mely az alábbi módon értelmezett
Míg az abszolút eloszlása az n-edik időpillanatban
ahol
j=1, 2, ..., s. s féle állapot van.
Azonban egy Markov-lánc lehet az időtől független, ilyenkor eloszlása, azaz nem függ n-től, azaz minden n-re. Ekkor szokás az eloszlást egyszerűen -vel jelölni.
Reducibilitás
Egy tetszőleges i, j állapotpárról azt mondjuk, hogy i-ből elérhető a j állapot (jelölése: i → j), ha feltéve, hogy az i állapotban vagyunk, annak a valószínűsége, hogy valamikor a jövőben a j-be kerülünk, nem nulla. Formálisan, j elérhető i-ből, ha létezik olyan n>0, melyre
Egy i állapot egy j állapottal kapcsolatos (más néven közlekedik) (jelölve: i ↔ j), ha i-ből j és j-ből i is egyaránt elérhető. Egy C halmaz kapcsolatos osztályt alkot, ha benne minden elempár kapcsolatos egymással, és nem létezik olyan C-n kívüli állapot, amely valamely C-beli állapottal kapcsolatos lenne. (Azt is mondhatjuk, hogy a kapcsolatosság ekvivalenciareláció, tehát osztályokra bontja az állapotteret). Egy ilyen osztályt zártnak hívunk, ha az osztály elhagyásának valószínűsége nulla, azaz ha i C-beli, de j nem, akkor j nem elérhető i-ből. Végezetül, egy Markov-láncot irreducibilisnek nevezünk, ha állapotainak halmaza egy kapcsolatos osztályt alkot: vagy mind tranziensek, vagy rekurrens zérus állapotok, vagy rekurrens nem zérus állapotok. Mindegyik esetben az összes állapot periódusa megegyezik. Egy véges sok állapotú láncnak nem lehet zérus állapota, és nem lehet az összes állapota tranziens. Egy irreducibilis Markov-láncban bármely állapotból bármely állapotba eljuthatunk valahány (véges) lépésben.
Periodicitás
Tetszőleges i állapot periódusa k, ha ahhoz, hogy i állapotból i állapotba visszatérjünk, k-nak valamely többszörös darabszámú lépésre van szükség. Például, ha egy i állapotba való visszatérés csak páros darab lépésben történhet meg, akkor i periódusa 2 lesz. Egy i állapot periódusának formális definíciója:
(ahol „lnko” a legnagyobb közös osztó). Meg kell jegyezni, hogy attól függetlenül, hogy egy állapot periódusa k, nem jelenti azt, hogy belőle kiindulva k lépésben újra el tudjuk érni azt. Például, ha egy állapotba vissza tudunk térni {6,8,10,12,...} lépésben, akkor annak periódusa 2 lesz, annak ellenére, hogy a 2-es szám nincs a listában. Ha k = 1, akkor az állapotot aperiodikusnak nevezzük. Egyébként (ha k>1) az állapotot k-periodikusnak mondjuk.
Bebizonyítható az is, hogy egy kapcsolatos osztályban minden állapot periódusa ugyanaz, azaz a periódus osztálytulajdonság.
Egy véges állapotú irreducibilis Markov-láncot ergodikusnak nevezünk, ha minden állapota aperiodikus.
Rekurrencia
Egy tetszőleges i állapot tranziens , átmeneti, ha (feltéve, hogy i állapotból indulunk) annak a valószínűsége, hogy soha nem térünk vissza i-be nem nulla, azaz annak valószínűsége, a rendszer valamikor visszatér az i állapotba, nem egy. Legyen Ti valószínűségi változó az az első a lépésszám, ami után először visszatérünk i-be:
Ekkor i állapot tranziens, ha:
Egy i állapot lényeges: ha i → j esetén j → i is teljesül. A lényegesség osztálytulajdonság, azaz beszélhetünk lényeges és lényegtelen osztályokról, egy osztálynak vagy minden eleme lényeges, vagy egy sem. A lényeges osztályokból nem lehet kijutni (mert akkor vissza is tudnánk jönni, azaz osztályon belül maradnánk), a lényegtelenekből viszont kijuthatunk és ekkor többé már nem térhetünk vissza. A nem lényeges állapotok tranziensek (fordítva azonban nem igaz).
Legyen Mi a visszatérésig megtett lépésszám várható értéke (átlagos visszatérési idő)
Ekkor ha Mi véges, az i állapotot pozitívnak, egyébként nullállapotnak nevezzük. Meg lehet mutatni azt is, hogy egy állapot akkor és csak akkor lényeges, ha:
Egy i állapotot nyelőnek nevezünk, ha lehetetlen belőle kikerülni, azaz, ha
, azaz minden -re.
Ergodicitás Egy i állapotra azt mondjuk, hogy ergodikus, ha aperiodikus és pozitív. Ha pedig egy Markov-láncban minden állapot ergodikus, akkor magát a láncot is ergodikusnak nevezzük.
Szilárd-állapot analízis és határeloszlások Ha egy Markov-lánc homogén, azaz a folyamat egy időfüggetlen pij mátrixszal leírható, ekkor a π vektor a stacionárius eloszlás, ha -re teljesül, hogy:
Egy irreducibilis láncnak akkor és csakis akkor van stacionárius eloszlása, ha az összes állapota pozitív. Ebben az esetben π egyértelmű, és kifejezhető a kapcsolata a várt visszatérési idővel:
Továbbá, ha egy lánc irreducibilis és aperiodikus is, akkor bármely i és j állapotra,
Meg kell jegyeznünk, hogy ez nem szab feltételeket a kezdeti eloszlásra nézve, a lánc konvergál a stacionárius eloszláshoz függetlenül attól, hol kezdődött.
Ha egy Markov-lánc nem irreducibilis, akkor stacionárius eloszlása nem lesz egyértelmű (beleértve minden zárt kapcsolatos osztályt, ami a láncban van, mindegyiknek külön-külön saját stacionárius eloszlása lesz. Ezek közül egyik sem lesz kiterjeszthető az egész láncra). Azonban, ha egy j állapot aperiodikus, akkor
és az összes többi i állapotra legyen fij annak a valószínűsége, hogy eljutunk j-be valahány lépésben, ha i-ből indultunk,
Véges állapotú Markov-láncok
Ha az állapothalmaz véges, az átmenet-valószínűségek mátrixba rendezhetőek, ezt átmenetmátrixnak (jele: P) nevezzük. Ezen mátrix i-edik sorának j-edik elemét pij-vel jelöljük, és az alábbi módon kaphatjuk meg:
A P egy sztochasztikus mátrix, azaz minden eleme nemnegatív, és minden sorban az elemek összege 1 (ez a valószínűség tulajdonságaiból következik). Továbbiakban, ha egy Markov-lánc homogén, azaz átmenet mátrixának, P-nek elemei nem függnek az időtől (azaz n-től), ekkor a k-lépéses átmenet-valószínűség mátrixa megkapható az átmenet mátrix k-adik hatványként, azaz Pk alakban (ez a Chapman–Kolmogorov-tétel következménye).
A stacionárius eloszlás π, egy (sor)vektor, amelyre teljesül az alábbi egyenlet:
Más szóval a π stacionárius eloszlás az átmenetmátrix az 1 sajátértékéhez tartozó bal oldali (lenormált) sajátvektora.
A stacionárius eloszlás mindig létezik, de az nem garantált, hogy egyértelmű is lesz. Azonban ha egy Markov-lánc irreducibilis, aperiodikus és véges állapotterű, akkor létezik egy és csakis egy stacionárius eloszlás, π. Ráadásul Pk konvergál egy egy-rangú mátrixhoz, melynek minden sora a stacionárius eloszlás π, azaz
ahol 1 egy oszlopvektor, aminek minden eleme 1. Ez itt nem más, mint a Perron–Frobenius-tétel. Az állítás tehát nem jelent mást, hogy ahogy telik az idő, a Markov-lánc elfelejti, honnan indult (azaz a kezdeti eloszlását), és konvergál a stacionárius eloszláshoz.
Példa center|200px Vegyük ismét csak a fenti példabeli Markov-láncot, és írjuk fel a átmenetmátrixot:
Jelöljük -vel a dolog t-beli állapotának valószínűségeit:
ahol annak a valószínűsége, hogy a dolog t-ben E állapotban van, és annak a valószínűsége, hogy a dolog t-ben A állapotban van. (Természetesen minden t-re.)