Diszkrét idejű Markov láncok vizsgálata.

Tekintsünk egy diszkrét idejű X_{0}, X_{1}, … Markov láncot P (j, k) = P (X_{n+1} = E_{k}|X_{n} = j), n = 1, 2, …, átmenetvalószínűségekkel egy (Ω, A, P) valószínűségi mezőn, amely bizonyos E_{1}, E_{2}, … értékeket vesz fel. Elsősorban a következő kérdésekre vagyunk kiváncsiak.

a) Milyen P (j, k) átmenetvalószínűségek esetében mondhatjuk azt, hogy a Markov lánc az E_{j} állapotból kiindulva 1 valószínűséggel (végtelen sokszor) visszatér az E_{j} állapotba? (Mint látni fogjuk, ha a Markov lánc 1 valószínűséggel visszatér az E_{j} állapotba, akkor az is igaz, hogy 1 valószínűséggel végtelen sokszor visszatér oda.)

b) Tekintsük egy X_{0}, X_{1}, … Markov lánc E_{j} állapotát, és a P (n, j, j) = P (X_{n} = E_{j}|X_{0} = E_{j}) n-lépéses átmenetvalószínűségeket. Létezik-e a lim_{n→∞} P (n, j, j) határérték? Ha létezik meg tudjuk-e adni ezt a határértéket viszonylag egyszerű módon? Léteznek-e és jellemezhetőek-e a lim_{n→∞} P (n, j, k) = lim_{n→∞} P (X_{n} = E_{k}|X_{0} = E_{j}) határértékek?

c) Mondhatjuk-e, hogy amennyiben E_{j} és E_{k} két olyan állapot, amelyekre teljesül az a tulajdonság, hogy a Markov lánc pozitív valószínűséggel jut el az az E_{j} állapotból az E_{k} állapotba, illetve az E_{k} állapotból az E_{j} állapotba (alkalmas számú lépésben) akkor a Markov láncot az E_{j} illetve E_{k} állapotból elindítva egyszerre igaz vagy nem igaz az, hogy a Markov lánc végtelen sokszor visszatér illetve csak véges sok alkalmommal tér vissza oda; egyszerre léteznek vagy nem léteznek pozitív lim_{n→∞} P (n, j, j) > 0 és lim_{n→∞} P (n, k, k) > 0 határértékek? Általánosabban, fel tudjuk-e osztani a Markov lánc állapotterét annak alapján, hogy mely állapotból mely állapotba lehet eljutni pozitív valószínűséggel természetes módon osztályokra úgy, hogy az egy osztályban levő elemeknek sok fontos hasonló tulajdonsága van?

E kérdések tárgyalása előtt érdemes bevezetni néhány fogalmat és mennyiséget.

Markov lánc rekurrens és tranziens állapotának fogalma. Legyen X_{0}, X_{1}, … egy Markov lánc egy E = {E_{1}, E_{2}, … } állapottéren. Azt mondjuk, hogy a Markov lánc E_{j} állapota rekurrens, ha a Markov láncot az E_{j} állapotból indítva, azaz ha P (X_{0} = E_{j}) = 1, a Markov lánc 1 valószínűséggel visszatér valamikor az E_{j} állapotba. Ez azt jelenti, hogy

P ( ⋃_{n=1}^{∞}{ω: X_{n}(ω) = E_{j}}) = 1.

A Markov lánc E_{j} állapota tranziens, ha a Markov láncot az E_{j} állapotból indítva, az 1-nél kisebb valószínűséggel tér vissza valamikor az E_{j} állapotba, azaz

P ( ⋃_{n=1}^{∞}{ω: X_{n}(ω) = E_{j}}) < 1.

