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 Markovlá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 nlé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}(n − 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.

A tétel utolsó állítása a következőt mondja. Ha egy az E_{j} állapotból induló Markovlánc 1 valószínűséggel tér vissza az E_{j} állapotba, akkor 1 valószínűséggel végtelen sokszor tér vissza az E_{j} állapotba. Míg abban az esetben, ha a visszatérés valószínűsége szigorúan kisebb, mint egy, akkor nulla annak a valószínűsége, hogy a Markov-lánc végtelen 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 ∑_{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}, …, Markovlá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.

Megjegyzés: Micheal Keane amerikai matematikus a következő humoros, de a lényeget jól kifejező interpretációját adta a Pólya tételnek: Egy részeg ember előbb-utóbb biztos, hogy hazatalál, de egy részeg madár nem feltétlenül.

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 φ_{n}(t) karakterisztikus függvényére, illetve annak normalizáltjára jó aszimptotikus becslést tudunk adni. Jelen esetben a karakterisztikus függvény egy φ_{n}(t_{1}, …, t_{d}) = c_{n}(k_{1}, …, k_{d})e^{i(k_{1}t_{1}+···+k_{d}t_{d})} alakú (több-változós) Fourier sor, amelynek tagjai c_{n}(k_{1}, …, k_{d})e^{i(k_{1}t_{1}+···+k_{d}t_{d})} alakú függvények, ahol k_{1}, …, k_{d} egész számok, és k_{1}+⋯+k_{d} páros szám. Továbbá a függetlenség miatt φ_{n}(t_{1}, …, t_{d}) = φ̄^{2n}(t_{1}, …, t_{d}),

ahol φ̄(t_{1}, …, t_{d}) = \frac{1}{2d} ∑_{j=1}^{d}(e^{it_{j}} +e^{−it_{j}}). Így a φ_{n}(t) karakterisztikus függvény kiszámol-

ható. Ezért felhasználva, hogy a Fourier sor tagjaiban szereplő függvények ortogonálisak 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, ami egyenlő a P (X_{2n} = 0) valószínűséggel, 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 az előadásban nem bizonyítom, csak elmagyarázom, hogy szemléletesen nagyon természetes. (A kiegészítésben ismertetem 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önyve XIII. fejezetének 11. pontjában leírt bizonyítás alapján.)

Felújítási tétel. Legyen Y_{1}, Y_{2}, …, független, egyforma eloszlású, (szigorúan) pozitív

egész értékeket felvevő valószínűségi változók sorozata. 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, amelyeket 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 érvényes 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ó mind μ < ∞, mind μ = ∞ esetben fennáll. 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. A (7) képlet speciálisan azt is állítja, hogy ha μ_{j} = ∞, akkor lim_{n→∞} P (n, j, j) = 0.

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 azt várni, hogy hogy a független, pozitív egész értékű valószínűségi változók S_{1}, S_{2}, …, részletösszegei körülbelül ugyanolyan valószínűséggel vesznek fel valamilyen indexre minden elég nagy n számot. (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. Ezzel kapcsolatban lásd a következő feladatot.) 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, (véletlen A_{n} végponttal), amelyre A_{n} ∼ nμ, és az [1, A_{n}] intervallumban pontosan n megjelölt pont van. Ezért a megjelölt pontok sűrűsége \frac{1}{μ}.

Feladat. Legyenek Y_{1}, Y_{2}, … független, egyforma eloszlású, pozitív egész értékeket felvevő valószínűségi változók. Tekintsük a felújítási tétel megfogalmazásában definiált A = {m: P (Y_{1} = m) > 0} halmazt. Mutassuk, meg hogy ha a A halmazban szereplő számok legnagyobb közös osztója 1, akkor létezik olyan (az A halmaztól függő) N_{0} küszöbszám, és olyan a_{1}, …, a_{k} ∈ A számok, hogy minden n ≥ N_{0} szám felírható n = r_{1}a_{1} + ⋯ + r_{k}a_{k} alakban, ahol r_{1}, …, r_{k} szigorúan pozitív egész számok. Ezért

annak valószínűsége, hogy ∑_{j=1}^{M} Y_{j} = n valamilyen M ≥ 1 számra, ha n ≥ N_{0}, szigorúan

pozitív.

Segítség. Vegyük észre, hogy bizonyos számelméleti eredmények alapján igaz a következő állítás: Ha a_{1}, …, a_{k} egész számok legnagyobb közös osztója 1, akkor az s_{1}a_{1} + ⋯ + s_{k}a_{k} = 1 reláció teljesül alkalmas s_{1}, …, s_{k} egész, de nem feltétlenül pozitív számokkal. Ha R(a_{1} + ⋯ + a_{k}) ≤ n < (R + 1)(a_{1} + ⋯ + a_{k}), akkor írjuk fel az n számot n = R(a_{1} + ⋯ + a_{k}) + [n − R(a_{1} + ⋯ + a_{k})] alakban, és alkalmazzuk a fenti eredményt.

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. Az erős Markov tulajdonság definiciója előtt be kell vezetnem a megállási szabály fogalmát.

A megállási szabály szemléletes tartalma az, hogy ez olyan utasítás (véletlen időpontbeli) megállásra, amely végrehajtható, azaz az n időpontbeli információk alapján, de a jövőbeli fejlődést nem feltétlenül ismerve el lehet dönteni, hogy az n-ik időpontban megállítsuk-e a folyamatot vagy sem. Először az általános esetben fogalmazom meg a definiciót, akkor amikor az n időpontig szerzett információk egy F_{n} σ-algebrában vannak összegyüjtve.

Megállási szabály definiciója. Legyen adva σ-algebrák növekvő F_{1} ⊂ F_{2} ⊂ F_{3} ⊂ ⋯ ⊂ A sorozata egy (Ω, A, P) valószínűségi mezőn. Azt mondjuk, hogy egy pozitív egész értékeket (és esetleg a ∞) értéket) felvevő τ(ω) valószínűségi változó megállási szabály e σ-algebrák rendszerére nézve, ha {ω: τ(ω) = n} ∈ F_{n} minden n = 1, 2, … számra.

