Markov-láncok és Markov-folyamatok

Tárgyalni fogom a Markov-láncok és Markov-folyamatok elméletét, amely a valószínűségszámítás egyik fontos része. Kissé informálisan a Markov-folyamatokat úgy jellemezhetjük, mint olyan sztochasztikus folyamatokat, amelyek jövőbeli viselkedéséről egy adott időpontig összegyüjtött információt a folyamat viselkedése a megfigyelt időintervallum végpontjában teljes mértékben tartalmazza. Ez azt jelenti, hogy annak feltételes valószínűsége, hogy valamely a folyamat jövőbeli viselkedésétől függő esemény bekövetkezik, feltéve, hogy a Markov-folyamat a jelen időpontban egy adott értéket vesz fel, megegyezik ugyanennek az eseménynek a feltételes valószínűségével, feltéve a folyamat teljes múltbeli viselkedését. Megfogalmazom ezt az állítást pontosabban is. A pontos definicióban megjelenik a a feltételes valószínűség meglehetősen bonyolult, a Radon–Nykodim deriváltak létezésén alapuló általános fogalma. Viszont abban az esetben, amikor a Markov-folyamat csak véges vagy megszámlálhatóan végtelen sok értéket vesz fel, elegendő a feltételes valószínűség egyszerű, a bevezető valószínűségszámítás előadásban is ismertett fogalmának az ismerete és használata. Az ilyen egyszerűbb Markov-folyamatokat Markov-láncoknak nevezik az irodalomban.

A következő eljárást fogom követni. Megadom a Markov-folyamat definicióját az általános esetben, de részletesen csak a Markov-láncok elméletét fogom tárgyalni, ahol sok érdekes és tanulságos kérdés megjelenik, viszont nincs szükség arra, hogy nehéz mértékelméleti problémákkal foglalkozzunk. Először megadom a Markov-folyamat általános definicióját. Egy Markov-folyamat alkalmas tulajdonságokkal rendelkező, speciális sztochasztikus folyamat, amely egy paramétertől függ, amit időnek fogok nevezni. Külön tárgyalom azt az esetet, amelyben ez a paraméter tartomány (idő) a nem negatív valós számok halmaza, az ilyen Markov-folyamatot folytonos idejű Markov-folyamatnak hívják, és azt az esetet, amikor a paraméter tartomány a pozitív egész számok halmaza. Az ilyen Markov-folyamatokat diszkrét idejű Markov-folyamatnak hívják.

Folytonos idejű Markov-folyamat definiciója. Legyen adva egy X(t), t ≥ 0, sztochasztikus folyamat valamely (Ω, A, P) valószínűségi mezőn, amely értékeit valamely (E, E) mérhető téren veszi fel. Azt mondjuk, hogy X(t) (E, E)-térbeli értékű folytonos idejű Markov-folyamat, ha minden 0 ≤ s ≤ t < ∞ számpárra és E-mérhető A ∈ E halmazra teljesül a

P (X_{t} ∈ A|B(X_{s})) = P (X_{t} ∈ A|B(X_{u}, u ≤ s))

azonosság, ahol B(X_{s}) az X_{s} valószínűségi változó, B(X_{u}, u ≤ s) pedig az összes X_{u}, u ≤ s, valószínűségi változó által generált σ-algebrát jelöli.

Kissé általánosabban, legyen adva egy (E, E) térbeli értékeket felvevő X(t), t ≥ 0, sztochasztikus folyamat, valamint σ-algebrák növekvő F_{t}, t ≥ 0, családja egy (Ω, A, P) valószínűségi mezőn, azaz legyen F_{s} ⊂ F_{t}, ha s ≤ t, és legyen X_{t} F_{t}-mérhető valószínűségi változó, t ≥ 0. Teljesüljön ezenkívül a F_{t} ⊂ A reláció minden t ≥ 0 számra. Az (X_{t}, F_{t}), t ≥ 0, rendszer folytonos idejű Markov-folyamat, ha

P (X_{t} ∈ A|B(X_{s})) = P (X_{t} ∈ A|F_{s}) minden 0 ≤ s ≤ t < ∞ számra,

és A ∈ E halmazra.

Diszkrét idejű Markov-folyamat definiciója. Legyen adva egy X_{n}, n = 0, 1, …, sztochasztikus folyamat valamely (Ω, A, P) valószínűségi mezőn, amely értékeit valamely (E, E) mérhető téren veszi fel. Azt mondjuk, hogy X_{n} (E, E)-térbeli értékű diszkrét idejű Markov-folyamat, ha minden 0 ≤ m ≤ n < ∞ számra és E-mérhető A ∈ E halmazra teljesül a

P (X_{n} ∈ A|B(X_{m})) = P (X_{n} ∈ A|B(X_{k}, 0 ≤ k ≤ m))

azonosság, ahol B(X_{m}) az X_{m} valószínűségi változó, B(X_{k}, 0 ≤ k ≤ m) pedig az összes X_{k}, 0 ≤ k ≤ m, valószínűségi változó által generált σ-algebrát jelöli.