Markov lánc egy állapotának a periódusa. Legyen X_{0}, X_{1}, … egy Markov lánc egy E = {E_{1}, E_{2}, … }, állapottéren, és jelölje P (n, j, k) = P (X_{n} = E_{k}|X_{0} = E_{j}), az n-lépéses átmenetvalószínűségeket. Vezessük be, az A(j) = {n: P (n, j, j) > 0}, halmazokat, azaz azon n indexek halmazát, amelyekre a P (n, j, j) átmenetvalószínűség szigorúan pozitív. Azt mondjuk, hogy a Markov lánc E_{j} állapotának periódusa l, ha az A(j) halmazban szereplő számok legnagyobb közös osztója l. Ha ez a legnagyobb közös osztó 1, akkor a Markov lánc E_{j} állapotát aperiódikusnak nevezzük. (Ha a A(j) halmaz üres, azaz a Markov lánc 1 valószínűséggel soha nem tér vissza az E_{j} állapotba, akkor nem definiáljuk az E_{j} halmaz periódusát.

(Egyszerű) feladat. Egy a d-dimenziós tér egész koordiátájú pontjaiból álló rácson történő bolyongás periódusa 2.

Legyen X_{0}, X_{1}, … Markov lánc egy E = {E_{1}, E_{2}, … }, állapottéren, és jelölje P (n, j, k) = P (X_{n} = E_{k}|X_{0} = E_{j}), az n-lépéses átmenetvalószínűségeket. Vezessük be az alábbi mennyiségeket:

f_{j}(n) = P (X_{n} = E_{j}, X_{m} ≠ E_{j}, ha 1 ≤ m < n|X_{0} = E_{j}), n = 1, 2, …,  (1)

azaz f_{j}(n) annak a valószínűsége, hogy az E_{j} állapotból indított Markov lánc n lépés múlva tér vissza először az E_{j} állapotba. Nyílván az E_{j} állapot akkor és csak akkor

rekurrens, ha ∑_{n=1}^{∞} f_{j}(n) = 1. Ha az E_{j} állapot rekurrens, akkor vezessük be a

μ_{j} = ∑_{n=1}^{∞} nf_{j}(n)  (2)

mennyiségeket is. A μ_{j} mennyiség egyenlő az E_{j} állapotba való első visszatérés idejének a várható értékével. Mint majd látni fogjuk, a μ_{j} mennyiség szoros kapcsolatban van a (létező) lim_{n→∞} P (n, j, j) határértékkel.

Vezessük be a

P_{j}(x) = ∑_{n=0}^{∞} P (n, j, j)x^{n}, F_{j}(x) = ∑_{n=0}^{∞} f_{j}(n)x^{n}  (3)

hatványsorokat, ahol P (0, j, j) = 1, f_{j}(0) = 0 definició szerint. Ezek a hatványsorok konvergálnak |x| < 1 esetében. Vegyük észre, hogy P (n, j, j) = f_{j}(n)P (0, j, j) + f_{j}(n − 1)P (1, j, j)+f_{j}(2)P (2, j, j)+⋯+f_{j}(1)P (n−1, j, j) minden n = 1, 2, … számra. Innen, illetve a P (0, j, j) = 1 relációból következik, hogy

F_{j}(x)P_{j}(x) = P_{j}(x) − 1.  (4)

A (4) azonosság segítségével be fogjuk látni a következő tételt.

Tétel Markov láncok rekurrens és tranziens állapotainak jellemzéséről. Legyen X_{0}, X_{1}, …, Markov lánc, E_{1}, E_{2}, … állapotokkal, és jelölje P (n, j, k) = P (X_{n} = E_{k}|X_{0} = E_{j}) a Markov lánc átmenetvalószínűségeit. A Markov lánc E_{j} állapota rekurrens, ha

∑_{n=1}^{∞} P (n, j, j) = ∞,

tranziens, ha

∑_{n=1}^{∞} P (n, j, j) < ∞.

Ha az E_{j} állapot rekurrens, akkor a Markov lánc 1 valószínűséggel végtelen sokszor tér vissza az E_{j} állapotba. Ha az E_{j} állapot tranziens, akkor a Markov lánc 1 valószínűséggel csak véges sokszor tér vissza az E_{j} állapotba.

Bizonyítás: A (4) reláció, illetve annak a ténynek az alapján, hogy F_{j}(x) és P_{j}(x) nem negatív együtthatós hatványsorok, kapjuk, hogy minden N ≥ 1 számra

∑_{n=1}^{N} f_{j}(n) ≤ lim_{x→1} F_{j}(x) = 1 − lim_{x→1} \frac{1}{P_{j}(x)} ≤ ∑_{n=1}^{∞} f_{j}(n).

Ha ∑_{n=1}^{∞} P (n, j, j) = K < ∞, akkor ∑_{n=1}^{N} f_{j}(n) ≤ 1 − lim_{x→1} \frac{1}{P_{j}(x)} ≤ 1 − \frac{1}{K} minden N =

1, 2, …, számra, ezért ∑_{n=1}^{∞} f_{j}(n) < 1, és az E_{j} állapot tranziens. Ha Ha ∑_{n=1}^{∞} P (n, j, j) =

∞, akkor 1 ≥ ∑_{n=1}^{∞} f_{j}(n) ≥ 1 − lim_{x→1} \frac{1}{P_{j}(x)} = 1, tehát ∑_{n=1}^{∞} f_{j}(n) = 1, és az E_{j} állapot

rekurrens.

A tétel bizonyításának befejezéséhez elegendő belátni, hogy mivel F_{j} = ∑_{n=1}^{∞} f_{j}(n)

annak a valószínűsége, hogy az E_{j} állapotból induló Markov lánc legalább 1-szer visszatér az E_{j} állapotba, F_{j}^{k} annak a valószínűsége, hogy a Markov lánc legalább k-szor visszatér az E_{j} állapotba. Ezt az állítást k szerinti teljes indukcióval fogjuk belátni.

Az indukciós feltevés k = 1 esetben érvényes. Jelölje f_{j}^{(k)}(n) annak a valószínűségét, hogy a Markov lánc az n időpontban tér vissza a k-ik alkalommal az E_{j} állapotba. Az,

hogy az indukciós feltevés érvényes k-ra azt jelenti, hogy ∑_{n=1}^{∞} f_{j}^{(k)}(n) = F_{j}^{k}. Annak a

valószínűsége, hogy a Markov lánc legalább k + 1-szer visszatér az E_{j} állapotba kife-

jezhető, mint ∑_{n=1}^{∞} ∑_{m=1}^{∞} f_{j}^{(k)}(n)f_{j}(m) = ( ∑_{n=1}^{∞} f_{j}^{(k)}(n)) ( ∑_{m=1}^{∞} f_{j}(m)) = F_{j}^{k+1}. A tétel

bizonyítását befejeztük.

Érdemes megfogalmazni a fenti eredmény következő Pólya tétel néven ismert híres következményét.

Pólya György tétele véletlen bolyongások visszatéréséről. Tekintsük a véletlen bolyongást a d-dimenziós egész rácson, azaz tekintsünk egy olyan X_{0}, X_{1}, …, Markov láncot a d-dimenziós tér egész koordinátájú pontjain, amelyre P (X_{0} = (0, …, 0)), az X_{n+1} − X_{n} valószínűségi változók függetlenek, P (X_{n+1} − X_{n} = e_{j}) = P (X_{n+1} − X_{n} = −e_{j}) = \frac{1}{2d}, j = 1, …, d, n = 0, 1, …, ahol e_{j} azt a d-dimenziós vektort jelöli, amelynek j-ik koordinátája 1, és összes többi koordinátája nulla. A véletlen bolyongás d = 1 és d = 2 dimenzióban 1 valószínűséggel végtelen sokszor visszatér az origóba, d ≥ 3 dimenzióban 1 valószínűséggel csak véges sokszor tér vissza oda.

A Pólya tétel bizonyítása. Az előző tétel alapján elég belátni azt, hogy ∑_{n=1}^{∞} P (n, 0, 0) =

∞ egy d-dimenziós véletlen bolyongás átmenet valószínűségeire, ha d = 1 vagy d = 2,

és ∑_{n=1}^{∞} P (n, 0, 0) < ∞, ha d ≥ 3. Ezen relációk megmutatásához elég belátni, hogy

P (2n, 0, 0) ∼ Kn^{−d/2} alkalmas K = K(d) > 0 együtthatóval minden n = 1, 2, …, paraméterre és d = 1, 2, … dimenzióra. (Jegyezzük meg, hogy P (2n + 1, 0, 0) = 0, azaz páratlan sok lépésben nem térhetünk vissza az origóba). Viszont ismert az úgynevezett lokális centrális határeloszlástétel, amely jelen esetben azt fejezi ki, kissé felületesen megfogalmazva, hogy a P (X_{n} = k) valószínűségek úgy viselkednek, mint ahogy azt a centrális határeloszlástétel sugallja.

Felírhatjuk az X_{n} = ∑_{j=1}^{n−1}(X_{j}−X_{j−1}) relációt, ahol az összegben független és (ismert)

egyforma eloszlású valószínűségi változók szerepelnek. Ez lehetővé teszi, hogy a centrális határeloszlástétel bizonyításához hasonlóan, (valójában egyszerűbben), jó aszimptotikus relációt írjunk fel annak valószínűségére, hogy az X_{n} valószínűségi változó adott értéket vesz fel. Most csak a számunkra a jelen feladatban érdekes formulát látjuk be. Nevezetesen azt, hogy amennyiben Y_{k} = X_{k}−X_{k−1}, k = 1, …, 2n független d-dimenziós térbeli értékeket felvevő valószínűségi változók, P (Y_{k} = e_{j}) = P (Y_{k} = −e_{j}) = \frac{1}{2d}, j = 1, …, d, k = 1, …, 2n, akkor

lim_{n→∞} n^{−d/2}P (X_{2n} = 0) lim_{n→∞} n^{−d/2}P (Y_{1} + ⋯ + Y_{2n} = 0) = \frac{2d^{d/2}}{(2π)^{d/2}} ,  (5)

Innen következik Pólya György tétele.

Az (5) reláció bizonyításának részleteit elhagyom, Csak rövid magyarázatot adok arra, honnan lehet látni, hogy egy ilyen aszimptotikus formula érvényes, illetve, mi a bizonyítás alapgondolata. A részletek kidolgozása szorgalmi feladat.

Az (5) képlet bizonyos értelemben a centrális határeloszlástétel lokális alakjának tekinthető. A centrális határeloszlástétel bizonyítása azon múlik, hogy az X_{2n} véletlen független összeg karakterisztikus függvényére, illetve annak normalizáltjára jó aszimptotikus becslést tudunk adni. Jelen esetben a karakteresztikus függvény egy olyan (többváltozós) Fourier sor, amelynek tagjai, c_{n}(k_{1}, …, k_{d})e^{i(k_{1}x_{1}+···+k_{d}x_{d})} alakú függvények, ahol k_{1}, …, k_{d} egész számok, és k_{1} + ⋯ + k_{d} páros szám. Ezért felhasználva, hogy a Fourier sor tagjaiban szereplő függvények ortogonalitásak a K = [−\frac{π}{2} , \frac{π}{2} ] × [−π, π]^{d−1} d-dimenziós téglatesten, (mely állítást külön igazolni kell,) a c_{n}(0, …, 0) Fourier együtthatót ki lehet fejezni a Fourier sor integráljának a segítségével a K téglatesten. Ez, mivel a Fourier sor értékére jó aszimptotikus formulánk van, lehetővé teszi az (5) képlet igazolását. Ennek a számolásnak a fő lépése annak megmutatása, hogy a tekintendő integrál lényegében az origó egy kis környezetébe van koncentrálva, ahol az integrandusra jó aszimptotikus formulát lehet adni.

Magát a végeredményt előre megsejthetjük. A keresett valószínűség közelítőleg egyenlő a megfelelő kovarianciájú, 0 várható értékű normális sűrűségfüggvény integráljával a K téglatesten. Ráadásul, mivel a kovariancia mátrix (nagy n index esetén) nagy, ezért kis hibát követünk el, ha a K téglatest helyett az egész téren integrálunk.

Rátérek a b) kérdés tárgyalására, annak vizsgálatára, hogy mennyivel egyenlő egy Markov lánc átmeneteinek lim_{n→∞} P (n, j, j) határértéke (feltéve, hogy ez a határérték létezik), illetve az így kapott eredményből milyen következtetéseket tudunk levonni a P (n, j, k) átmenetvalószínűségek aszimptotikus viselkedésére nagy n paraméter esetén. A vizsgálat elején csak aperiódikus E_{j} állapotokat vizsgálunk. Ha ezek viselkedését jól le tudjuk írni, akkor az általános eset vizsgálata viszonylag egyszerűen visszavezethető erre.

A vizsgálat kulcslépése a valószínűségszámítás egyik érdekes eredményének az úgynevezett felújítási tételnek az alkalmazása. Ezt az eredményt itt nem bizonyítom, csak elmagyarázom, hogy szemléletesen nagyon természetes. (Az érdeklődők megtalálhatják ennek az eredménynek egy lehetséges bizonyítását William Feller: Bevezetés a Valószínűségszámításba című könyvében a XII. fejezet 11. pontjában. Az ismertetett eredmény megegyezik az ott tárgyalt 3. tétellel.)

Felújítási tétel. Legyenek Y_{1}, Y_{2}, …, független, egyforma eloszlású valószínűségi vál-

tozók, amelyek (szigorúan) pozitív egész értékeket vesznek fel. Jelölje S_{n} = ∑_{j=1}^{n} Y_{j},

n = 1, 2, …, a tekintett valószínűségi változók részletösszegeit, és A = {m: P (Y_{1} = m) > 0}, azaz azon egész számok halmazát, melyeket az Y_{1} valószínűségi változó pozitív valószínűséggel vesz fel. Tegyük fel, hogy az A halmazban szereplő számok legnagyobb

közös osztója 1. Jelölje továbbá μ = ∑_{j=1}^{∞} jP (Y_{1} = j) az Y_{1} valószínűségi változó várható

értékét. Ekkor a következő aszimptotikus formulát kaphatjuk annak valószínűségére, hogy valamelyik S_{m} részletösszeg felvesz egy előre rögzített nagy n értéket:

lim_{n→∞} P (ω: ⋃_{m=1}^{∞} S_{m}(ω) = n) = \frac{1}{μ}.  (6)

A (6) reláció érvényes mind μ < ∞, mind μ = ∞ esetben. Utóbbi esetben ez a képlet a \frac{1}{∞} = 0 jelöléssel érvényes.

A felújítási tétel segítségével be fogjuk látni a következő tételt.

Tétel Markov láncok átmenetvalószínűségeinek aszimptotikus viselkedéséről. Legyen X_{0}, X_{1}, … olyan Markov lánc P (n, i, j) = P (X_{n} = E_{j}|X_{0} = E_{i}) átmenetvalószínűségekkel, amelyben az E_{j} állapot rekurrens és aperiódikus. Ekkor teljesül a

lim_{n→∞} P (n, j, j) = \frac{1}{μ_{j}}  (7)

azonosság, ahol a μ_{j} mennyiség a (2) formulában van definiálva.