Ezután megadom a definició változatát abban az esetben, ha σ-algebrák helyett valószínűségi változók egy sorozata van adva.

Megállási szabály definiciója. Legyen valószínűségi változók ξ_{1}(ω), ξ_{2}(ω), … sorozata egy (Ω, A, P) valószínűségi mezőn. Egy pozitív egész értékeket (és esetleg a ∞) értéket) felvevő τ(ω) valószínűségi változó megállási szabály e valószínűségi változók sorozatára nézve, ha megállási szabály a F_{n} = B(ξ_{k}(ω), 1 ≤ k ≤ n) σ-algebrák növekvő rendszerére nézve.

Feladat: Mutassuk meg, hogy a megállási szabály definicióját ekvivalens módon fogalmazzuk át, ha az {ω: τ(ω) = n} ∈ F_{n} feltételt az {ω: τ(ω) ≤ n} ∈ F_{n} feltétellel helyettesítjük (minden n = 1, 2, … számra).

E fogalom bevezetése után megfogalmazom az erős Markov tulajdonságot.

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}) = 1, 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} = 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ának feltételében 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 megjelenő 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 számok 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 jelentené, 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 null rekurrens á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 null rekurrens á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 rekurrens á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 rekurrens á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 rekurrens aperiódikus állapotot ergodikusnak nevezünk.