Kissé általánosabban tekintsünk egy (E, E) térbeli értékeket felvevő X_{n}, n = 0, 1, …, sztochasztikus folyamatot, és ezenkívül σ-algebrák növekvő F_{n}, n = 0, 1, …, családját egy (Ω, A, P) valószínűségi mezőn, azaz legyen F_{m} ⊂ F_{n}, ha m ≤ n, és legyen X_{n} F_{n}-mérhető valószínűségi változó, n = 1, 2, . . .. Teljesüljön ezenkívül a F_{n} ⊂ A reláció minden n = 0, 1, … számra. Az (X_{n}, F_{n}), n = 1, 2 …, rendszer diszkrét idejű Markovfolyamat, ha

P (X_{n} ∈ A|B(X_{m})) = P (X_{n} ∈ A|F_{m}) minden 0 ≤ m ≤ n < ∞ számra,

és A ∈ E halmazra.

1. megjegyzés: Az F_{t} = B(X_{u}, u ≤ t) illetve F_{n} = B(X_{k}, k ≤ n) választással tekinthetjük a Markov-folyamatok időben folytonos illetve diszkrét definicióit az általános definició speciális eseteinek.

2. megjegyzés: A Markov-folyamatok definiciójában szereplő P (X_{t} ∈ A|B(X_{s})) illetve P (X_{n} ∈ A|B(X_{m})) feltételes valószínűségek megadhatóak, mint az X_{s} = x illetve X_{m} = x feltételek valamint az s és t illetve m és n időpontok és A ∈ E halmazok függvényei. A P (X_{t} ∈ A|X_{s} = x) = P_{s,t}(x, A) illetve P (X_{n} ∈ A|X_{m} = x) = P_{m,n}(x, A), x ∈ E, A ∈ E), s ≤ t illetve m ≤ n mennyiségeket átmenet valószínűségnek hívják. Ezek szemléletes tartalma a következő: A P_{s,t}(x, A), illetve P_{m,n}(x, A) átmenet valószínűség megadja annak valószínűségét, hogy a Markov-folyamat a t illetve n időpontban az A halmaz valamely pontjába jut, feltéve, hogy az az s < t illetve m < n időpontban az x pontban tartózkodott. A Markov tulajdonság azt jelenti, hogy ha tudom milyen módon jutott a Markov-folyamat az x pontba az s illetve m időpontban, akkor ez a plusz ismeret nem befolyásolja a fenti feltételes valószínűség értékét.

3. megjegyzés: A továbbiakban feltesszük, hogy a Markov-folyamatok P_{s,t}(x, A) vagy P_{m,n}(x, A), s ≤ t illetve m ≤ n függvényei teljesítik a következő tulajdonságokat.

a) Rögzített x ∈ E pontra P_{s,t}(x, ·) illetve P_{m,n}(x, ·) valószínűségi mérték az (E, E) téren.

b) Rögzített A ∈ A halmazra P_{s,t}(·, A) illetve P_{m,n}(·, A) mérhető függvény az (E, E) téren.

c) P_{s,s}(x, A) = 1, ha x ∈ A és P_{s,s}(x, A) = 0, ha x ∉ A. Hasonlóan, P_{m,m}(x, A) = 1, ha x ∈ A és P_{m,m}(x, A) = 0, ha x ∉ A.

Ezek a tulajdonságok természetesek. Be lehet látni, hogy minden szép tulajdonságú téren definiált Markov-folyamatra (például ez a helyzet, ha (E, E) teljes szeparábilis metrikus tér a szokásos Borel σ-algebrával) meg lehet adni a feltételes átmenetvalószínűségeket úgy, hogy teljesítsék a fenti tulajdonságokat. Ennek a ténynek a bizonyítását, amely a reguláris feltételes eloszlás létezésének a bizonyításán alapul nem tárgyalom.

Általában úgynevezett stacionárius Markov-folyamatokkal foglalkoznak az irodalomban. Ha nem hangsúlyozzák külön az ellenkezőjét, akkor Markov-folyamaton stacionárius Markov-folyamatot értenek. Mi is így fogunk tenni a továbbiakban. A stacionárius Markov-folyamatok definiciója a következő:

Stacionárius Markov-folyamat definiciója. Egy X_{t}, t ≥ 0, (vagy X_{t}, F_{t}) általánosított) folytonos idejű Markov-folyamatot folytonos idejű stacionárius Markovfolyamatnak nevezünk, ha a folyamat átmenetvalószínűségei teljesítik a P s, t(x, A) = P_{t−s}(x, A) azonosságot, minden 0 ≤ s ≤ t számpárra, azaz a P_{s,t}(x, A) átmenetvalószínűség csak az s és t időpont között eltelt időtől függ.

Egy X_{n}, n = 0, 1, …, (vagy X_{n}, F_{n}) általánosított) diszkrét idejű Markov-folyama-tot diszkrét idejű stacionárius Markov-folyamatnak nevezünk, ha az átmenetvalószínűségei teljesítik a P_{m,n}(x, A) = P_{n−m}(x, A) azonosságot minden 0 ≤ m ≤ n számpárra, azaz a P_{m,n}(x, A) átmenetvalószínűség csak az m és n időpont között eltelt időtől függ.

Stacionárius Markov-folyamatok átmenetvalószínűségeinek definiciója. Egy értékeit valamely (E, E) mérhető téren felvevő X_{t}, t ≥ 0, folytonos idejű stacionárius Markov-folyamat átmenetvalószínűségén a