Először elmagyarázom a felújítási tétel szemléletes tartalmát, majd azt, hogy hogyan lehet ennek segítségével az ezt követő tételt belátni.

Természetes feltenni, hogy annak valószínűsége, hogy a független pozitív egész értékeket felvevő valószínűségi változók S_{1}, S_{2}, …, összegei különböző nagy n értékekre körülbelül ugyanolyan valószínűséggel veszik fel valamilyen indexre az n értéket. (Ahhoz, hogy ez a tulajdonság teljesüljön fel kellett tenni, hogy a tételben definiált A halmazban szereplő számok legnagyobb közös osztója 1.) Ez azt sugallja, hogy ha megjelöljük azokat a (véletlen) pontokat, amelyeket az S_{1}(ω), S_{2}(ω), … részletösszegek meglátogatnak, akkor a megjelölt pontok halmazának az összes pozitív egész számok halmazában van valamilyen sűrűsége, és a (6) képlet baloldalán szereplő kifejezésnek ez a sűrűség a (létező) limesze. Viszont ezt a sűrűséget könnyen kiszámolhatjuk. Ugyanis a nagy számok törvénye alapján \frac{S_{n}}{n} értéke tart a μ számhoz 1 valószínűséggel, ha n → ∞. Ez azt jelenti, hogy nagy n indexre van egy olyan [1, A_{n}] intervallum, amelyre A_{n} ∼ nμ, és az [1, A_{n}] intervallumban pontosan n megjelölt pont van. Ez azt jelenti, hogy a megjelölt pontok sűrűsége \frac{1}{μ}.

A fenti heurisztikus gondolatmenet mutatja, miért hihető, hogy a felújítási tétel igaz. Másrészt, mint látni fogjuk, abban az esetben, ha egy olyan az E_{j} állapotból induló Markov láncot tekintünk, amelynek E_{j} állapota rekurrens és aperiódikus, akkor az E_{j} állapot egymást követő látogatásai között eltelt időszakaszok hosszai olyan független, egyforma eloszlású valószínűségi változók, amelyek teljesítik a felújítási tétel feltételeit μ = μ_{j} várható értékkel. Ezen észrevétel segítségével megkapjuk a (7) formula bizonyítását. A részletek kidolgozása érdekében érdemes bevezetni és bebizonyítani diszkrét idejű Markov láncokra az úgynevezett erős Markov tulajdonságot. Ez egyszerű, de fontos tulajdonság.

Erős Markov tulajdonság definiciója diszkrét idejű Markov láncokra. Legyen X_{0}, X_{1}, … (stacionárius) Markov lánc. Azt mondjuk, hogy a Markov lánc teljesíti az erős Markov tulajdonságot, ha a Markov lánc tetszőleges olyan τ megállási szabályára, amelyre P (τ(ω) < ∞) = 1

P (X_{τ+1} = E_{u_{1}}, X_{τ+2} = E_{u_{2}}, …, X_{τ+j} = E_{u_{j}}|τ = n, X_{0} = E_{v_{0}}, …, X_{τ} = E_{v_{n}})
= P (X_{1} = E_{u_{1}}, X_{2} = E_{u_{2}}, …, X_{j} = E_{u_{j}}|X_{0} = E_{v_{n}})  (8)

minden olyan n, u_{1}, …, u_{n} és v_{1}, … v_{k} számokra, amelyekre a (8) képlet baloldalán szereplő feltétel nem nulla valószínűségű esemény.

A Markov tulajdonság (stacionárius) Markov láncokra azt mondja ki, hogy rögzítve egy n időpontot, és egy trajektóriát a [0, n] intervallumon egy Markov folyamatnak az n időpont utáni viselkedése, feltéve, hogy a [0, n] időintervallumban az előírt trajektóriát járta be ugyanolyan, mint egy olyan Markov folyamaté, amely a 0 időpontban ennek a trajektóriának a végpontjából indul. Az erős Markov tulajdonság ezt a tulajdonságot fogalmazza meg abban az általánosabb esetben, amikor a Markov folyamatnak nem egy determinisztikus, hanem egy véletlen megállási szabály által definiált időpontja utáni viselkedését kívánjuk leírni. Bár ezt a fogalmat csak diszkrét idejű Markov láncokra fogalmaztuk meg, az erős Markov tulajdonság fogalmát lehet (sőt érdemes) definiálni általános Markov folyamatokra is. Számunkra az erős Markov tulajdonságnak az alább definiált τ_{n}, n = 1, 2, …, megállási szabályokra vett alkalmazása lesz elsősorban érdekes.

Legyen X_{0}, X_{1}, …, stacionáris Markov lánc, P (X_{0} = E_{j}) = 1, és legyen E_{j} a Markov lánc egy rekurrens állapota. Legyen

τ_{1} = τ_{1}(E_{j}) = min{k: k > 0, X_{k} = E_{j}}.  (9)

Definiáljuk ezután a τ_{n}, n = 1, 2, …, megállási szabályokat az n szám szerinti teljes indukcióval a következő módon. Ha τ_{n}-et már definiáltuk, akkor legyen

τ_{n+1} = τ_{n+1}(E_{j}) = min{k: k > τ_{n}, X_{k} = E_{j}}.  (9′)

Szavakkal megfogalmazva, τ_{n} az E_{j} állapotba való n-ik visszatérés időpontja. Belátjuk a következő lemmát.

Lemma. Egy X_{0}, X_{1}, …, Markov lánc teljesíti az erős Markov tulajdonságot. Speciálisan, ha E_{j} a Markov lánc rekurrens állapota, és P (X_{0} = E_{j}) = 0, akkor a (9) és (9′) formulákban definiált τ_{n}, n = 1, 2, …, megállási szabályokra az Y_{1} = τ_{1}, Y_{k} = τ_{k} −τ_{k−1}, k = 2, 3, …, valószínűségi változók függetlenek és egyforma eloszlásúak, P (Y_{k} = N) = f_{j}(N), ahol f_{j}(N) a (1) képletben van definiálva.

A Lemma bizonyítása. Mivel τ megállási szabály, a (8) formula baloldalán szereplő {τ = n, X_{0} = E_{v_{0}}, …, X_{τ} = E_{v_{n}}} feltételben definiált esemény részeként szereplő {τ = n} esemény be vagy be nem következtét az {X_{0} = E_{v_{0}}, …, X_{n} = E_{v_{n}}} esemény determinisztikusan meghatározza. Ezért ez a feltétel vagy az üres vagy az {X_{0} = E_{v_{0}}, …, X_{n} = E_{v_{n}}} esemény. Az utóbbi esetben a (8) képlet baloldalán szereplő kifejezés a P (X_{n+1} = E_{u_{1}}, X_{n+2} = E_{u_{2}}, …, X_{n+j} = E_{u_{j}}|X_{0} = E_{v_{0}}, …, X_{n} = E_{v_{n}}) feltételes valószínűséggel egyenlő. Ez viszont a (stacionárius) Markov tulajdonság miatt egyenlő a jobboldali kifejezéssel.

A Lemma második állításának bizonyításához elég megmutatni, hogy minden n pozitív, N_{1}, N_{2}, …, N_{n} és N nem-negatív egész számokból álló számrendszerre

P (τ_{n+1} − τ_{n} = N|τ_{1} = N_{1}, τ_{2} − τ_{1} = N_{2}, …, τ_{n} − τ_{n−1} = N_{n}) = P (τ_{1} = N|X_{0} = E_{j}),

illetve észrevenni azt, hogy P (τ_{1} = N|X_{0} = E_{j}) = f_{j}(N) definició szerint. Másrészt {τ_{n+1} − τ_{n} = N} eseményt felírhatjuk, mint {X_{τ_{n}+1} = E_{u_{1}}, …, X_{τ_{n}+N} = E_{u_{N}} } alakú diszjunkt események unióját, és hasonlóan a {τ_{1} = N} esemény felírható, mint {X_{1} = E_{u_{1}}, …, X_{N} = E_{u_{N}} } alakú diszjunkt események uniója. Ezért a bizonyítandó azonosság igazolásához elég megmutatni azt, hogy

P (X_{τ_{n}+1} = E_{u_{1}}, …, X_{τ_{n}+N} = E_{u_{N}} |τ_{1} = N_{1}, τ_{2} − τ_{1} = N_{2}, …, τ_{n} − τ_{n−1} = N_{n})
= P (X_{1} = E_{u_{1}}, …, X_{τ_{n}+N} = E_{u_{N}} |X_{0} = E_{j})

minden lehetséges E_{u_{1}}, …, E_{u_{N}} állapotokra.

Viszont az utolsó bizonyítandó azonosság baloldalán szereplő {τ_{1} = N_{1}, τ_{2} − τ_{1} = N_{2}, …, τ_{n} − τ_{n−1} = N_{n}} feltétel felbontható {τ_{n} = N_{1} + ⋯ + N_{n}, X_{0} = E_{u_{0}}, X_{1} = E_{u_{1}}, …, X_{N_{1}+···+N_{n}} = E_{j}} alakú diszjunkt események uniójára. (Fontos, hogy az utolsó egyenlet jobboldalán az E_{j} állapot szerepel.) Ezért elég megmutatni, hogy a bizonyítani kívánt azonosság érvényes, ha az azonosság baloldalán szereplő feltételes valószínűségben szereplő feltételt ilyen alakú feltétellel helyettesítjük. Ez viszont a (8) formulában szereplő erős Markov tulajdonság következménye. A lemmát bebizonyítottuk.