A következő tételben megfogalmazott eredmény részben összefoglaló jellegű. Ebben felsorolom azokat a már bizonyított eredményeket is, amelyek a P (n, j, k) átmenetvalószínűségek segítségével jellemzik a tranziens, null rekkurens és pozitív rekurrens á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 később 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), ha n ≥ 1,  (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ó Markovlá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 tranziens, 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 null rekurrens á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) = \frac{1}{μ_{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)\frac{1}{μ_{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 Markovlá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} = \frac{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.

Feladat: Tekintsünk egy az origóból induló bolyongást a számegyenesen. Mutassuk meg, hogy a bolyongás egy valószínűséggel eljut az 1 pontba, viszont az 1 pontba jutás idejének a várható értéke végtelen.

Segítség: Alkalmazzuk az előző tétel eredményét.

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, …, nemnegatí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 Markovlá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 pozitív rekurrens, 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}, … Markovlá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 Markov-lánc állapotainak tulajdonságairól szóló tétel bizonyítása. Először azt mutatjuk meg, hogy ha P (n, j, k) > 0 valamely n ≥ 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, j, k) > 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 az E_{j} állapotba.

Ha k ∈ C_{j}, akkor léteznek olyan r és r̄ számok, amelyekre P (r, j, k) > 0 és P (r̄, k, j) > 0. Továbbá 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 ek-

vivalens 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 null rekurrens állapot, akkor E_{j} is null rekurrens állapot. Innen következik, hogy C(j) osztályban levő állapotok egyidejűleg null vagy pozitív rekurrens á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.

Az előző eredményből kiolvasható, hogy ha veszünk egy rekurrens állapotot, akkor ez az állapot az összes olyan állapottal együtt, amelyek egy 1 valószínűséggel ebből az állapotból induló Markov-láncban pozitív valószínűséggel elérhetőek zárt osztályt alkotnak. A tranziens állapotok osztályozása nem ilyen egyszerű, áttekinthető. Az egyik lehetőségre a következő feladat mutat példát.

Feladat. Legyen X_{1}, X_{2}, … bolyongás a d-dimenziós téren. Ez irreducibilis Markovlá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 rekurrens állapotok, ha d ≥ 3 akkor tranziens állapotok.

Látni fogunk példát olyan Markov-láncokra is, amelynek tranziens állapotai nem tartoznak egyetlen zárt osztályba sem.

Bebizonyítom az előző 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, állapotpárra 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 irreducibilis osztály minden eleme egyidejűleg, tranziens, null-rekurrens 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, (mert C nem üres halmaz, az E_{l} állapotot viszont nem tartalmazza), 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. Azt állítom, hogy 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 ellentmondá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 megmutatnunk, 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. Ennek megmutatása érdekében a bolyongások állapotterének leírásáról szóló feladatot kiegészítem a következő példával.

Példa. 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.

Egy irreducibilis Markov-láncokról szóló állítást fogjuk bebizonyítani, azaz olyan Markov-láncot fogunk tekinteni, amelynek állapottere egyetlen, zárt osztály. Az ismertetett tétel feltételt ad arra, hogy mikor van egy ilyen Markov-láncnak stacionárius eloszlása.

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 az n változó szerint mind a két oldalon felhasználva azt, 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ágból kapjuk n → ∞ határátmenettel, hogy

s = ∑_{k:E_{k}∈E} u_{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 Markovlá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 Markovlá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 feltétlenül 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. A részletek bizonyítását elhagyom.

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 null rekurrens á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 Markov-lánc n lépéses átmenetvalószínűségeit 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 null rekurrens á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. Számunkra a következő eredmény érdekes.

A Perron tétel egy következménye Markov láncok viselkedéséről. Teljesítse egy E_{1}, …, E_{m} állapotokat tartalmazó Markov lánc Π átmenetvalószínűség mátrixa a Perron tétel feltételeit. Ekkor a Markov lánc irreducibilis, és q_{j} = P (X_{0} = E_{j}), 1 ≤ j ≤ m, stacionárius eloszlása megegyezik a Π mátrix azon 1 sajátértékű q = (q_{1}, …, q_{m})

sajátvektorával, amelyre ∑_{k=1}^{m} q_{k} = 1. A Markov lánc tetszőleges 0 időpontbeli eloszlása

esetén a Markov lánc n időpontbeli eloszlása (az n változó szerint) exponenciális sebességgel tart a q eloszláshoz, amikor n → ∞.

A következmény bizonyítása. Mivel a tekintett Markov lánc bármely állapotából a Markov lánc bármely más állapotába pozitív valószínűséggel el lehet jutni (1 lépésben), a Markov lánc irreducibilis. A Markov lánc stacionárius eloszlása megegyezik a Perron tétel állítása szerint létező q vektorral. A következmény állításának igazolásához azt kell

még megmutatni, hogy tetszőleges p = (p_{1}, …, p_{m}), p_{j} ≥ 0, 1 ≤ j ≤ k, ∑_{j=1}^{m} p_{j} = 1 alakú

vektorra lim_{n→∞} pΠ^{n} = q, és a konvergencia exponenciális sebességű ebben a relációban.

Tekintsük a Π mátrix J Jordan-féle normálalakját, és azt az e^{(1)}, …, e^{(m)} bázist, amelyben a Π mátrix ezt a Jordan féle normálakot veszi fel. Ekkor e^{(1)} = q, a mátrix 1 sajátértékű sajátvektora, egy 1 × 1 méretű Jordan kalickában van, és a Jordan-féle normálalakban szereplő összes többi sajátérték szigorúan kisebb, mint 1. Ezért, ha a

Markov lánc p = (p_{1}, …, p_{m}) eloszlásvektorát felírjuk p = c_{1}q + ∑_{j=2}^{m} c_{j}e^{(j)} alakban,

akkor a Markov lánc n időpontbeli p^{(n)} = (p_{1}^{(n)}, …, p_{m}^{(n)}) = pΠ^{n} eloszlására a p^{(n)} =

c_{1}q + ∑_{j=2}^{m} c(j, n)e^{(j)} reláció teljesül alkalmas exponenciálisan kicsi c(j, n) együtthatókkal,

azaz létezik olyan 0 < λ < 1 szám, amelyre érvényes a lim_{n→∞} c(j, n)λ^{−n} = 0 reláció

minden 2 ≤ j ≤ m számra. Azt kell még észrevenni, hogy a p = c_{1}q + ∑_{j=2}^{m} c_{j}e^{(j)}

relációban c_{1} = 1, mert 1 = lim_{n→∞} ∑_{j=1}^{m} p_{j}^{(n)} = lim_{n→∞} (c_{1} ∑_{j=1}^{n} q_{j} + ∑_{j=2}^{m} c(j, n) ∑_{s=1}^{m} e_{s}^{(j)}) = c_{1},

ahol e^{(j)} = (e_{1}^{(j)}, …, e_{m}^{(j)}), 2 ≤ j ≤ m.

A Perron tételben tekintett mátrixok irreducibilis és 1 periódusú Markov-láncok vizsgálatában használhatóak. Algebrai módon jellemezhetőek az irreducibilis Markovláncok átmenetvalószínűségei által meghatározott sztochasztikus mátrixok általánosan is. 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.

Kiegészítés.

A felújítási tétel bizonyítása.

Legyenek Y_{1}, Y_{2} … független, egyforma eloszlású pozitív egész értékű valószínűségi

változók, S_{n} = ∑_{k=1}^{n} Y_{k}, n = 1, 2, …, és definiáljuk a következő mennyiségeket: f_{k} =

P (Y_{1} = k), μ = EY_{1} = ∑_{k=1}^{∞} kf_{k}, B(ω) = {S_{1}(ω), S_{2}(ω) … }, u_{n} = P (n ∈ B(ω)),

n = 1, 2, …, és u_{0} = 1. Vegyük észre, hogy teljesülnek a

∑_{k=1}^{∞} f_{k} = 1, és f_{k} ≥ 0 minden k = 1, 2, … számra,  (A1)

valamint az

u_{n} = f_{1}u_{n−1} + f_{2}u_{n−2} + ⋯ f_{n}u_{0}, n = 1, 2, …  (A2)

relációk. Az (A1) formula azt fejezi ki, hogy az Y_{1} valószínűségi változó értéke 1 valószínűséggel egy pozitív egész szám. Az (A2) formula azért igaz, mert f_{j}u_{n−j} annak a valószínűsége, hogy Y_{1} = j, és Y_{2} + ⋯ Y_{l} = n − j valamilyen l ≥ 2 számra, ha 1 ≤ j < n, és f_{n}u_{n} annak a valószínűsége, hogy Y_{1} = n. (Vegyük észre, hogy mivel az Y_{j} valószínűségi változók függetlenek és azonos eloszlásúak, ezért u_{m} = P ({ω: Y_{2}(ω) + ⋯ Y_{l}(ω) = m valamely l = 2, 3, …, számra}.) Továbbá a felújítási tétel feltételei szerint az A = {j: f_{j} > 0} halmazban szereplő számok legnagyobb közös osztója 1. Ezért a felújítási tétel következik az alább megfogalmazott és később bebizonyítandó eredményből.

Tétel A. Legyenek f_{1}, f_{2}, … pozitív egész számok, amelyek teljesíti az (A1) relációt, és amelyekre az A = {j: f_{j} > 0} halmazban szereplő számok legnagyobb közös osztója 1. Legyen u_{0} = 1, és definiáljuk az u_{n}, n = 1, 2, …, számokat rekurzíve az (A2) formula segítségével. Ekkor

lim_{n→∞} u_{n} = \frac{1}{μ}, ahol μ = ∑_{k=1}^{∞} f_{k}.  (A3)

A μ = ∞ esetben az (A3) formula a lim_{n→∞} u_{n} = 0 azonosságot adja.

A Tétel A állítását a következő Propozició segítségével fogjuk bebizonyítani.

Propozició. Teljesüljenek a Tétel A feltételei. Vezessük be a Tétel A jelöléseit használva az η = lim sup_{n→∞} u_{n} mennyiséget. Ekkor létezik olyan n_{1} < n_{2} < … számsorozat,

amelyre igaz, hogy

lim_{j→∞} u_{n_{j}+k} = η = lim sup_{n→∞} u_{n} minden k = 0, ±1, ±2, … számra.  (A4)

Először megmutatom, hogy hogyan következik a Tétel A a Propozició állításából. Vezessük be a ρ_{k} = f_{k+1} + f_{k+2} + ⋯, k = 0, 1, 2, …, mennyiségeket. Ekkor az

(A1) képlet szerint ρ_{0} = 1, és a μ mennyiséget μ = ∑_{k=0}^{∞} ρ_{k} alakban írhatjuk. Valóban,

μ = ∑_{k=1}^{∞} kf_{k} = ∑_{k=1}^{∞} k(ρ_{k−1} − ρ_{k}) = ∑_{k=0}^{∞} ρ_{k}.

Továbbá az (A2) formulából következik az alábbi azonosság.

ρ_{0}u_{N} + ρ_{1}u_{N−1} + ⋯ + ρ_{N}u_{0} = 1 minden N = 1, 2, … számra.  (A5)

Valóban az (A2) formulát összegezve 1 ≤ n ≤ N-re kapjuk, hogy

u_{1} + ⋯ + u_{N} = u_{N−1}f_{1} + u_{N−2}(f_{1} + f_{2}) + ⋯ + u_{0}(f_{1} + ⋯ + f_{N})
= u_{N−1}(ρ_{0} − ρ_{1}) + u_{N−2}(ρ_{0} − ρ_{2}) + ⋯ + u_{0}(ρ_{0} − ρ_{N})
= ρ_{0}(u_{N−1} + ⋯ + u_{0}) − (ρ_{1}u_{N−1} + ρ_{2}u_{N−2} + ⋯ + ρ_{N}u_{N}).

Innen, mivel ρ_{0} = 1 és u_{0} = 1

u_{N} = u_{0} − (ρ_{1}u_{N−1} + ρ_{2}u_{N−2} + ⋯ + ρ_{N}u_{N})
= u_{N} + 1 − (ρ_{0}u_{N} + ρ_{1}u_{N−1} + ρ_{2}u_{N−2} + ⋯ + ρ_{N}u_{N}),

ahonnan következik az (A5) azonosság.

Bizonyítsuk be a Tétel A állítását először a μ = ∞ esetben. Alkalmazzuk az (A5) formulát olyan N = n_{j} indexekre, amelyek teljesítik a Propozició állítását, azaz lim_{j→∞} ρ_{n_{j}−k} = η = lim sup_{n→∞} u_{n} minden k > 0 számra, és hajtsuk végre a j → ∞

határátmenetet. Ekkor az (A5) formulából, illetve a μ = ∑_{k=0}^{∞} ρ_{k} = ∞ azonosságból

következik, hogy η = lim sup_{n→∞} u_{n} = 0. Viszont mivel u_{n} ≥ 0 minden n ≥ 0 indexre,

innen adódik a lim_{n→∞} u_{n} = 0 reláció ebben az esetben.

A μ < ∞ esetben mutassuk meg először azt, hogy η = \frac{1}{μ}. Az (A2) formulából látható, hogy 0 ≤ u_{n} ≤ 1 minden n indexre. Alkalmazzuk az (A5) formulát az N = n_{j} számokkal, ahol az n_{j} számok a Propozicióban szereplő indexeket jelölik, és tartsunk a j index-szel végtelenhez. Nem nehéz belátni, felhasználva a lim_{j→∞} u_{n_{j}−k}ρ_{k} = ρ_{k}η relációt

minden fix k indexre, hogy a μ = ∑_{k=0}^{∞} ρ_{k} < ∞ esetben a j → ∞ határátmenet az (A5)

formulában az

η(ρ_{0} + ρ_{1} + ⋯) = 1

azonossághoz vezet, ahonnan η = \frac{1}{μ}.

A Tétel A bizonyításának befejezéséhez elég azt megmutatni, hogy akárhogy rögzítünk egy ε > 0 számot nem lehet a pozitív egész számok olyan n_{j} részsorozatát találni, amelyre lim_{j→∞} u_{n_{j}} = η_{0} valamely 0 ≤ η_{0} ≤ η − ε számmal. Valóban, ha lenne ilyen

sorozat, akkor felhasználva azt, hogy 0 ≤ u_{n} ≤ η + \frac{ε}{2μ} n ≥ n_{0} esetében alkalmas n_{0} küszöbindex-szel, és 0 ≤ u_{n} ≤ 1 minden n-re az (A5) formula baloldalán szereplő kifejezést a következő módon becsülhetnénk felülről N = n_{j} indexre elég nagy j számra.

ρ_{0}u_{N} + ρ_{1}u_{N−1} + ⋯ + ρ_{N}u_{0}

≤ (η_{0} + \frac{ε}{2μ}) ρ_{0} + (ρ_{1} + ⋯ + ρ_{K}) (η + \frac{ε}{2μ}) + ∑_{j=K+1}^{∞} ρ_{j}

≤ (η_{0} − η) + η ∑_{l=0}^{K} ρ_{l} + \frac{ε}{2μ} ∑_{l=0}^{K} ρ_{l} + \frac{ε}{4} ≤ −ε + 1 + \frac{ε}{2} + \frac{ε}{4} ≤ 1 − \frac{ε}{4},

ha először a K, majd attól függően a j indexet választjuk elég nagyra. A számolásban

kihasználjuk az ημ = 1 és μ = ∑_{l=0}^{∞} ρ_{l} azonosságokat. A kapott egyenlőtlenség ellent-

mond az (A5) relációnak. Ezért a kívánt tulajdonságú η_{0} nem létezik, hanem teljesül a lim_{n→∞} u_{n} = η = \frac{1}{μ} azonosság.

A bizonyítás befejezéséhez be kell még bizonyítani a Propoziciót. Ennek érdekében válasszuk ki a pozitív egész számok egy olyan n_{j} részsorozatát, amelyre létezik minden k = 0, ±1, ±2, … számra a lim_{j→∞} u_{n_{j}+k} = w_{k} határérték, továbbá w_{0} = η = lim sup_{n→∞} u_{n}.

Ilyen részsorozat létezik. Valóban, mivel az u_{n} sorozat korlátos, ezért ki lehet választani pozitív egész számok egy olyan n_{1}^{(0)}, n_{2}^{(0)}, … részsorozatát, amelyre teljesül a lim_{n→∞} u_{n_{j}^{(0)}} = lim sup_{n→∞} u_{n} = η reláció. Ezután szukcesszíve ki lehet választani

a természetes számok egymásba skatulyázott n_{1}^{(l)}, n_{2}^{(l)}, …, részsorozatait minden l = 1, 2, … számra úgy, hogy teljesüljön a lim_{n→∞} u_{n_{j}^{(l)+k}} = w_{k} reláció minden |k| ≤ l egész számra valamely w_{k} határértékkel. Ezután a szokásos átlós eljárással megkaphatjuk a kívánt tulajdonságú u_{n_{j}} sorozatot. Azt állítom, hogy az így kapott sorozat teljesíti a Propozicióban előírt tulajdonságokat. Azt kell még belátni, hogy a Propozició feltételeinek teljesülése esetén w_{k} = η minden k = 0, ±1, ±2, … számra.

Közvetlenül csak azt látjuk, hogy 0 ≤ w_{k} ≤ η minden k = 0, ±1, ±2, … számra, és w_{0} = η. Ahhoz, hogy a még bizonyítandó állítást igazoljuk, először megmutatom, hogy teljesül a

w_{k} = ∑_{l=1}^{∞} f_{l}w_{k−l}  (A6)

azonosság minden k = 0, ±1, ±2, … számra. Valóban, definiáljuk a

V_{k}^{(j)} = \{ \begin{matrix}u_{n_{j}+k}, ha n_{j} + k ≥ 0 \\ 0, ha n_{j} + k < 0 \end{matrix}

számokat minden j = 1, 2, … és k = 0, ±1, ±2, … indexre. Ekkor az (A2) formula alapján

V_{k}^{(j)} = ∑_{l=1}^{∞} f_{l}V_{k−l}^{(j)},

és innen j → ∞ határátmenettel megkapjuk az (A6) formulát. Megfogalmazom a következő Lemmmát.

Lemma. Legyen w_{k}, k = 0, ±1, ±2, …, valós számok olyan sorozata, amely teljesíti az (A6) relációt valamely az (A1) formulát kielégítő f_{k} sorozattal. Legyen továbbá 0 ≤ w_{k} ≤ η minden k = 0, ±1, ±2, … indexre, w_{0} = η, és legyen az A = {j: f_{j} > 0} halmazban szereplő számok legnagyobb közös osztója 1. Ekkor w_{k} = η minden k = 0, ±1, ±2, … indexre.

A Propozició az (A6) reláció és a Lemma következménye. Ezért elegendő a Lemmát belátni.

A lemma bizonyítása. Mivel az f_{k} sorozat teljesíti az (A1) relációt, és 0 ≤ w_{k} ≤ w_{0} = η minden k indexre, az (A6) formula adja k = 0 választással, hogy w_{−k} = η minden k ∈ A indexre. Ezután az (A6) relációt k, −k ∈ A, alakú számokra alkalmazva kapjuk, hogy w_{−(k_{1}+k_{2})} = η, ha k_{1}, k_{2} ∈ A. Folytatva ezt az eljárást azt kapjuk, hogy minden k = α_{1}k_{1} + ⋯ + α_{s}k_{s} alakú lineáris kombinációra, ahol α_{1}, …, α_{s} pozitív egész számok, és k_{1}, …, k_{s} ∈ A igaz a w_{−k} = η reláció. Másrészt azt állítom, hogy mivel a A halmazban levő számok legnagyobb közös osztója 1, létezik olyan k_{0} küszöbindex, hogy minden k ≥ k_{0} szám felírható a fenti alakú k = α_{1}k_{1} + ⋯ + α_{s}k_{s} lineáris kombinációként. Valóban, alapvető számelméleti eredmények alapján léteznek olyan a_{1}, …, a_{j} ∈ A számok, és

β_{1}, …, β_{j} egész, (nem feltétlenül pozitív) együtthatók, amelyekre teljesül a ∑_{s=1}^{j} β_{s}a_{s} = 1

reláció. Legyen A = a_{1} + ⋯ + a_{j}, és írjunk minden k pozitív egész számot k = tA + p,

0 ≤ p < A, alakban. Ekkor a k = t(a_{1} +⋯+a_{j})+p ∑_{s=1}^{j} β_{s}a_{s} azonosság megadja minden

elég nagy szám kívánt alakú előállítását.

A fentiekből következik, hogy létezik olyan k_{0} küszöbindex, hogy w_{k} = η, ha k ≤ −k_{0}. Viszont ha w_{l} = η minden l ≤ k számra valamely k számra, akkor az (A1) és (A6) formula (a k + 1 indexre alkalmazva) azt adja, hogy w_{k+1} = η. Ezen észrevétel alapján teljes indukcióval kapjuk, hogy w_{k} = η minden k indexre. A lemmát bebizonyítottuk.