P (t, x, A) = P (X_{u+t} ∈ A|X_{u} = x) = P_{u,u+t}(x, A), t ≥ 0, x ∈ E, A ∈ A,

feltételes valószínűségek rendszerét értjük, amely a stacionárius tulajdonság miatt nem függ az u ≥ 0 paramétertől.

Hasonlóképpen egy értékeit valamely (E, E) mérhető téren felvevő X_{n}, n = 0, 1, …, diszkrét idejű stacionárius Markov-folyamat átmenetvalószínűségén a

P (n, x, A) = P (X_{n+m} ∈ A|X_{m} = x) = P_{m,n+m}(x, A), n = 0, 1, …, x ∈ E, A ∈ A,

feltételes valószínűségek rendszerét értjük, amely a stacionárius tulajdonság miatt nem függ az m = 1, 2, … paramétertől.

Megjegyzés: A stacionárius Markov-folyamatokra az előbb bevezetett P (t, x, A) és P (n, x, A), x ∈ E, A ∈ E, n = 0, 1, 2, …, átmenetvalószínűségek teljesítik a következő Chapman–Kolmogorov egyenletnek nevezett azonosságokat:

P (s + t, x, A) = ∫ P (t, y, A)P (s, x, dy) ha s ≥ 0 és t ≥ 0.  (1)

és

P (m + n, x, A) = ∫ P (n, y, A)P (m, x, dy) minden m = 0, 1, …
és n = 0, 1, … számra.  (2)

Ezenkívül a P (t, x, A) illetve P (n, x, A) átmenetvalószínűségek teljesítik az alábbi tulajdonságokat: Minden rögzített t illetve n időpontra és x ∈ E pontra P (t, x, ·) illetve P (n, x, ·) valószínűségi mérték. Minden t illetve n időpontra és A ∈ E halmazra P (t, ·, A) illetve P (n, ·, A) mérhető függvények az (E, E) téren. Továbbá mind a folytonos mind a diszkrét idejű Markov-folyamatok esetén teljesül a P (0, x, A) = 1, ha x ∈ A és P (0, x, A) = 0, ha x ∉ A reláció. A felsorolt tulajdonságok jellemzik is a stacionárius Markov-folyamatokat, azaz minden (értékeit szép topológiai tulajdonságokkal rendelkező téren, (például teljes szeparábilis metrikus téren) felvevő stacionárius Markov-folyamathoz meg lehet adni a feltételes eloszlásokat a fenti tulajdonságokkal rendelkező átmenetvalószínűségekkel.

Valójában érvényes a Chapman–Kolmogorov egyenlet következő általánosabb alakja is nem feltéltenül stacionárius folyamatokra:

P_{s,t}(x, A) = ∫ P_{u,t}(y, A)P_{s,u}(x, dy) ha 0 ≤ s ≤ u ≤ t.  (1′)

és

P_{m,n}(x, A) = ∫ P_{l,n}(y, A)P_{m,l}(x, dy) minden 0 ≤ m ≤ l ≤ n, egész számhármasra. (2′)

A fent megfogalmazott, az irodalomban Chapman–Kolmogorov egyenletnek nevezett (1) illetve (2) azonosságok (és azok (1′) illetve (2′) általánosításai) nagyon természetes állítások. A Chapman–Kolmogorov egyenlet tekinthető a Markov-folyamatok elméletében a legfontosabb azonosságnak. Ennek precíz bizonyításához szükség van arra, hogy általános (Radon–Nykodim deriváltak segítségével definiált) feltételes valószínűségekkel számoljunk, illetve fel kell használni azt a tényt, hogy az átmenetvalószínűségek teljesítik a (2) képlet után megfogalmazott tulajdonságokat. Mivel az ilyen technikai részletek tárgyalását minimálisra kívánom szorítani, ezért ezt a számolást csak a kiegészítésben ismertetem. A számunkra legfontosabb esetben, amikor Markov-láncokat tekintünk, elvégzem ezt a lényegesen egyszerűbb számolást az előadás fő részében.

Legyen adva egy diszkrét idejű Markov-folyamat, amely értékeit valamely (E, E) téren veszi fel. A (2) reláció szerint a Markov-folyamat P (x, A) átmenetvalószínűségei teljesítik a

P (n + 1, x, A) = ∫ P (1, y, A)P (n, x, dy) minden n = 0, 1, … számra.  (3)

azonosságot. Ez azt jelenti, hogy ha megadjuk a P (1, x, A) átmenetvalószínűségeket, akkor n szerinti indukcióval ki tudjuk számolni a P (n, x, A) átmenetvalószínűségeket minden n = 0, 1, … számra.

Be lehet látni, hogy igaz a következő állítás. Ha P (x, A), x ∈ E, A ∈ E, olyan függvényrendszer egy (E, E) mérhető téren, amely minden rögzített x ∈ E pontra valószínűségi mérték és minden A ∈ A halmazra mérhető függvény az (E, E) téren, akkor a következő definicióval egy diszkrét idejű Markov-folyamat átmenetvalószínűségeit definiáljuk, amelyek teljesítik a (2) Chapman–Kolmogorov egyenletet.

Legyen P (0, x, A) = 1, ha x ∈ A és P (0, x, A) = 0, ha x ∉ A, P (1, x, A) = P (x, A), és n ≥ 2 indexekre definiáljuk a P (n, x, A) n-lépéses átmenetvalószínűségeket n szerinti indukcióval. A fenti inkább technikai jellegű, számunkra inkább elvi jelentőségű állítás bizonyítását elhagyom.

A Markov-folyamatok tulajdonságairól szóló állítások összefoglalása. Legyen adva egy (X_{t}, F_{t}) t ≥ 0, folytonos vagy egy (X_{n}, F_{n}), n = 0, 1, 2, …, diszkrét idejű Markov-folyamat. (Feltesszük, hogy ez a Markov-folyamat egy szép topológiai tulajdonságokkal rendelkező téren veszi fel az értékeit.) Ekkor ennek a Markov-folyamatnak léteznek olyan P_{s,t}(x, A) illetve P_{m,n}(x, A) átmenetvalószínűségei, amelyek teljesítik a 3. megjegyzésben megfogalmazott a), b) és c) tulajdonságokat valamint az (1′) illetve (2′) formulában megfogalmazott Chapman–Kolmogorov egyenlőséget is.