A Markov láncok átmenetvalószínűségeinek aszimptotikus viselkedéséről szóló tétel egyszerű következménye a fenti lemmának és a felújítási tételnek. Valóban, tekintsük a lemma második állításában szereplő τ_{n} megállási szabályokat. Ezek felírhatóak τ_{n} =

∑_{k=1}^{n} Y_{k} alakban, ahol Y_{1}, Y_{2}, … független egyforma eloszlású valószínűségi változók, és

az az esemény, hogy az E_{j} pontból induló bolyongás az n-ik időpontban visszatér az E_{j} állapotba azzal az eseménnyel egyezik meg, hogy az τ_{1}(ω), τ_{2}(ω), …, visszatérési idők valamelyike felveszi az n értéket. Mivel ezeket a valószínűségi változókat előállítottuk, mint független, egyforma eloszlású Y_{1}, Y_{2}, … valószínűségi változók részletösszegeit, azt kell meggondolnunk, hogy ezekre alkalmazható a felújítási tétel, és az az általunk megfogalmazott eredményt adja.

Valóban, megadtuk az Y_{1} valószínűségi változó eloszlását, és abból látszik, hogy Y_{1} várható értéke a (2) formulában definiált μ_{j} szám. Másrészt azon pozitív egész halmazának, amelyeket az Y_{1} valószínűségi változó pozitív valószínűséggel vesz fel, (azaz a A halmazban szereplő számoknak) a legnagyobb közös osztója 1 az E_{j} állapot aperiódikus tulajdonsága miatt. Valóban, ha ezen számok mindegyike osztható volna valamely d ≥ 2 számmal, akkor a τ_{n} valószínűségi változók értékei 1 valószínűséggel oszthatók lennének d-vel minden n = 1, 2, … számra, és ez azt jelntené, hogy az E_{j} állapot periódusa osztható d-vel. Így a felújítási tétel megadja a kívánt állítást.

Bevezetem a következő definiciókat.

Markov lánc rekurrens null állapotának a definiciója. Legyen X_{0}, X_{1}, … Markov lánc egy E = {E_{1}, E_{2}, … } állapottéren. Azt mondjuk, hogy a Markov lánc egy E_{j} állapota rekurrens null állapot, ha az E_{j} állapotból indított Markov lánc egy valószínűséggel visszatér az E_{j} állapotba, de a visszatérés idejének a várható értéke végtelen.

Markov lánc pozitív állapotának a definiciója. Legyen X_{0}, X_{1}, … Markov lánc egy E = {E_{1}, E_{2}, … } állapottéren. Azt mondjuk, hogy a Markov lánc egy E_{j} állapota pozitív állapot, ha az E_{j} állapotból indított Markov lánc egy valószínűséggel visszatér az E_{j} állapotba, és a visszatérés idejének a várható értéke véges. Egy pozitív aperiódikus állapotot ergodikusnak nevezünk.

Feladat: Láttuk martingálok segítségével, hogy egy a nulla pontból kiinduló 1 dimenziós bolyongás 1 valószínűséggel eljut az 1 pontba, de az eljutás idejének várható értéke végtelen. Mutassuk meg, hogy ez az állítás következik a Markov láncokról tanult eredményekből is.

Segítség: Szimmetria okok miatt a 0-ból az 1-be eljutás idejének a várható értéke megegyezik az 1 vagy −1-ből a nullába való eljutás várható értékével. Másrészt a nullába való visszatérés idejének a várható értéke 1 plusz 1/2-szer az 1-ből nullába való jutás idejének a várható értéke plusz 1/2-szer a −1-ből a nullába jutás idejének a várható értéke.

A következő tételben megfogalmazott eredmény részben összefoglaló jellegű. Ebben felsoroljuk azokat a már bizonyított eredményeket, amelyek a P (n, j, k) átmenetvalószínűségek segítségével jellemzik a tranziens, rekkurens null és pozitív állapotokat. Ezenkívül nagy n idő esetén, aszimptotikus formulát is adunk a P (n, i, j) átmenetvalószínűségekre, azaz annak a valószínűségére, hogy az E_{j} állapotba jutunk az ( attól esetleg különböző) E_{i} állapotból. Ahhoz, hogy ezeket az eredményeket megkapjuk, először bevezetek néhány jelölést, és megadok néhány egyszerű, de hasznos formulát.

Vezessük be az

f_{i,j}(n) = P (X_{n} = E_{j}, X_{m} ≠ E_{j}, ha 1 ≤ m < n|X_{0} = E_{i}), n = 1, 2, …,  (10)

és

F (i, j) = ∑_{n=1}^{∞} f_{i,j}(n) n = 1, 2, …,  (10′)

mennyiségeket. Az f_{i,j}(n) szám annak a valószínűsége, hogy az E_{i} állapotból elinduló Markov lánc az n időpontban jut először az E_{j} állapotba, és F_{i,j} annak a valószínűsége, hogy az E_{i} állapotból elindítított Markov lánc valamikor eljut az E_{j} állapotba.

Igaz a következő azonosság:

P (n, i, j) = ∑_{l=1}^{n} f_{i,j}(l)P (n − l, j, j),  (11)

mert f_{i,j}(l)P (n − l, j, j) annak a valószínűsége, hogy az E_{i} állapotból kiinduló Markov lánc az l-ik lépésben veszi fel először az E_{j} értéket, 1 ≤ l ≤ n, és ezután n−l lépésben az E_{j} állapotból visszajut az E_{j} állapotba. Most megfogalmazom a következő eredményt.

Tétel egy Markov lánc egy állapotának jellemzéséről. Legyen X_{0}, X_{1}, … Markov lánc valamely E = {E_{1}, E_{2}, … } állapottéren P (n, i, j) = P (X_{n} = E_{j}|X_{0} = E_{i}) átmenetvalószínűségekkel.

a) Az E_{j} állapot akkor és csak akkor tranzitív, ha

∑_{n=1}^{∞} P (n, j, j) < ∞.

Ebben az esetben

∑_{n=1}^{∞} P (n, i, j) < ∞ minden E_{i} állapotra.

b) Az E_{j} állapot akkor és csak akkor rekurrens null állapot, ha

∑_{n=1}^{∞} P (n, j, j) = ∞ és lim_{n→∞} P (n, j, j) = 0.

Ebben az esetben

lim_{n→∞} P (n, i, j) = 0 minden E_{i} állapotra.

c) Egy aperiódikus E_{j} állapot akkor és csak akkor ergodikus, (azaz akkor és csak akkor teljesül a lim_{n→∞} P (n, j, j) = μ_{j} > 0 reláció alkalmas μ_{j} > 0 számmal, ha μ_{j} =

∑_{n=1}^{∞} nf_{j}(n) < ∞, ahol az f_{j}(n) mennyiség az (1) képlettel van megadva. A két

képletben szereplő μ_{j} szám megegyezik. Ha az E_{j} állapot ergodikus, akkor

lim_{n→∞} P (n, i, j) = F (i, j)μ_{j} minden E_{i} állapotra.  (12)

Az ebben a képletben szereplő F (i, j) számot a (10′) képletben definiáltuk.

Markov lánc egy állapotának jellemzéséről szóló tétel bizonyítása. Az a) rész első állítását a Markov láncok rekurrens és tranziens állapotainak jellemzéséről szóló tétel tartalmazza. Az a) rész második állítása következik az a) rész első állításából és a (11) formulából, mert ebből következik, hogy

∑_{n=1}^{∞} P (n, i, j) = ∑_{n=1}^{∞} ∑_{l=1}^{n} f_{i,j}(l)P (n − l, j, j) = (∑_{l=1}^{∞} f_{i,j}(l)) ( ∑_{m=1}^{∞} P (m, j, j)) < ∞.

A b) rész első állítása következik a Markov láncok rekurrens és tranziens állapotainak és a Markov láncok átmenetvalószínűségeinek aszimptotikus viselkedéséről szóló tételekből. Ez utóbbi eredmény csak aperiódikus (azaz 1 periódusú) állapotokról szól. Viszont, ha az X_{j} állapot periódusa d ≥ 2, akkor tekinthetjük az X̄_{j} = X_{dj}, j = 0, 1, …, P (X̄_{j} = 0) = 1, Markov láncot. Ennek periódusa 1, ezért erre alkalmazva a Markov láncok átmenetvalószínűségeinek aszimptotikus viselkedéséről szóló eredményt kapjuk, hogy lim_{n→∞} P (X_{nd} = E_{j}) = 0. Másrészt P (X_{nd+r} = E_{j}) = 0, ha 0 < r < d. Ezért a b) rész első állítása igaz az általános esetben.

A b) rész második állítása következik annak első feléből és a (11) formulából, mert

P (n, i, j) ≤ sup_{m≥ \frac{n}{2}} P (m, j, j) ∑_{l=1}^{n/2} f_{i,j}(l) + ∑_{l=n/2}^{∞} f_{i,j}(l),

és a b) eset feltételei mellett mind a két összeg nagyon kicsi nagy n indexre.

A c) résznek is csak a második állítása új. Az elsőt tartalmazza a Markov láncok átmenetvalószínűségeinek aszimptotikus viselkedéséről szóló tétel. A hiányzó részt az első rész és a (11) formula segítségével láthatjuk be hasonlóan a b) rész indoklásához. Valóban

P (n, i, j) = ∑_{l=1}^{n/2} f_{i,j}(l)P (n − l, j, j) + ∑_{l=n/2+1}^{n} f_{i,j}(l)P (n − l, j, j) = Σ_{1}(n) + Σ_{2}(n).

Viszont