Igaz a fenti állítás következő itt nem bizonyított megfordítása is. Legyen adva P_{s,t}(x, A), 0 ≤ s ≤ t vagy P_{m,n}(x, A), ≤ m ≤ n függvényeknek egy olyan rendszere, amely teljesíti a 3. megjegyzésben megfogalmazott a), b) és c) tulajdonságokat és az (1′) illetve (2′) formulában megfogalmazott Chapman–Kolmogorov egyenlőséget. Ez úgy értendő, hogy adva van egy (E, E) tér, ahol E egy az E téren definiált σ-algebra, és a P_{s,t}(x, A) illetve P_{m,n}(x, A) függvények minden x ∈ E pontra A ∈ E halmazra és 0 ≤ s ≤ t valós, illetve 0 ≤ m ≤ n egész számokra definiálva vannak. Ekkor létezik olyan X_{t}, t ≥ 0 folytonos, illetve olyan X_{n}, n = 0, 1, 2, … diszkrét idejű, értékeit az (E, E) térben felvevő Markov-folyamat, amelynek a P_{s,t}(x, A) illetve a P_{m,n}(x, A) függvények az átmenetvalószínűségei. Sőt, a 0 időpontbeli X_{0} valószínűségi változó eloszlását tetszőleges módon előírhatjuk.

A következő definicióban bizonyos az irodalomban elterjedt szóhasználatot vezetünk be.