lim_{n→∞} Σ_{1}(n) = lim_{n→∞} ∑_{l=1}^{n/2} f_{i,j}(l)μ_{j} = F (i, j)μ(j),

és

0 ≤ lim sup_{n→∞} Σ_{2}(n) ≤ lim_{n→∞} ∑_{l=n/2}^{∞} f_{i,j}(l) = 0,

ahonnan következik az állítás.

Megadom egy Markov lánc határátmenetvalószínűségeinek egy más tipusú jellemzését is. Ennek alapgondolata a következő. Ha megadjuk a Markov lánc egy olyan kezdeti (úgynevezett stacionárius) eloszlását, amely az idő során nem változik, akkor bizhatunk abban, hogy ennek eloszlásai megegyeznek az előző tételben megadott határértékekkel. Íly módon ki tudjuk számolni az \frac{1}{μ_{j}} határértékeket anélkül, hogy a közvetlenül nehezen kiszámítható várható értékeket kellene meghatároznunk. Ehelyett egy (esetleg végtelen) lineáris egyenletrendszert kell megoldanunk. E módszer tárgyalásában szükségünk van az alábbi definicióra.

Markov lánc stacionárius eloszlásáának a definiciója. Legyen X_{0}, X_{1}, …, Markov lánc valamely E = {E_{1}, E_{2}, … } állapottéren P (i, j) = P (X_{1} = E_{j}|X_{0} = E_{i}) egy lépéses átmenetvalószínűségekkel. Azt mondjuk, hogy egy u_{1} ≥ 0, u_{2} ≥ 0, …, nem negatív számokból álló sorozat a Markov lánc stacionárius eloszlását adja meg, ha ez a sorozat teljesíti a

∑_{j:E_{j}∈E} u_{j} = 1  (13)

u_{j} = ∑_{i:E_{i}∈E} u_{i}P (i, j) minden j = 1, 2, … számra.  (14)

egyenleteket.

A (13) és (14) formuláknak természetes szemléletes tartalma van. Ha olyan Markov láncot tekintünk, amelynek 0 időpontbeli eloszlása P (X_{0} = E_{j}) = u_{j} minden j = 1, 2, … számra, akkor a (13) képlet alapján a Markov lánc 1 időpontbeli eloszlása

P (X_{1} = E_{j}) = ∑_{i:E_{i}∈E} P (X_{0} = E_{i})P (X_{1} = E_{j}|X_{0} = E_{i}) = ∑_{i:E_{i}∈E} u_{i}P (i, j) = u_{j} minden

j = 1, 2, … számra. Ez azt jelenti, hogy a Markov láncnak ugyanaz a P (X_{1} = E_{j}) = u_{j}, j = 1, 2, …, az eloszlása az n = 1 időpontban. De ekkor indukcióval kapjuk, hogy ugyanez a Markov lánc eloszlása minden n = 1, 2, … időpontban.

A korábbi eredmények alapján természetes azt várni, hogy bizonyos nem túl megszorító feltételek teljesülése esetén a Markov láncnak egyetlen stacionárius eloszlása van, amelyet az u_{j} = \frac{1}{μ_{j}} képlettel adhatunk meg. Azt várjuk, hogy ez a számsorozat kielégíti a (13) és (14) képleteket, valamint a Markov lánc tetszőleges kezdeti eloszlás esetén tart a stacionárius eloszláshoz, ha az idő tart a végtelenhez. Ilyen tipusú eredményt fogunk bizonyítani.

Csak abban az esetben várhatjuk, hogy egy Markov láncnak létezik az előbb leírt stacionárius eloszlása, ha annak állapotai rekurrens, pozitív aperiódikus állapotok. Ez a feltétel biztosítja, hogy az u_{j} = \frac{1}{μ_{j}} számok pozitívak. Annak érdekében, hogy lássuk azt, hogy a később megfogalmazott eredmény jól használható, először áttekintjük egy Markov lánc állapotterének szerkezetét. Megmutatjuk, hogy az állapotteret természetes módon fel lehet bontani alkalmas osztályok uniójaként úgy, hogy az egy osztályban levő állapotok egyszerre tranziens, null vagy pozitív rekurrens állapotok, és mindegyiküknek ugyanannyi a periódusa. Az állapottér alkalmas felbontásának megtalálásában a következő eredmény játszik kulcsfontosságú szerepet.

Tétel Markov lánc állapotainak tulajdonságairól. Legyen X_{0}, X_{1}, … Markov lánc valamely E = {E_{1}, E_{2}, … } állapottéren P (n, i, j) = P (X_{n} = j|X_{0} = i) átmenetvalószínűségekkel. Legyen E_{j} rekurrens állapota a Markov láncnak, és definiáljuk az állapottér következő az E_{j} állapottól függő C(j) ⊂ E részhalmazát. E_{k} ∈ C(j) akkor és csak akkor, ha létezik olyan r pozitív egész szám, hogy P (r, j, k) > 0, azaz az E_{j} állapotból pozitív valószínűséggel el lehet jutni az E_{k} állapotba.

A C(j) halmaz minden eleme rekurrens állapot. Ha E_{k} ∈ C(j), E_{l} ∈ C(j) akkor F (k, l) = 1 a (10′) képletben definiált F (·, ·) mennyiséggel, azaz az E_{k} állapotból kiinduló Markov lánc 1 valószínűséggel eléri az E_{l} állapotot. A C(j) halmazban levő állapotok mindegyike egyszerre null vagy pozitív rekurrens állapot, és mindegyikük periódusa megegyezik. Továbbá minden E_{k} ∈ C(j) (rekurrens) állapotra az E_{k} állapottól függő C(k) ⊂ E halmazra C(k) = C(j).

A tétel bizonyítása. Először azt mutatjuk meg, hogy ha P (r, j, k) > 0 valamely r ≥ 1 számra, azaz az E_{j} állapotból indított Markov lánc pozitív valószínűséggel eljut az E_{k} állapotba, akkor F (k, j) = 1, azaz az E_{k} állapotból indított Markov lánc 1 valószínűséggel eljut az E_{j} állapotba. Valóban, ha ez nem lenne igaz, akkor az 1 − F (k, j) > 0 és P (n, k, j) > 0 relációk miatt pozitív lenne annak a valószínűsége, hogy az E_{j} állapotból induló Markov lánc az n időpont után nem tér vissza az E_{j} állapotba, mert az n időpontban az E_{k} állapotba jut, és onnan nem lép soha az E_{j} állapotba. Ez viszont ellentmond annak a ténynek, hogy az E_{j} állapot rekurrens, ezért a Markov lánc 1 valószínűséggel végtelen sokszor visszatér oda.

Mivel k ∈ C_{j} esetén léteznek olyan r és r̄ számok, amelyekre P (r, j, k) > 0 és P (r̄, k, j) ezért P (r + r̄ + n, k, k) ≥ P (r̄, k, j)P (n, j, j)P (r, j, k). Ebből az egyenlőtlenségből, illetve abból a tényből, hogy a E_{j} állapot rekurrens tulajdonsága ekvivalens azzal, hogy ∑_{n=1}^{∞} P (n, j, j) = ∞ következik, hogy ∑_{n=1}^{∞} P (n, k, k) = ∞, és az E_{k} állapot