Markov-láncok definiciója. Ha egy (folytonos vagy diszkrét idejű Markov-folyamat egy (E, E) mérhető téren veszi fel az értékeit, akkor ezt az (E, E) teret a Markov-folyamat állapotterének hívjuk. Egy olyan Markov folyamatot, amelynek állapottere egy véges vagy megszámlálható számosságú halmaz (a diszkrét topológiával) Markov-láncnak nevezzük.

Feladat: Ha (X_{0}, X_{1}, …) olyan a természetes számokkal indexelt sztochasztikus folyamat egy megszámlálható számosságú (E, E) állapottéren, amely teljesíti az

P (X_{n+1} = E_{j_{n+1}}|X_{n} = E_{j_{n}}, …, X_{0} = E_{j_{0}}) = P (X_{n+1} = E_{j_{n+1}}|X_{n} = E_{j_{n}})
P (X_{1} = E_{j_{n+1}}|X_{0} = E_{j_{n}})

azonosságot, akkor (X_{0}, X_{1}, …) (stacionárius) Markov-lánc, amelynek egy lépéses átmenetvalószínűségeit a P (j, k) = P (X_{1} = E_{j}|X_{0} = E_{k}) képlet adja meg.

(A feladat tartalma mindössze annyi, hogy a feltételes valószínűségekre a Markovfolyamatok definiciójb́an kirótt feltétel az adott esetben ezt az azonosságot jelenti.)

A továbbiakban (stacionárius) Markov-láncokkal fogunk foglalkozni, azokon belül is elsősorban diszkrét idejű Markov-láncokkal. A következő jelölést fogom használni. Jelölje az állapotokat E_{1}, E_{2}, …, és legyen P (n, j, k) = P (X_{n+m} = E_{k}|X_{m} = E_{j}), m = 1, 2, …, n = 0, 1, 2, … azaz P (n, j, k) annak feltételes valószínűsége, hogy a Markov-lánc az n + m időpontban az E_{k} állapotba jut, feltéve, hogy az m időpontban az E_{j} állapotban volt. Használjuk továbbá a P (j, k) = P (1, j, k) jelölést, azaz az 1lépéses P (1, j, k) átmenetvalószínűségekben hagyjuk el az 1 koordinátát. Felírom a Chapman–Kolmogorov egyenlőséget Markov-láncokra a fent bevezetett jelöléssel.

P (n + m, j, k) = ∑_{l} P (n, j, l)P (m, l, k)  (4)

ahol az összegzés végigfut az összes olyan l indexen, amelyre az E_{l} állapot létezik. Jelöléseink szerint vagy létezik egy olyan N pozitív egész szám, hogy E_{1}, …, E_{N} az összes lehetséges állapotok halmaza, és ekkor 1 ≤ l ≤ N az összegzés a (4) formulában, vagy megszámlálható sok E_{1}, E_{2}, … a lehetséges állapotok halmaza, és ekkor az összegezés 1 ≤ l < ∞ indexelésre történik.

Lemma. Egy diszkrét idejű stacionárius Markov-lánc teljesíti a (4) formulában megfogalmazott Chapman–Kolmogorov egyenlőséget.

A lemma bizonyítása.

P (n + m, j, k) = P (X_{n+m} = E_{k}|X_{0} = E_{j})

= ∑_{l} P (X_{n+m} = E_{k}, X_{n} = E_{l}|X_{0} = E_{j})

= ∑_{l} P (X_{n+m} = E_{k}, |X_{n} = E_{l}, X_{0} = E_{j})P (X_{n} = E_{l}|X_{0} = E_{j})

= ∑_{l} P (X_{n+m} = E_{k}, |X_{n} = E_{l})P (X_{n} = E_{l}|X_{0} = E_{j})

= ∑_{l} P (m, l, k)P (n, j, l).

(E számolásban felhasználtuk a Markov tulajdonságból következő

P (X_{n+m} = E_{k}|X_{n} = E_{l}, X_{0} = E_{j}) = P (X_{n+m} = E_{k}|X_{n} = E_{l})

azonosságot.)

Feladat: Bizonyítsuk be a Chapman–Kolmogorov egyenlőséget diszkrét idejű nem feltétlenül stacionárius Markov-láncokra. Részletesebben megfogalmazva legyenek egy E_{1}, E_{2}, … állapotokkal rendelkező diszkrét idejű X_{0}, X_{1}, … Markov-lánc átmenetvalószínűségei P_{m,n}(j, k) = E(X_{n} = E_{k}|X_{m} = E_{j}), n ≥ m ≥ 0, j, k = 0, 1, . . .. Minden m ≤ r ≤ n időpontra igaz a következő azonosság:

P_{m,n}(j, k) = ∑_{l} P_{m,r}(j, l)P_{r,n}(l, k).

Ha adva van egy (véges sok), N állapotot felvevő Markov-lánc, akkor ennek 1lépéses átmenetvalószínűségeinek rendszerén a P (j, k), 1 ≤ j, k ≤ N, 1 lépéses átmenetvalószínűségeinek összességét, n-lépéses átmenetvalószínűségeinek rendszerén, n = 1, 2, …, pedig a P (n, j, k) valószínűségeinek összességét értjük. Természetes módon hozzárendelhetjük egy ilyen véges sok, N állapotot felvevő Markov-lánc átmenetvalószínűségeinek P (j, k) rendszeréhez azt az N ×N méretű négyzetes Π mátrixot, amelynek j-ik sorának és k-ik oszlopának a metszetében a P (j, k) szám áll. Hasonlóan feleltessük meg egy ilyen mátrix n lépéses átmenet valószínűségei P (n, j, k) rendszerének azt a Π_{n} mátrixot, amelynek j-ik sorának és l-ik oszlopának a metszetében a P (n, j, k) szám áll. Érdemes bevezetni a sztochasztikus mátrix fogalmát, amely leírja az ily módon létrejövő mátrixokat.

Sztochasztikus mátrixok definiciója. Egy N × N méretű (P (j, k)), 1 ≤ j, k ≤ N, mátrixot sztochasztikus mátrixnak nevezünk, ha P (j, k) ≥ 0, 1 ≤ j, k ≤ N, a mátrix

minden elemére, és ∑_{k=1}^{N} P (j, k) = 1, 1 ≤ j ≤ N, azaz a mátrix minden sorösszege eggyel

egyenlő.

A következő egyszerű észrevétel nagyon hasznos véges állapotterű Markov-láncok vizsgálatában.

Fontos észrevétel. A fent ismertetett megfeleltetés kölcsönösen egyértelmű megfeleltetést létesít véges állapotterű Markov-láncok 1-lépéses átmenetvalószínűségeinek rendszere és a sztochasztikus mátrixok között. Továbbá, a Markov-láncokról szóló (4) formulában megfogalmazott Chapman–Kolmogorov azonosságából következik, hogy ha egy mátrix 1-lépéses átmenetvalószínűségeinek rendszeréhez hozzárendelt mátrix Π, és az nlépéses átmenetvalószínűségeinek rendszeréhez hozzárendelt mátrix Π_{n}, akkor Π_{n} = Π^{n}, ahol Π^{n} a Π mátrix n-ik hatványát jelöli a szokásos mátrix szorzás értelmében.

A ‘Fontos észrevétel’ lehetővé teszi, hogy mátrix elméleti eredmények segítségével fontos eredményeket állapítsunk meg véges állapotterű Markov-láncok viselkedéséről. Ezt a módszert csak később fogom tárgyalni. A továbbiakban elsősorban a mind véges mind végtelen állapotterű (stacionárius) Markov-láncok viselkedéséről szóló alapvető eredmények ismertetésére fogok koncentrálni.

Mutatok néhány példát Markov-láncokra és folyamatokra.

Néhány érdekes Markov-folyamat és Markov-lánc definiciója.

1.) Tekintsünk egy véletlen bolyonást a d-dimenziós rácson, azaz a

Z = {(j_{1}, …, j_{d}): −∞ < j_{s} < ∞, j_{s} egész szám, 1 ≤ s ≤ d}

halmazon. Ezt úgy definiáljuk, hogy ha a bolyongást végző részecske az n-ik időpontban a Z rács valamelyik pontjában tartózkodik, akkor a múltbeli viselkedéstől függetlenül egyforma, azaz \frac{1}{2d} valószínűséggel átugrik valamelyik szomszédos rácspontba. Azaz, ha S_{n}-nel jelöljük a részecske tartozkódási helyét az n időpntban, akkor az S_{n} − S_{n−1} valószínűségi változók, n = 1, 2, …, függetlenek, és P (S_{n} − S_{n−1} = e_{j}) = P (S_{n} − S_{n−1} = −e_{j}) = \frac{1}{2d} minden n = 1, 2, …, 1 ≤ j ≤ d számra, ahol e_{j} jelöli azt a vektort, amelynek j-ik koordinátája 1, és az összes többi koordinátája nulla. A definició teljessége érdekében még definiálnunk kell az S_{0} mennyiséget is. Legyen P (S_{0} = x) = 1, ahol x ∈ Z a d-dimenziós tér valamely rögzített rácspontja.

2.) Véletlen bolyongás a nem negatív egész számokon, a 0-val, mint elnyelő fallal. Az előző példához hasonló modell a d = 1 esetben, amely bolyongást valamely x ≥ 0 pontban indítunk el, azzal a különbséggel, hogy amennyiben a bolyongás elér a nullába, akkor örökre ottmarad. Ez képletekben azt jelenti, hogy az átmenetvalószínűségek a P (j, j + 1) = P (j, j − 1) = \frac{1}{2}, ha j ≥ 1, és P (0, 0) = 1 képletekkel adhatóak meg.

3.) Véletlen bolyongás a nem negatív egész számokon, a 0-val, mint visszaverő fallal. Az előző példához hasonló modell azzal a különbséggel, hogy amennyiben a bolyongás elér a nullába, akkor onnan visszaverődik. Ez képletekben azt jelenti, hogy az átmenetvalószínűségek a P (j, j + 1) = P (j, j − 1) = \frac{1}{2}, ha j ≥ 1, és P (0, 1) = 1 képletekkel adhatóak meg.

4.) Véletlen bolyongás a modulo n csoporton. Legyen a Markov-lánc állapottere az {1, …, n} halmaz, valamely n ≥ 2 pozitív egész számmal. Legyenek a Markov-lánc átmenetvalószínűségei P (i, i + 1) = P (i, i − 1) = \frac{1}{2}, ahol az összeadás és kivonás modulo n értendő.

5.) A diffuzió Ehrenfest modellje. Ez véges állapotterű Markov-lánc. E Markov-lánc függ egy N paramétertől, amely pozitív egész szám. Ha ez a paraméter N, akkor a modellben N +1 állapot van, E_{0}, E_{1}, …, E_{N}, és az átmenetvalószínűségek P (k, k− 1) = \frac{k}{N}, P (k, k + 1) = \frac{N−k}{N}, ha 1 ≤ k ≤ N, és P (0, 1) = 1, P (N, N − 1) = 0. E képletek szemléletes tartalma a következő: Legyen N részecske, amelyek mindegyike két urna valamelyikében van, és jelölje E_{k} azt az eseményt, hogy az első urnában k részecske, a második urnában N − k részecske van. Minden egyes időpontban, kiválasztunk véletlenül egy részecskét, mindegyik részecskét egyforma valószínűséggel, és azt áthelyezzük a másik urnába. Ekkor, ha az első urnában k golyó van, akkor P (k, k − 1) = \frac{k}{N} annak a valószínűsége, hogy az áthelyezendő részecskét az első urnából választottuk, ezért az első urnában levő részecskék száma eggyel csökken, és P (k, k + 1) = \frac{N−k}{N}, annak a valószínűsége, hogy az áthelyezendő részecskét a második urnából választottuk, ezért az első urnában levő részecskék száma eggyel nő.

6.) Modell egy szerkezet élettartamára. Legyen adva egy Markov-lánc a végtelen E_{1}, E_{2}, … állapottéren, amelynek átmenetvalószínűségeit valamely p_{1}, p_{2}, …, 0 ≤ p_{k} ≤ 1, és q_{k} = 1 − p_{k}, k = 1, 2, …, számsorozat segítségével határozzuk meg a következő módon: P (k, k+1) = p_{k}, P (k, 1) = q_{k}, k = 1, 2, . . .. E modell szemléletes tartalma a következő: Legyen adva egy szerkezet, amelyet minden időpontban, ha nem romlik el, akkor tovább használunk, és életkora egy egységgel nő. Ha elromlik, akkor kicseréljük egy új szerkezetre, amelynek életkora 1. Jelölje X_{n} azt a valószínűségi változót, amely megadja azt, hogy mennyi az n időpontban használt szerkezet életkora.

A következő példa az 1. példában szereplő bolyongás természetes általánosítása.

7.) Legyen X_{1}, X_{2}, …, független egyforma eloszlású valószínűségi változók sorozata, amelyek értékeiket valamely E lineáris térben veszik fel. Tegyük fel továbbá, hogy ezek az X_{1}, X_{2}, …, valószínűségi változók egy megszámlálható, T = {t_{1}, t_{2}, … },