szintén rekurrens. Továbbá, ha az E_{j} állapot vagy E_{k} állapot egyikéből egy E_{l} pozitív valószínűséggel elérhető, akkor ez az E_{l} állapot a E_{j} és E_{l} állapotok másikából is pozitív valószínűséggel elérhető, (esetleg először azt az állapotot látogatva meg, ahonnan tudjuk, hogy az E_{l} halmaz meglátogatható. Ez azt jelenti, hogy C(j) = C(k), ha E_{k} ∈ C(j). Ez speciálisan azt a következményt is maga után vonja, hogy E_{k}, E_{l} ∈ C(j) esetén F (k, l) = 1. Valóban (a paraméterek más szereposztásában) láttuk, hogy ez a reláció következik abból, hogy E_{k} ∈ C(l).

Megmutatom, hogy abban az esetben, ha létezik egy olyan E_{k} ∈ C(j), amelyik rekurrens null állapot, akkor E_{j} is rekurrens null állapot. Innen következik, hogy C(j) osztályban levő állapotok egyidejűleg null vagy pozitív állapot. Az említett tulajdonság azért érvényes, mert P (r+r̄+n, k, k) ≥ P (r̄, k, j)P (n, j, j)P (r, j, k) alkalmas P (r̄, k, j) > 0 és P (r, j, k) > 0 számokkal, ezért a lim_{n→∞} P (n, k, k) = 0 relációból következik, hogy

lim_{n→∞} P (n, j, j) = 0.

A tétel bizonyításának befejezéséhez elegendő azt megmutatni, hogy ha E_{k}, E_{l} ∈ C(j), és az A(k) = {n: P (n, k, k) > 0} halmaz elemei oszthatók egy d számmal, akkor az A(l) = {n: P (n, l, l) > 0} halmaz elemei szintén oszthatók ezzel a d számmal. Innen következik, hogy a C(j) halmaz elemei ugyanolyan periódusú állapotok. A fent megfogalmazott állítás igazolása érdekében vegyük észre, hogy léteznek olyan r_{1} > 0 és r_{2} > 0, amelyekre P (r_{1}, k, l) > 0 és P (r_{2}, l, k) > 0. Továbbá r_{1} + r_{2} ∈ A(k), mert a Markov lánc pozitív valószínűséggel visszajuthat r_{1} + r_{2} lépésben az E_{k} állapotból az E_{k} állapotba, r_{1} lépésben az E_{l} majd további r_{2} lépésben az E_{k} állapotba jutva. Ezért r_{1} + r_{2} osztható a d számmal. Továbbá, ha n ∈ A(l), azaz P (n, l, l) > 0 valamely n számra, akkor P (n + r_{1} + r_{2}, k, k) ≥ P (r_{1}, k, l)P (n, l, l)P (r_{2}, l, k) > 0, ezért n + r_{1} + r_{2} osztható a d számmal. A fentiekből következik, hogy n osztható d-vel, és ezt kellett belátnunk.

Bevezetem a következő két definiciót.

Zárt osztályok definiciója egy Markov láncok állapotterében. Legyen adva egy X_{0}, X_{1}, … Markov lánc valamely E = {E_{1}, E_{2}, … } állapotterén P (j, k) 1 lépéses átmenetvalószínűségekkel. Azt mondjuk, hogy egy C ⊂ E halmaz az állapottér egy zárt osztályát alkotja, ha minden E_{j} ∈ C állapotra ∑_{k∈C} P (j, k) = 1, azaz, ha a Markov lánc

egy C halmazbeli állapotból indul, akkor egy valószínűséggel a következő lépésben is egy ilyen állapotban marad.

Irreducibilis, zárt osztályok definiciója egy Markov lánc állapotterében. Azt mondjuk, hogy egy Markov lánc állapotterének egy zárt osztálya irreducibilis, ha önmagán és az üres halmazon kívül nincs más olyan részhalmaza, amely zárt osztály. Egy Markov láncot irreducibilisnak hívunk, ha a teljes állapottér irreducibilis (zárt) osztály.

Bebizonyítom az előbbi tétel segítségével az irreduciblis zárt osztályok néhány tulajdonságát.

Tétel Markov lánc irreducibilis zárt osztályainak tulajdonságairól. Legyen C egy X_{0}, X_{1}, …, P (n, j, k) = P (X_{n} = E_{k}|X_{0} = E_{j}) átmenetvalószínűségekkel rendelkező Markov lánc E = {E_{1}, E_{2}, … } állapotterének irreducibilis, zárt osztálya. Ekkor minden E_{k} ∈ C és E_{l} ∈ C, állapotokra az E_{l} állapot elérhető az E_{k} állapotból, azaz létezik olyan r pozitív egész szám, amelyre P (r, k, l) > 0. Egy irreducibilis osztály minden elemének ugyanaz a periódusa, és egy irreucibilis osztály minden eleme egyidejűleg, tranziens, nullrekurrens vagy pozitív rekurrens állapot. Ha E_{j} a Markov lánc rekurrens állapota, akkor az előző tételben definiált C(j) halmaz, amely azokból az állapotokból áll, amelyeket az E_{j} állapotból pozitív valószínűséggel el lehet érni, irreducibilis, zárt osztály. Minden olyan zárt, irreducibilis osztály, amely tartalmaz egy E_{j} rekurrens állapotot megegyezik egy ilyen C(j) osztállyal.

A tétel bizonyítása. Adva egy C zárt osztály és egy E_{k} ∈ C állapot definiáljuk azt a C^{(k)} ⊂ C halmazt, amely azokból az E_{p} ∈ C állapotokból áll, amelyekre P (n, k, p) > 0 valamely n számra. Azt állítom, hogy C^{(k)} is zárt osztály. Innen következik a Tétel első állítása, mert ha a C halmaz valamelyik állapota nem érhető el az E_{k} állapotból, azaz ha létezik olyan E_{l} állapot, amelyre P (n, k, l) = 0 minden pozitív egész n számra, akkor C^{(k)} a C halmaz olyan nem üres, valódi részhalmaza, amely zárt osztály. Ez azt jelenti, hogy C nem irreducibilis.

Világos, hogy ∑_{l:E_{l}∈C^{(k)}} P (n, k, l) = 1 minden n = 1, 2, … számra, mert E \ C^{(k)} csak

olyan E_{l} állapotokat tartalmaz, amelyekre P (n, k, l) = 0 minden n = 1, 2, … számra. Ha E_{l} ∈ C^{(k)}, akkor a ∑_{p:E_{p}∈C^{(k)}} P (n, l, p) = 1 relációnak is teljesülnie kell minden n =

1, 2, … számra, amiből következik, hogy C^{(k)} zárt osztály. A bizonyítandó állítás igaz, mert ellenkező esetben lenne olyan n ≥ 1 szám, amelyre ∑_{p:E_{p}∈C^{(k)}} P (n, l, p) < 1. Ekkor

létezik olyan r szám, amelyre P (r, k, l) > 0, és ∑_{l̄:El̄∈C^{(k)}}P (n+r, k, l̄) ≤ ∑_{l̄:El̄∈E\{E_{l}}}P (r, k, l̄)+

P (r, k, l) ∑_{p:E_{p}∈C^{(k)}}P (n, l, p) = 1 − P (r, k, l) + P (r, k, l) ∑_{p:E_{p}∈C^{(k)}}P (n, l, p) < 1, és ez ellent-

mondás.

Az irreducibilis osztályok már bizonyított tulajdonságából következik az előző tétel bizonyításának befejezéséhez hasonlóan, hogy egy ilyen osztály minden elemének ugyanannyi a periódusa. Az előző tételben láttuk, hogy egy rekkurrens E_{j} állapotra a C(j) halmaz az állapottér egy zárt osztálya. Továbbá, ha C̄ ⊂ C(j) nem üres zárt osztály, akkor létezik egy E_{k} ∈ C̄ elem, és ezért C(j) = C(k) ⊂ C̄. Ezért C(j) irreducibilis zárt osztály. Továbbá, ha egy irreducibilis zárt osztály tartalmaz egy rekurrens E_{j} állapotot, akkor tartalmazza a zárt C(j) osztályt is, ezért megegyezik vele. Innen következik, hogy egy irreducibilis zárt osztálynak vagy mindegyike eleme tranziens állapot vagy megegyezik valamelyik C(j) halmazzal, ahol E_{j} rekurrens állapot. Egy ilyen osztály minden eleme rekurrens null vagy rekurrens pozitív állapot. A tétel bizonyítását befejeztük.

Megfogalmazom a fenti eredmények alábbi következményét.

Következmény. Legyen X_{0}, X_{1}, … Markov lánc P (n, j, k) = P (X_{n} = E_{k}|X_{0} = E_{j}) átmenetvalószínűségekkel egy E = {E_{1}, E_{2} … } állapottéren. Bontsuk fel az E állapotteret az E = R ∪ T képlettel az R rekurrens és T tranziens állapotokból álló halmazok uniójaként. A R halmaz felbontható C(j) diszjunkt irreducibilis, zárt osztályok uniójaként. Ha E_{k}, E_{l} ∈ C(j) az R halmaz egy irreducibilis, zárt C(j) osztályára, akkor F (k, l) = 1 a (10′) képletben definiált F (·, ·) függvénnyel.

Bizonyítás. A megfogalmazott eredmények következnek a Markov lánc irreducibilis zárt osztályainak és egy Markov lánc állapotainak tulajdonságairól szóló tételek eredményeiből. Azt kell még meggondolnunk, hogy ha két az utóbbi tétel megfogalmazásában definiált C(j) és C(k) halmaz nem diszjunkt, akkor C(j) = C(k). De ebben az esetben létezik egy E_{l} ∈ C(j) ∩ C(k) állapot, és C(j) = C(l) = C(k).

A fent megfogalmazott követezményben egy Markov lánc rekurrens állapotainak halmazát felbontottuk irreducibilis, zárt halmazok uniójaként. A tranziens állapotok halmazának nincs ilyen egyértelmű leírása. Ezt mutatja a következő példa.

Példa. Legyen X_{1}, X_{2}, … bolyongás a d-dimenziós téren. Ez irreducibilis Markov lánc (azaz egyetlen irreducibilis osztályból áll), melynek elemei 2 periódikusak. Ha d = 1 vagy d = 2 akkor ennek az osztálynak az elemei null periódikusak, ha d ≥ 3 akkor tranziensek.

Definiáljuk a következő Markov láncot a két-dimenziós tér egész koordinátájú rácspontjain: Ha a Markov lánc valamely (j, k), j ≠ 0 pontban van, akkor a következő lépésban egyforma \frac{1}{4} valószínűséggel lép a (j − 1, k), (j + 1, k), (j, k + 1), (j, k − 1) szomszéd pontok valamelyikébe. Ha a Markov lánc valamely (0, k) alakú pontban van akkor a következő lépésben \frac{1}{2} valószínűséggel lép a (0, k + 1) vagy a (0, k − 1) pontba. Ennek a Markov láncnak a (0, k), k = 0 ± 1, ±2, … alakú pontok a rekurrens állapotai, amelyek irreducibilis zárt osztályt alkotnak. Ennek elemei null-rekurrens, 2 periódusú állapotok. A (j, k), j ≠ 0 alakú pontok tranziensek. Egy ilyen állapotból kiinduló Markov lánc 1 valószínűséggel eljut a rekurrens állapotokból álló halmazba, ezért nincs olyan irreducibilis zárt osztály, amely ezeket tartalmazza.

Feladat: Bizonyítsuk be a fenti példa állítását.

A következő állítást fogjuk bebizonyítani.

Tétel irreducibilis Markov láncok stacionárius eloszlásáról. Legyen X_{0}, X_{1}, … irreducibilis, aperiódikus Markov lánc P (n, j, k) = P (X_{n} = E_{k}|X_{0} = E_{j}) átmenetvalószínűségekkel egy E = {E_{1}, E_{2}, … } állapottéren.

a) Ha a Markov lánc állapotai pozitív rekurrensek, akkor az u_{j} = lim_{n→∞} P (n, i, j) >