halmazon veszik fel az értékeiket, azaz P (X_{1} ∉ T) = 0. Definiáljuk az S_{n} = ∑_{j=1}^{n} X_{j},

n = 1, 2, …, részletösszegeket, és az S ⊂ E (megszámlálható) halmazt melynek

elemei azok az s ∈ E elemek, amelyek előállíthatóak s = ∑_{j=1}^{k} t_{j}, k = 1, 2, …, t_{j} ∈ T,

1 ≤ j ≤ k, alakban. Ekkor S_{1}, S_{2}, …, Markov-lánc az S állapottéren, amelynek átmenetvalószínűségeit a P (S_{n+1} = s̄|S_{n} = s) = P (X_{1} = s̄ − s), s, s̄ ∈ S, képlet adja meg. Ugyancsak Markov-láncot alkotnak ugyanezen a téren és ugyanezekkel az átmenetvaószínűségekkel az S̄_{n} = S_{n} + t_{j}, n = 1, 2, …, sorozatok is, ahol t_{j} ∈ T tetszőleges szám.

Valóban,

P (S_{n+1} = s_{n+1}|S_{n} = s_{n}, …, S_{1} = s_{1}) = \frac{P (S_{n+1} = s_{n+1}, S_{n} = s_{n}, …, S_{1} = s_{1})}{P (, S_{n} = s_{n}, …, S_{1} = s_{1})}

= \frac{P (X_{n+1} = s_{n+1} − s_{n}, X_{n} = s_{n} − s_{n−1}, …, X_{1} = s_{1})}{P (X_{n} = s_{n} − s_{n−1}, …, X_{1} = s_{1})}

= P (X_{n+1} = s_{n+1} − s_{n}) = P (X_{1} = s_{n+1} − s_{n}).

Érvényes a 7.) példa alábbi természetes általánosítása tetszőleges (nem feltétlenül megszámlálható sok értéket felvevő) valószínűségi változók részletösszegeire. Az általánosítás bizonyítása annyiban nehezebb, hogy abban általános értelemben vett feltételes valószínűségekkel kell számolni.

8.) Legyenek X_{1}, X_{2}, …, független, egyforma eloszlású valószínűségi változók, amelyek

értékeiket valamely (E, E) lineáris térben veszik fel. Ekkor az S_{n} = ∑_{j=1}^{n} X_{j}, j =

1, 2, …, részletösszegek (stacionárius) Markov-folyamatot alkotnak az (E, E) téren, amelynek 1 lépéses átmenetvalószínűségeit a P (1, x, A) = P (S_{n+1} ∈ A|S_{n} = x) = P (X_{1} ∈ A − x) képlet adja meg.

Nem kötelező feladat. Bizonyítsuk be, hogy a 8. példa állítása valóban igaz.

Külön feladatban megfogalmazom azt a feltételes eloszlásokról szóló állítást, amely az előző feladat megoldásának a lényege.

Feladat: Legyenek X_{1}, …, X_{k}, Y független valószínűségi változók, amelyek értékeiket valamely (E, E) téren veszik fel, f(x_{1}, …, x_{k+1}) egy k-változós mérhető (korlátos) függvény az (E, E) téren. Ekkor

E(f(X_{1}, …, X_{k}, Y)|X_{1} = x_{1}, …, X_{k} = x_{k}) = Ef(x_{1}, …, x_{k}, Y).

Vegyük észre, hogy az előző feladat eredményéből, (amely egyébként tekinthető a Fubini tétel egy verziójának) következik a 2. példa állítása. Valóban, ezt felhasználva meg lehet mutatni, hogy

P (S_{n+1} ∈ A|S_{1} = x_{1}, S_{2} = x_{2}, …, S_{n} = x_{n}) = P (X_{1} + ⋯ + X_{n} + Y ∈ A|X_{1} = x_{1}, X_{2} = x_{2} − x_{2}, …, X_{n} = x_{n} − x_{n−1})

= P (x_{1} + (x_{2} − x_{1}) + ⋯ + (x_{n} − x_{n−1}) + Y ∈ A) = P (X_{1} ∈ A − x_{n})

ahol, X_{1}, …, X_{n}, Y) független egyforma eloszlású valószínűségi változók, melyek értékeiket valamely (E, E) lineáris térben veszik fel.

9.) Végül mutatok példát valószínűségi változók egy olyan sorozatára, amely nem alkot Markov-láncot. Legyen adva egy urna és benne mondjuk 5 piros és 3 fehér golyó. Kihúzunk az urnából egy golyót véletlenszerűen, majd dobjuk vissza azt az urnába egy ugyanolyan színű golyóval együtt. Folytassuk ezt a procedurát a végtelenségig, és definiáljuk az X_{1}, X_{2}, … valószínűségi változókat úgy, hogy X_{n} = 1, ha a n-ik húzáskor kihúzott golyó színe piros, és X_{n} = 0, ha az n-ik húzáskor kihúzott golyó színe fehér. Ekkor nyílvánvalóan P (X_{n} = 1|X_{1} = 1, X_{2} = 1, …, X_{n−1} = 1) > P (X_{n} = 1|X_{n−1} = 1), mert ha minden eddigi húzás eredménye piros színű golyó volt, akkor az urnában levő piros golyók számát növeltük, ezért nagyobb annak a valószínűsége, hogy a következő húzásban is piros golyót húzunk.

Kiegészítés.

Megfogalmazok és bebizonyítok egy lemmát, amelynek fő mondanivalója az a (B) azonosság, amely szerint egy stacionárius Markov-folyamat teljesíti a Chapman–Kolmogorov egyenlőséget. Valójában ez egy általánosabb változata a Chapman–Kolmogorov egyenlőségnek, amely nem feltétlenül stacionárius Markov folyamatokra is érvényes.

Stacionárius Markov-folyamatok esetében P_{s,t}(x, A) = P_{t−s}(x, A), P_{u,t}(y, A) = P_{t−u}(y, A), P_{s,u}(x, dy) = P_{u−s}(x, dy), és a (B) reláció megegyezik a Chapman–Kolmogorov egyenlőséggel.

Lemma. Legyen (X_{t}, F_{t}), t ≥ 0, Markov-folyamat valamely a (E, E) mérhető téren valamely P_{s,t}(x, A) a 3. megjegyzésban szereplő a) b) és c) tulajdonságot teljesítő átmenetvalószínűségekkel. Legyen f(y), korlátos, mérhető függvény az (E, E) téren. Ekkor

E(f(X_{u})|X_{s} = x) = ∫ f(y)P_{s,u}(x, dy) ha u ≥ s  (A)

és

P_{s,t}(x, A) = ∫ P_{u,t}(y, A)P_{s,u}(x, dy) ha s ≤ u ≤ t  (B)

Bizonyítás: Ha az f függvény egy A halmaz indikátor függvénye, akkor könnyen látható, hogy az (A) formula érvényes. Mivel a kifejezés mindkét oldala az f függvény lináris függvénye, ezért az azonosság érvényes halmazok indikátor függvényeinek lineáris kombinációira is. Ezután ilyen függvényekkel végrehajtott közelítések segítségével kapjuk, hogy az (A) reláció tetszőleges f függvényre érvényes. Az (A) formula szemléletesen azt mondja ki, hogy feltételes várható értéket úgy számolhatunk ki feltételes eloszlásfüggvények segítségével, mint várható értéket eloszásfüggvények segítségével.

A (B) formula bizonyításában felhasználhatjuk, hogy a Markov tulajdonság és a feltételes várható érték tulajdonságai miatt

P_{s,t}(x, A) = P (X_{t} ∈ A|X_{s} = x) = E(E(I_{{X_{t}∈A}}|X_{s}, X_{u})|X_{s} = x)
= E(E(I_{{X_{t}∈A}}|X_{u})|X_{s} = x) = E(E(f(X_{u})|X_{s} = x),

ahol I_{A} egy A halmaz indikátorfüggvényét jelöli. Az utolsó lépésben használtuk ki a Markov tulajdonságot, amely szerint E(I_{{X_{t}∈A}}|X_{s}, X_{u}) = E(I_{{X_{t}∈A}}|X_{u}), ha u ≥ s.

Vezessük be az f(y) = P (X_{t} ∈ A|X_{u} = y) = P_{u,t}(A, y) függvényt. Az előző azonosság és az A) reláció alapján

P_{s,t}(x, A) = E(E(f(X_{u})|X_{s} = x) = ∫ P_{u,t}(A, y)P_{s,u}(dy, x),

amint állítottuk.

Kimondom e tétel diszkrét idejű megfelelőjét, amelyet hasonlóan bizonyíthatunk.

Lemma. Legyen (X_{n}, F_{n}), n = 0, 1, …, Markov-folyamat valamely a (E, E) mérhető téren valamely P_{m,n}(x, A) a 3. megjegyzésban szereplő a) b) és c) tulajdonságot teljesítő átmenetvalószínűségekkel. Legyen f(y), korlátos, mérhető függvény az (E, E) téren. Ekkor

E(f(X_{n})|X_{m} = x) = ∫ f(y)P_{m,n}(x, dy) ha n ≥ m  (A′)

és

P_{m,n}(x, A) = ∫ P_{k,n}(y, A)P_{m,k}(x, dy) ha m ≤ k ≤ n.  (B′)

Bizonyítás nélkül közlöm a következő eredményt.

Tétel. Legyen adva egy a 3. megjegyzésben felsorolt a), b) és c) tulajdonságokat teljesítő P_{s,t}(x, A) illetve P_{m,n}(x, A) függvény amely teljesíti az (e) illetve (e′) tulajdonságot is. Legyen továbbá adva valamely P_{0} valószínűségi mérték az (E, E) téren. Ekkor létezik olyan időben folytonos Markov-folyamat, amelyre P (X_{0} ∈ A) = P_{0}(A) és P (X_{t} ∈ A|X_{s} = x) = P_{s,t}(x, A), x ∈ E, A ∈ E, m ≤ n választással. Létezik olyan időben diszkrét Markov-folyamat, amelyre P (X_{0} ∈ A) = P_{0}(A), és P (X_{n} ∈ A|X_{m} = x) = P_{s,t}(x, A) minden x ∈ E, A ∈ E, 0 ≤ m ≤ n választással.