0 határértékek léteznek, u_{j} = \frac{1}{μ_{j}}, ahol a μ_{j} számok a (2) formulában vannak definiálva. Az u_{j} számok, E_{j} ∈ E, a Markov lánc stacionárius eloszlását definiálják, azaz teljesítik a (13) és (14) formulákat.

b) Megfordítva, ha a Markov láncnak van u_{j}, j ∈ E, stacionárius eloszlása, akkor a Markov lánc ergodikus, azaz pozitív rekurrens állapotokkal rendelkezik, (és aperiódikus).

A Markov lánc (egyetlen) stacionárius eloszlása teljesíti az u_{j} = \frac{1}{μ_{j}}, E_{j} ∈ E_{j}, azonosságot.

A tétel bizonyítása. Tekintsük először azt az esetet, amikor az a) rész feltételei teljesülnek. Az egy Markov lánc egy állapotának jellemzéséről szóló tételben bizonyított (12) formulából és a Markov lánc állapotainak tulajdonságairól szóló tételből következik, hogy lim_{n→∞} P (n, i, j) = F (i, j)\frac{1}{μ_{j}} = \frac{1}{μ_{j}}. Azt kell még belátnunk, hogy az u_{j} = \frac{1}{μ_{j}}, E_{j} ∈ E, számok teljesítik a (13) és (14) azonosságot. Először azt mutatom meg, hogy

u_{j} = ∑_{k:E_{k}∈E} u_{k}P (m, k, j) minden m = 1, 2, …, számra.  (15)

Ennek érdekében írjuk fel a

P (n + m, i, j) = ∑_{k:E_{k}∈E} P (n, i, k)P (m, k, j)

és próbáljunk limeszt venni mind a két oldalon felhasználva, hogy lim_{n→∞} P (n + m, i, j) = u_{j} és lim_{n→∞} P (n, i, k) = u_{k}. Mivel a jobb oldalon szereplő P (m, k, j) együtthatók összege (rögzített j-re és a k változó szerint összegezve) lehet divergens is, egyelőre csak az alábbi a kívántnál gyengébb összefüggést tudjuk felírni (felhasználva, hogy a jobb-oldalon szereplő számok mind nem-negatívak:

u_{j} ≥ ∑_{k:E_{k}∈E} u_{k}P (m, k, j)  (15a)

Hasonlóan a ∑_{k:E_{k}∈E} P (n, i, k) = 1 azonossábból kapjuk n → ∞ határátmenettel, hogy

s = ∑_{k:E_{k}∈E} P (n, i, k) ≤ 1.  (16)

Ezt az egyenlőtlenséget felhasználva, és összegezve j-re a (15a) egyenlőtlenségeket azt kapjuk, hogy

s = ∑_{j:E_{j}∈E} u_{j} ≥ ∑_{j:E_{j}∈E} ∑_{k:E_{k}∈E} u_{k}P (m, k, j) = ( ∑_{j:E_{j}∈E} P (m, k, j)) ( ∑_{k:E_{k}∈E} u_{k}) = s.

Mivel az utolsó egyenlőtlenségsor bal és jobb oldala egyenlő (és véges), a felhasznált (15a) egyenlőtlenségekben mindenütt azonosságnak kell állni, tehát a (15) formula érvényes.

Ha a (15) formulát m = 1 választással tekintjük, megkapjuk a (14) képletet. Tekintsük újból a (15) formulát tetszőleges j számmal, és tartsunk végtelenhez az m paraméterrel. Ekkor felhasználva a (16) formulát (pontosabban csak azt, hogy az ott tekintett összeg véges) azt kapjuk, hogy

u_{j} = ∑_{k:E_{k}∈E} u_{k}u_{j} = u_{j} ∑_{k:E_{k}∈E} u_{k}.

Mivel u_{j} = \frac{1}{μ_{j}} > 0, innen következik a (13) reláció.

Rátérek a b) rész bízonyítására. Megmutatom n szerinti teljes indukcióval a Chapman–Kolmogorov egyenlet segítségével, hogy a b) esetben teljesül a (14) képlet következő általánosítása is.

u_{j} = ∑_{i:E_{i}∈E} u_{i}P (n, i, j) minden j = 1, 2, … és n = 1, 2, … számra.  (14′)

Valóban, ha a (14) formula igaz az n számra, akkor

∑_{i:E_{i}∈E} u_{i}P (n + 1, i, j) = ∑_{i:E_{i}∈E} u_{i} ∑_{k:E_{k}∈E} P (n, i, k)P (k, j)

= ∑_{k:E_{k}∈E} P (k, j) ∑_{i:E_{i}∈E} u_{i}P (n, i, k) = ∑_{k:E_{k}∈E} P (k, j)u_{k} = u_{j},

tehát a (14′) azonosság igaz n + 1-re is.

Alkalmazzunk n → ∞ határátmenetet a (14′) képletben. Azt állítom, hogy a Markov lánc ergodikus, minden i és j indexre létezik a lim_{n→∞} P (n, i, j) = \frac{1}{μ_{j}} > 0 (2) képletben definiált határérték, és

u_{j} = ∑_{i:E_{i}∈E} u_{i} \frac{1}{μ_{j}} minden j = 1, 2, … számra.  (17)

Valóban, mivel irreducibilis Markov láncot tekintünk, a Markov lánc minden állapota egyszerre tranziens, null-rekurrens vagy pozitív rekurrens. Viszont az első két esetben lim_{n→∞} P (n, i, j) = 0, ezért a (14′) formulában elvégzett határátmenet azt adná, hogy u_{j} = 0 minden j indexre. Ez viszont ellentmond a (13) relációnak. Ezért a Markov lánc állapotai pozitív rekurensek. Mivel feltettük, hogy a Markov lánc aperiódikus, ezért ergodikus, az átmenet valószínűségeknek az előző bekezdésben felírt határértékeik vannak, és teljesül a (17) formula. A (17) és (13) formulák alapján viszont

u_{j} = ∑_{i:E_{i}∈E} u_{i} \frac{1}{μ_{j}} = \frac{1}{μ_{j}} ∑_{i:E_{i}∈E} u_{i} = \frac{1}{μ_{j}} minden j = 1, 2, … számra.

Ez azt jelenti, hogy egy ergodikus Markov láncnak u_{j} = \frac{1}{μ_{j}}, E_{j} ∈ E_{j}, az egyetlen stacionárius eloszlása.

Feladat: Lássuk be az előző feladat eredményének a segítségével, hogy egy X_{0}, X_{1}, …, irreducibilis, ergodikus Markov lánc eloszlása tetszőleges kezdeti eloszlás esetén konvergál a Markov lánc stacionárius eloszlásához, ha n → ∞, azaz lim_{n→∞} P (X_{n} = E_{j}) = u_{j} minden u_{j} állapotra.

A korábbi eredményekben feltettem, hogy a tekintett Markov lánc aperiódikus. Ezt elsősorban kényelmi szempontok miatt tettem. Periódikus Markov láncok vizsgálata hasonlóan történhet, és az eredmények is hasonlóak, csak a jelölés válik kissé bonyolultabbá. Ezenkívül periódikus Markov láncok vizsgálata visszavezethető az aperiódikus Markov láncok esetére. Itt csak röviden áttekintem azt, hogy milyen eredmények érvényesek, és milyen észrevétel segítségével kaphatjuk meg azokat.

Legyen X_{0}, X_{1}, … irreducibilis Markov lánc egy E = {E_{1}, E_{2}, … } állapottéren P (n, j, k) átmenetvalószínűséggel. Tegyük fel, hogy a Markov lánc állapotai pozitív rekurrensek, és periódusok valamilyen d ≥ 1. (Tudjuk, hogy egy irreducibilis Markov lánc minden állapota egyszerre, tranziens, null vagy pozitív rekurrens, és minden állapotnak ugyanaz a periódusa.) Tekintsük az X_{0}, X_{1}, … Markov lánc mellett az X̄_{n} = X_{dn}, n = 0, 1, 2, … Markov láncot is, amelynek állapottere megegyezik az eredeti Markov lánc E állapotterével, és értéke az n időpontban egyenlő az eredeti Markov lánc értékével az nd időpontban. Ez utóbbi Markov lánc aperiódikus, P̄(j, k) = P (d, j, k) egy lépéses átmenetvalószínűségekkel, minden állapota pozitív rekurrens, de állapottere nem irreducibilis. Viszont meg tudjuk adni e Markov lánc állapotterének felbontását d darab C_{0}, …, C_{d−1} irreducibilis osztály uniójaként.

Rögzítsük mondjuk az E_{1} ∈ E állapotot, és tekintsük minden E_{k} ∈ E állapotra az N_{k} = {n: P (n, 1, k) > 0} halmazt, azaz azon időpontok halmazát, amely időpontok alatt az E_{1} állapotból pozitív valószínűséggel jutunk az E_{k} állapotba. Nem nehéz belátni, hogy az X_{0}, X_{1}, … Markov lánc d periódusa miatt létezik olyan 0 ≤ p ≤ d − 1 szám, hogy n = p mod d minden n ∈ N_{k} számra. Nevezzük ezt a p számot az E_{k} állapot r(k) rangjának. Definiáljuk a C_{p} ⊂ E, 1 ≤ p ≤ d, halmazokat úgy, hogy E_{k} ∈ C_{p} akkor és csak akkor, ha r(k) = p. Némi munkával be lehet látni, hogy a X̄_{0}, X̄_{1}, … Markov lánc E állapotterének felbontása irreducibilis zárt osztályokra a C_{p}, 0 ≤ p ≤ d−1, halmazokból áll. Továbbá, ha E_{k} ∈ C_{p}, E_{l} ∈ C_{q} valamely p és q számokkal, akkor P (n, k, l) > 0 csak akkor lehetséges, ha n = q − p mod d. Ezenkívül, ha E_{k} ∈ C_{p}, és P (n, k, l) > 0 valamely n időpontra, akkor E_{l} ∈ C_{q} azzal a q számmal, amelyre n = q − p mod d.

A fenti összefüggések segítségével, és használva a már bizonyított eredményeket az X̄_{0}, X̄_{1}, … Markov lánc megszorításán az irreducibilis C_{p}, 1 ≤ p ≤ d − 1 irreducibilis zárt osztályokra kapjuk, hogy létezik a

du_{j} = lim_{n→∞} P (dn + q − p, i, j) = \frac{d}{μ_{j}} ha E_{i} ∈ C_{p} és E_{j} ∈ E_{q}

határérték, ahol a μ_{j} szám a (2) képletben van definiálva, és P (dn + r, i, j) = 0, ha r ≠ q − p mod p. Továbbá az is igaz, hogy az u_{j} = \frac{1}{μ_{j}} számok alkotják a Markov lánc (egyetlen) stacionárius eloszlását.

Rátérek véges állapotterű, azaz véges sok különböző értéket felvevő Markov láncok rövid tárgyalására. Véges állapotterű Markov láncok rendelkeznek néhány extra tulajdonsággal, amelyeket a következő tételben fogalmazok meg. Ezenkívül a sztochaszikus mátrixok néhány lineáris algebrai tulajdonsága segít véges állapotterű Markov láncok vizsgálatában.

Tétel véges állapotterű Markov láncok tulajdonságairól. Egy véges állapotterű Markov láncnak mindig van pozitív rekurrens állapota, viszont nincs rekurrens null állapota. Egy tranziens állapotból elindított Markov lánc 1 valószínűséggel bekerül a Markov lánc rekurrens állapotaiból álló halmazba.

A tétel bizonyítása. Mivel egy véges lánc Markov n lépéses átmenetvalószínűségét is egy sztochasztikus mátrix adja meg, amelynek mérete nem függ az n számtól, és egy sztochasztikus mátrix sorösszege 1, ezért, rögzítve a sztochasztikus mátrix i-edik sorát valamely i számmal, létezik olyan j index, amelyre lim sup n → ∞P (n, i, j) > 0. Viszont egy ilyen j indexhez tartozó E_{j} állapot pozitív rekurrens, mert sem tranziens, sem null rekurrens nem lehet. Mivel a Markov lánc rekurrens állapotaiból álló halmaz felbontható diszjunkt irreducibilis zárt osztályok uniójára, és egy irreducibilis zárt osztály elemei egyidejűleg pozitív vagy null rekurrens állapotok, ezért tekintve a Markov lánc megszorítását egy irreducibilis zárt osztályra az előző érvelés alapján kapjuk, hogy a Markov láncnak nincs rekurrens null állapota. Végül, ha egy tranziens E_{i} állapotból elindított Markov lánc pozitív valószínűséggel elkerülné a Markov lánc rekurrens állapotaiból álló halmazt, akkor (újból a Markov lánc véges állapottere miatt létezne a Markov láncnak olyan E_{j} tranziens állapota, amelyre lim sup_{n→∞} P (n, i, j) > 0, és ez ellentmondás.

Egy Markov lánc viselkedéséről nagyon hasznos információt ad az a Markov lánc átmenetvalószínűségeit megadó sztochasztikus mátrix spektrumának, azaz sajátértékeinek és sajátvektorainak az ismerete. Vegyük észre, hogy egy sztochasztikus mátrixnak, ha jobbról szorozzuk meg oszlopvektorokkal, akkor a csupa 1 koordinátából álló vektor sajátvektor 1 sajátértékkel. Továbbá 1-nél nagyobb sajátértékkel rendelkező (oszlop) sajátvektor nem lehetséges. Azt is tudjuk a lineáris algebrából, hogy egy mátrixot akár balról szorozzuk meg egy sorvektorral, akár jobbról egy oszlopvektorral, ugyanazok lesznek a sajátértékei. (A sajátvektorai lényegesen különbözhetnek.)

Feladat. Lássuk be, hogy egy sztochasztikus mátrixnak nem lehet 1-nél nagyobb sajátértékkel rendelkező (oszlop) sajátvektora. Segítség: Mutassuk meg, hogy az eredeti vektor legnagyobb abszolut értékű koordinátájának az abszolut értéke nagyobb vagy egyenlő, mint a képvektor bármely koordinátájának az abszolut értéke.

Tudjuk tehát, hogy egy sztochasztikus mátrixnak létezik egy 1 sajátértékkel rendelkező (sor) sajátvektora. Enyhe plusz feltevések mellett azt is lehet tudni, hogy ennek összes koordinátája pozitív, és szép esetekben az is igaz, hogy a sztochasztikus mátrix összes többi sajátértéke szigorúan kisebb, mint 1. Ilyen esetben a sztochasztikus mátrix n-ik hatványának viselkedéséről nagyon értékes információt nyerhetünk. Ugyanis felírva a mátrix által meghatározott lineáris transzformációt olyan koordinátarendszerben, ahol annak a lehető legegyszerűbb az alakja (ez a Jordan féle normálalak használatát jelenti) be lehet látni, hogy a következő aszimptotikus reláció érvényes. Tekintsünk egy tetszőleges nem negatív értékű koordinátákból álló sorvektort, amelyben a koordináták összege 1. Ha alkalmazzuk erre a vektorra az átmenetvalószínűségek által meghatározott sztochasztikus mátrix n-ik hatványát, akkor olyan vektort kapunk, amely e mátrix 1 sajátértékű sajátvektorától az (n változó függvényében) exponenciálisan kis különbséggel tér el. Ez azt jelenti, hogy a mátrix sajátvektora adja meg a Markov lánc stacionárius eloszlását, és ha a Markov láncot tetszőleges kezdeti eloszlással indítjuk el, akkor a Markov lánc eloszlása az n idő függvényében exponenciális sebességgel konvergál a stacionárius eloszláshoz.

Az előbb vázolt gondolatmenet azt mutatja, hogy hasznos olyan eredményeket bizonyítani, amelyek megmondják, hogy egy sztochasztikus mátrixnak mikor van egyetlen 1 sajátértékű sajátvektora. A Markov láncok elméletében Perron egy tétele, illetve annak Frobenius által bizonyított általánosítása hasznos. Ezek az eredmények olyan mátrixokkal foglalkoznak, amelyeknek összes együtthatója nem negatív. Perron tételét fogom kimondani, és röviden jelzem, hogy milyen általánosítását adta ennek az eredménynek Frobenius.

Perron tétele. Legyen egy A n × n méretű négyzetes mátrix minden eleme szigorúan pozitív szám. Az A mátrix det(A − λI) karakterisztikus polinomjának, (ahol I az n × nes diagonális egységmátrix) legnagyobb abszolut értékű gyöke szigorúan pozitív, egyszeres gyök, és a karakterisztikus polinom összes többi gyökének az abszolut értéke szigorúan kisebb, mint ez a sajátérték. Az A mátrixnak a karakterisztikus polinom legnagyobb sajátértékéhez tartozó egyszeres sajátvektorának mindegyik koordinátája szigorúan pozitív szám. Ha az A mátrix sztochasztikus mátrix, azaz minden sorösszege 1-gyel egyenlő, akkor karakterisztikus polinomjának a legnagyobb gyöke 1.

Perron tétele alkalmazható olyan véges állapotterű Markov lánc vizsgálatában, amelynek összes egy-lépéses átmenetvalószínűségei szigorúan pozitívak. Ebben az esetben a Markov lánc (egyetlen) stacionárius eloszlását a Markov lánc sztochasztikus mátrixának 1 sajátértékű alkalmasan normalizált sajátvektora adja meg, és a Markov lánc n időpontbeli eloszlása tetszőleges kezdeti eloszlás esetén exponenciális sebességgel tart a stacionárius eloszláshoz, ha az n lépésszám tart végtelenhez.

A Perron tételben tekintett mátrixok irreducibilis és 1 periódusú Markov láncok vizsgálatában használhatóak. Ugyancsak algebrai módon jellemezhetőek az irreducibilis Markov láncok átmenetvalószínűségei által meghatározott sztochasztikus mátrixok. Be lehet vezetni a nem negatív elemű úgynevezett irreducibilis mátrixok fogalmát az általános esetben, amely az irreducibilis Markov láncok által meghatározott sztochasztikus mátrixok természetes általánosítása. A Perron tétel Frobenius által bizonyított általánosítása irreducibilis, nem negatív elemű mátrixok legnagyobb abszolut értékű sajátértékeinek és a hozzájuk tartozó sajátvektorok jellemzését adja meg. Ennek megfogalmazása, amelyet ebben az ismertetésben elhagyok, bonyolultabb, mint az eredeti Perron tételé. Ez a bonyolultság azzal függ össze, hogy Frobenius eredménye nemcsak az aperiódikus, hanem az irreducibils, periódikus Markov láncok viselkedésének a leírását is lehetővé teszi.