Diszkr´ et idej˝ u Markov-l´ ancok vizsg´ alata. Tekints¨ unk egy diszkr´et idej˝ u X0 , X1 , . . . Markov-l´ancot P (j, k) = P (Xn+1 = Ek |Xn = j), n = 1, 2, . . . , ´ atmenetval´ osz´ın˝ us´egekkel egy (Ω, A, P ) val´ osz´ın˝ us´egi mez˝ on, amely bizonyos E1 , E2 , . . . ´ert´ekeket vesz fel. Els˝osorban a k¨ ovetkez˝ o k´erd´esekre vagyunk kiv´ancsiak. a) Milyen P (j, k) ´ atmenetval´ osz´ın˝ us´egek eset´eben mondhatjuk azt, hogy a Markovl´anc az Ej ´ allapotb´ol kiindulva 1 val´ osz´ın˝ us´eggel (v´egtelen sokszor) visszat´er az Ej allapotba? (Mint l´atni fogjuk, ha a Markov-l´anc 1 val´ ´ osz´ın˝ us´eggel visszat´er az Ej allapotba, akkor az is igaz, hogy 1 val´ ´ osz´ın˝ us´eggel v´egtelen sokszor visszat´er oda.) b) Tekints¨ uk egy X0 , X1 , . . . Markov-l´anc Ej ´ allapot´ at, ´es a P (n, j, j) = P (Xn = Ej |X0 = Ej ) n-l´ep´eses ´ atmenetval´ osz´ın˝ us´egeket. L´etezik-e a lim P (n, j, j) hat´arn→∞ ´ert´ek? Ha l´etezik meg tudjuk-e adni ezt a hat´ar´ert´eket viszonylag egyszer˝ u m´ odon? L´eteznek-e ´es jellemezhet˝ oek-e a lim P (n, j, k) = lim P (Xn = Ek |X0 = Ej ) han→∞ n→∞ t´ar´ert´ekek? c) Mondhatjuk-e, hogy amennyiben Ej ´es Ek k´et olyan ´ allapot, amelyekre teljes¨ ul az a tulajdons´ag, hogy a Markov-l´anc pozit´ıv val´ osz´ın˝ us´eggel jut el az az Ej allapotb´ol az Ek ´ ´ allapotba, illetve az Ek ´ allapotb´ol az Ej a´llapotba (alkalmas sz´am´ u l´ep´esben) akkor a Markov-l´ancot az Ej illetve Ek ´ allapotb´ol elind´ıtva egyszerre igaz vagy nem igaz az, hogy a Markov-l´anc v´egtelen sokszor visszat´er illetve csak v´eges sok alkalmommal t´er vissza oda; egyszerre l´eteznek vagy nem l´eteznek ´ pozit´ıv lim P (n, j, j) > 0 ´es lim P (n, k, k) > 0 hat´ar´ert´ekek? Altal´ anosabban, fel n→∞ n→∞ tudjuk-e osztani a Markov-l´anc ´ allapotter´et annak alapj´ an, hogy mely a´llapotb´ol mely ´ allapotba lehet eljutni pozit´ıv val´ osz´ın˝ us´eggel term´eszetes m´ odon oszt´alyokra u ´gy, hogy az egy oszt´alyban lev˝ o elemeknek sok fontos hasonl´o tulajdons´aga van? E k´erd´esek t´argyal´ asa el˝ ott ´erdemes bevezetni n´eh´any fogalmat ´es mennyis´eget. Markov-l´ anc rekurrens ´ es tranziens ´ allapot´ anak fogalma. Legyen X0 , X1 , . . . egy Markov-l´ anc egy E = {E1 , E2 , . . . } ´ allapott´eren. Azt mondjuk, hogy a Markov-l´ anc Ej ´ allapota rekurrens, ha a Markov-l´ ancot az Ej ´ allapotb´ ol ind´ıtva, azaz ha P (X0 = Ej ) = 1, a Markov-l´ anc 1 val´ osz´ın˝ us´eggel visszat´er valamikor az Ej ´ allapotba. Ez azt jelenti, hogy ! ∞ [ {ω: Xn (ω) = Ej } = 1. P n=1
A Markov-l´ anc Ej ´ allapota tranziens, ha a Markov-l´ ancot az Ej ´ allapotb´ ol ind´ıtva, az 1-n´el kisebb val´ osz´ın˝ us´eggel t´er vissza valamikor az Ej ´ allapotba, azaz P
∞ [
!
{ω: Xn (ω) = Ej }
n=1
1
< 1.
Markov-l´ anc egy ´ allapot´ anak a peri´ odusa. Legyen X0 , X1 , . . . egy Markov-l´ anc egy E = {E1 , E2 , . . . }, ´ allapott´eren, ´es jel¨ olje P (n, j, k) = P (Xn = Ek |X0 = Ej ), az nl´ep´eses ´ atmenetval´ osz´ın˝ us´egeket. Vezess¨ uk be az A(j) = {n: P (n, j, j) > 0}, halmazokat, azaz azon n indexek halmaz´ at, amelyekre a P (n, j, j) ´ atmenetval´ osz´ın˝ us´eg szigor´ uan pozit´ıv. Azt mondjuk, hogy a Markov-l´ anc Ej ´ allapot´ anak peri´ odusa l, ha az A(j) halmazban szerepl˝ o sz´ amok legnagyobb k¨ oz¨ os oszt´ oja l. Ha ez a legnagyobb k¨ oz¨ os oszt´ o 1, akkor a Markov-l´ anc Ej ´ allapot´ at aperi´ odikusnak nevezz¨ uk. (Ha a A(j) halmaz u ¨res, azaz a Markov-l´ anc 1 val´ osz´ın˝ us´eggel soha nem t´er vissza az Ej ´ allapotba, akkor nem defini´ aljuk az Ej halmaz peri´ odus´ at.) (Egyszer˝ u) feladat. Egy a d-dimenzi´os t´er eg´esz koordi´at´ aj´ u pontjaib´ol a´ll´o r´acson t¨ort´en˝ o bolyong´as peri´ odusa 2. Legyen X0 , X1 , . . . Markov-l´anc egy E = {E1 , E2 , . . . }, a´llapott´eren, ´es jel¨olje P (n, j, k) = P (Xn = Ek |X0 = Ej ), az n-l´ep´eses ´ atmenetval´ osz´ın˝ us´egeket. Vezess¨ uk be az al´ abbi mennyis´egeket: fj (n) = P (Xn = Ej , Xm 6= Ej , ha 1 ≤ m < n|X0 = Ej ),
n = 1, 2, . . . ,
(1)
azaz fj (n) annak a val´ osz´ın˝ us´ege, hogy az Ej ´ allapotb´ol ind´ıtott Markov-l´anc n l´ep´es m´ ulva t´er vissza el˝ osz¨ or az Ej ´ allapotba. Ny´ılv´an az Ej ´ allapot akkor ´es csak akkor ∞ P fj (n) = 1. Ha az Ej ´ allapot rekurrens, akkor vezess¨ uk be a rekurrens, ha n=1
µj =
∞ X
nfj (n)
(2)
n=1
mennyis´egeket is. A µj mennyis´eg egyenl˝o az Ej ´ allapotba val´ o els˝ o visszat´er´es idej´enek a v´ arhat´ o ´ert´ek´evel. Mint majd l´atni fogjuk, a µj mennyis´eg szoros kapcsolatban van a (l´etez˝ o) lim P (n, j, j) hat´ar´ert´ekkel. n→∞
Vezess¨ uk be a Pj (x) =
∞ X
n
P (n, j, j)x ,
Fj (x) =
n=0
∞ X
fj (n)xn
(3)
n=0
hatv´anysorokat, ahol P (0, j, j) = 1, fj (0) = 0 definici´ o szerint. Ezek a hatv´anysorok konverg´ alnak |x| < 1 eset´eben. Vegy¨ uk ´eszre, hogy P (n, j, j) = fj (n)P (0, j, j) + fj (n − 1)P (1, j, j) + fj (n − 2)P (2, j, j) + · · · + fj (1)P (n − 1, j, j) minden n = 1, 2, . . . sz´amra. Innen, illetve a P (0, j, j) = 1 ´es fj (0) = 0 rel´ aci´okb´ ol k¨ ovetkezik, hogy Fj (x)Pj (x) = Pj (x) − 1.
(4)
A (4) azonoss´ag seg´ıts´eg´evel be fogjuk l´atni a k¨ ovetkez˝ o t´etelt. T´ etel Markov-l´ ancok rekurrens ´ es tranziens ´ allapotainak jellemz´ es´ er˝ ol. Legyen X0 , X1 , . . . , Markov-l´ anc, E1 , E2 , . . . ´ allapotokkal, ´es jel¨ olje P (n, j, k) = P (Xn = 2
Ek |X0 = Ej ) a Markov-l´ anc ´ atmenetval´ osz´ın˝ us´egeit. A Markov-l´ anc Ej ´ allapota rekurrens, ha ∞ X P (n, j, j) = ∞, n=1
tranziens, ha
∞ X
P (n, j, j) < ∞.
n=1
Ha az Ej ´ allapot rekurrens, akkor a Markov-l´ anc 1 val´ osz´ın˝ us´eggel v´egtelen sokszor t´er vissza az Ej ´ allapotba. Ha az Ej ´ allapot tranziens, akkor a Markov-l´ anc 1 val´ osz´ın˝ us´eggel csak v´eges sokszor t´er vissza az Ej ´ allapotba. A t´etel utols´ o´ all´ıt´ asa a k¨ ovetkez˝ ot mondja. Ha egy az Ej ´ allapotb´ol indul´ o Markovl´anc 1 val´ osz´ın˝ us´eggel t´er vissza az Ej ´ allapotba, akkor 1 val´ osz´ın˝ us´eggel v´egtelen sokszor t´er vissza az Ej ´ allapotba. M´ıg abban az esetben, ha a visszat´er´es val´ osz´ın˝ us´ege szigor´ uan kisebb, mint egy, akkor nulla annak a val´ osz´ın˝ us´ege, hogy a Markov-l´anc v´egtelen sokszor t´er vissza az Ej ´ allapotba. Bizony´ıt´ as: A (4) rel´ aci´o, illetve annak a t´enynek az alapj´ an, hogy Fj (x) ´es Pj (x) nem-negat´ıv egy¨ utthat´os hatv´anysorok, kapjuk, hogy minden N ≥ 1 sz´amra
Ha
∞ P
N X
∞ X 1 ≤ fj (n) ≤ lim Fj (x) = 1 − lim fj (n). x→1 x→1 Pj (x) n=1 n=1
P (n, j, j) = K < ∞, akkor
n=1
1, 2, . . . , sz´amra, ez´ert akkor 1 ≥
∞ P
∞ P
N P
1 x→1 Pj (x)
fj (n) ≤ 1 − lim
n=1
fj (n) < 1, ´es az Ej ´ allapot tranziens. Ha
n=1 1 x→1 Pj (x)
fj (n) ≥ 1− lim
n=1
≤ 1−
= 1, teh´at
∞ P
1 K
∞ P
minden N =
P (n, j, j) = ∞,
n=1
fj (n) = 1, ´es az Ej a´llapot rekurrens.
n=1
A t´etel bizony´ıt´ as´anak befejez´es´ehez elegend˝ o bel´ atni, hogy mivel Fj =
∞ P
fj (n)
n=1
annak a val´ osz´ın˝ us´ege, hogy az Ej ´ allapotb´ol indul´ o Markov-l´anc legal´ abb 1-szer visszak t´er az Ej ´ allapotba, Fj annak a val´ osz´ın˝ us´ege, hogy a Markov-l´anc legal´ abb k-szor visszat´er az Ej ´ allapotba. Innen ugyanis k¨ ovetkezik, hogy annak val´ osz´ın˝ us´ege, hogy a Markov l´anc v´egtelen sokszor t´er vissza az Ej ´ allapotba lim Fjk , ´es ez 1, ha Fj = 1, ´es k→∞
nulla ha Fj < 1. Ezt az ´ all´ıt´ ast k szerinti teljes indukci´ oval fogjuk bel´ atni. (k)
osz´ın˝ us´eg´et, Az indukci´ os feltev´es k = 1 esetben ´erv´enyes. Jel¨olje fj (n) annak a val´ hogy a Markov-l´anc az n id˝ opontban t´er vissza a k-ik alkalommal az Ej a´llapotba. Az, ∞ P (k) fj (n) = Fjk . Annak a hogy az indukci´ os feltev´es ´erv´enyes k-ra azt jelenti, hogy n=1
val´ osz´ın˝ us´ege, hogy a Markov-l´anc legal´ k + 1-szer er az Ej a´llapotba kife visszat´ abb ∞ ∞ ∞ ∞ P P P P (k) (k) fj (m) = Fjk+1 . A t´etel fj (n) fj (n)fj (m) = jezhet˝ o, mint n=1 m=1
bizony´ıt´ as´at befejezt¨ uk.
n=1
3
m=1
´ Erdemes megfogalmazni a fenti eredm´eny k¨ ovetkez˝ o P´ olya t´etel n´even ismert h´ıres k¨ ovetkezm´eny´et. P´ olya Gy¨ orgy t´ etele v´ eletlen bolyong´ asok visszat´ er´ es´ er˝ ol. Tekints¨ uk a v´eletlen bolyong´ ast a d-dimenzi´ os eg´esz r´ acson, azaz tekints¨ unk egy olyan X0 , X1 , . . . , Markovl´ ancot a d-dimenzi´ os t´er eg´esz koordin´ at´ aj´ u pontjain, amelyre P (X0 = (0, . . . , 0)), az Xn+1 − Xn val´ osz´ın˝ us´egi v´ altoz´ ok f¨ uggetlenek, P (Xn+1 − Xn = ej ) = P (Xn+1 − Xn = 1 −ej ) = 2d , j = 1, . . . , d, n = 0, 1, . . . , ahol ej azt a d-dimenzi´ os vektort jel¨ oli, amelynek j-ik koordin´ at´ aja 1, ´es ¨ osszes t¨ obbi koordin´ at´ aja nulla. A v´eletlen bolyong´ as d = 1 ´es d = 2 dimenzi´ oban 1 val´ osz´ın˝ us´eggel v´egtelen sokszor visszat´er az orig´ oba, d ≥ 3 dimenzi´ oban 1 val´ osz´ın˝ us´eggel csak v´eges sokszor t´er vissza oda. Megjegyz´es: Micheal Keane amerikai matematikus a k¨ ovetkez˝ o humoros, de a l´enyeget j´ ol kifejez˝ o interpret´aci´oj´at adta a P´ olya t´etelnek: Egy r´eszeg ember el˝ obb-ut´obb biztos, hogy hazatal´ al, de egy r´eszeg mad´ ar nem felt´etlen¨ ul. A P´ olya t´etel bizony´ıt´ asa. Az el˝ oz˝ o t´etel alapj´ an el´eg bel´ atni azt, hogy
∞ P
P (n, 0, 0) =
n=1
∞ egy d-dimenzi´os v´eletlen bolyong´as ´ atmenet val´ osz´ın˝ us´egeire, ha d = 1 vagy d = 2, ∞ P P (n, 0, 0) < ∞, ha d ≥ 3. Ezen rel´ aci´ok megmutat´ as´ahoz el´eg bel´ atni, hogy ´es n=1
P (2n, 0, 0) ∼ Kn−d/2 alkalmas K = K(d) > 0 egy¨ utthat´oval minden n = 1, 2, . . . , param´eterre ´es d = 1, 2, . . . dimenzi´ ora. (Jegyezz¨ uk meg, hogy P (2n + 1, 0, 0) = 0, azaz p´aratlan sok l´ep´esben nem t´erhet¨ unk vissza az orig´oba). Viszont ismert az u ´gynevezett lok´ alis centr´ alis hat´areloszl´ast´etel, amely jelen esetben azt fejezi ki, kiss´e fel¨ uletesen megfogalmazva, hogy a P (Xn = k) val´ osz´ın˝ us´egek u ´gy viselkednek, mint ahogy azt a centr´ alis hat´areloszl´ast´etel sugallja. n−1 P Fel´ırhatjuk az Xn = (Xj −Xj−1 ) rel´ aci´ot, ahol az ¨ osszegben f¨ uggetlen ´es (ismert) j=1
egyforma eloszl´ as´ u val´ osz´ın˝ us´egi v´ altoz´ ok szerepelnek. Ez lehet˝ ov´e teszi, hogy a centr´ alis hat´areloszl´ast´etel bizony´ıt´ as´ahoz hasonl´oan, (val´ oj´aban egyszer˝ ubben), j´ o aszimptotikus rel´ aci´ot ´ırjunk fel annak val´ osz´ın˝ us´eg´ere, hogy az Xn val´ osz´ın˝ us´egi v´ altoz´ o adott ´ert´eket vesz fel. Most csak a sz´amunkra a jelen feladatban ´erdekes formul´ at l´atjuk be. Nevezetesen azt, hogy amennyiben Yk = Xk −Xk−1 , k = 1, . . . , 2n f¨ uggetlen d-dimenzi´os 1 t´erbeli ´ert´ekeket felvev˝o val´ osz´ın˝ us´egi v´ altoz´ ok, P (Yk = ej ) = P (Yk = −ej ) = 2d , j = 1, . . . , d, k = 1, . . . , 2n, akkor lim n−d/2 P (X2n = 0) = lim n−d/2 P (Y1 + · · · + Y2n = 0) =
n→∞
n→∞
2dd/2 . (2π)d/2
(5)
Innen k¨ ovetkezik P´ olya Gy¨orgy t´etele. Az (5) rel´ aci´o bizony´ıt´ as´anak r´eszleteit elhagyom, Csak r¨ovid magyar´ azatot adok arra, honnan lehet l´atni, hogy egy ilyen aszimptotikus formula ´erv´enyes, illetve, mi a bizony´ıt´ as alapgondolata. A r´eszletek kidolgoz´ asa szorgalmi feladat. Az (5) k´eplet bizonyos ´ertelemben a centr´ alis hat´areloszl´ast´etel lok´ alis alakj´ anak tekinthet˝ o. A centr´ alis hat´areloszl´ast´etel bizony´ıt´ asa azon m´ ulik, hogy az X2n v´eletlen 4
f¨ uggetlen ¨ osszeg ϕn (t) karakterisztikus f¨ uggv´eny´ere, illetve annak normaliz´altj´ ara j´ o aszimptotikus becsl´est tudunk adni. Jelen esetben a karakterisztikus f¨ uggv´eny egy ϕn (t1 , . . . , td ) = cn (k1 , . . . , kd )ei(k1 t1 +···+kd td ) alak´ u (t¨ obb-v´ altoz´ os) Fourier sor, amelynek tagjai cn (k1 , . . . , kd )ei(k1 t1 +···+kd td ) alak´ u f¨ uggv´enyek, ahol k1 , . . . , kd eg´esz sz´amok, ´es k1 +· · ·+kd p´aros sz´am. Tov´ abb´a a f¨ uggetlens´eg miatt ϕn (t1 , . . . , td ) = ϕ¯2n (t1 , . . . , td ), d P 1 (eitj + e−itj ). ´Igy a ϕn (t) karakterisztikus f¨ uggv´eny kisz´ amolahol ϕ(t ¯ 1 , . . . , td ) = 2d j=1
hat´o. Ez´ felhaszn´ alva, hogy a Fourier sor tagjaiban szerepl˝o f¨ uggv´enyek ortogon´ alisak ert π π d−1 a K = − 2 , 2 × [−π, π] d-dimenzi´os t´eglatesten, (mely ´ all´ıt´ ast k¨ ul¨ on igazolni kell,) a cn (0, . . . , 0) Fourier egy¨ utthat´ot, ami egyenl˝o a P (X2n = 0) val´ osz´ın˝ us´eggel, ki lehet fejezni a Fourier sor integr´alj´anak a seg´ıts´eg´evel a K t´eglatesten. Ez, mivel a Fourier sor ´ert´ek´ere j´ o aszimptotikus formul´ ank van, lehet˝ ov´e teszi az (5) k´eplet igazol´as´at. Ennek a sz´amol´ asnak a f˝ o l´ep´ese annak megmutat´ asa, hogy a tekintend˝ o integr´al l´enyeg´eben az orig´o egy kis k¨ ornyezet´ebe van koncentr´ alva, ahol az integrandusra j´ o aszimptotikus formul´ at lehet adni. Mag´at a v´egeredm´enyt el˝ ore megsejthetj¨ uk. A keresett val´ osz´ın˝ us´eg k¨ ozel´ıt˝ oleg egyenl˝o a megfelel˝ o kovarianci´aj´ u, 0 v´ arhat´ o ´ert´ek˝ u norm´ alis s˝ ur˝ us´egf¨ uggv´eny integr´alj´ aval a K t´eglatesten. R´ aad´asul, mivel a kovariancia m´ atrix (nagy n index eset´en) nagy, ez´ert kis hib´at k¨ ovet¨ unk el, ha a K t´eglatest helyett az eg´esz t´eren integr´alunk. R´ at´erek a b) k´erd´es t´argyal´ as´ara, annak vizsg´alat´ara, hogy mennyivel egyenl˝o egy Markov-l´anc ´ atmeneteinek lim P (n, j, j) hat´ar´ert´eke (felt´eve, hogy ez a hat´ar´ert´ek n→∞
l´etezik), illetve az ´ıgy kapott eredm´enyb˝ol milyen k¨ ovetkeztet´eseket tudunk levonni a P (n, j, k) a´tmenetval´ osz´ın˝ us´egek aszimptotikus viselked´es´ere nagy n param´eter eset´en. A vizsg´alat elej´en csak aperi´ odikus Ej ´ allapotokat vizsg´alunk. Ha ezek viselked´es´et j´ ol le tudjuk ´ırni, akkor az ´ altal´ anos eset vizsg´alata viszonylag egyszer˝ uen visszavezethet˝ o erre. A vizsg´alat kulcsl´ep´ese a val´ osz´ın˝ us´egsz´am´ıt´ as egyik ´erdekes eredm´eny´enek az u ´gynevezett fel´ uj´ıt´ asi t´etelnek az alkalmaz´asa. Ezt az eredm´enyt az el˝ oad´asban nem bizony´ıtom, csak elmagyar´ azom, hogy szeml´eletesen nagyon term´eszetes. (A kieg´esz´ıt´esben ismertetem ennek az eredm´enynek egy lehets´eges bizony´ıt´ as´at William Feller: Bevezet´es a Val´ osz´ın˝ us´egsz´am´ıt´ asba c´ım˝ u k¨ onyve XIII. fejezet´enek 11. pontj´aban le´ırt bizony´ıt´ as alapj´ an.) Fel´ uj´ıt´ asi t´ etel. Legyen Y1 , Y2 , . . . , f¨ uggetlen, egyforma eloszl´ as´ u, (szigor´ uan) pozit´ıv n P eg´esz ´ert´ekeket felvev˝ o val´ osz´ın˝ us´egi v´ altoz´ ok sorozata. Jel¨ olje Sn = Yj , n = 1, 2, . . . , j=1
a tekintett val´ osz´ın˝ us´egi v´ altoz´ ok r´eszlet¨ osszegeit, ´es A = {m: P (Y1 = m) > 0}, azaz azon eg´esz sz´ amok halmaz´ at, amelyeket az Y1 val´ osz´ın˝ us´egi v´ altoz´ o pozit´ıv val´ osz´ın˝ us´eggel vesz fel. Tegy¨ uk fel, hogy az A halmazban szerepl˝ o sz´ amok legnagyobb k¨ oz¨ os oszt´ oja ∞ P 1. Jel¨ olje tov´ abb´ aµ= jP (Y1 = j) az Y1 val´ osz´ın˝ us´egi v´ altoz´ o v´ arhat´ o ´ert´ek´et. Ekkor j=1
a k¨ ovetkez˝ o aszimptotikus formul´ at ´erv´enyes annak val´ osz´ın˝ us´eg´ere, hogy valamelyik Sm 5
r´eszlet¨ osszeg felvesz egy el˝ ore r¨ ogz´ıtett nagy n ´ert´eket: lim P
n→∞
ω: n ∈
∞ [
!
{Sm (ω)}
m=1
=
1 . µ
(6)
A (6) rel´ aci´ o mind µ < ∞, mind µ = ∞ esetben fenn´ all. Ut´ obbi esetben ez a k´eplet a 1 = 0 jel¨ o l´ e ssel ´ e rv´ e nyes. ∞ A fel´ uj´ıt´ asi t´etel seg´ıts´eg´evel be fogjuk l´atni a k¨ ovetkez˝ o t´etelt. T´ etel Markov-l´ ancok ´ atmenetval´ osz´ın˝ us´ egeinek aszimptotikus viselked´ es´ er˝ ol. Legyen X0 , X1 , . . . olyan Markov-l´ anc P (n, i, j) = P (Xn = Ej |X0 = Ei ) ´ atmenetval´ osz´ın˝ us´egekkel, amelyben az Ej ´ allapot rekurrens ´es aperi´ odikus. Ekkor teljes¨ ul a 1 (7) lim P (n, j, j) = n→∞ µj azonoss´ ag, ahol a µj mennyis´eg a (2) formul´ aban van defini´ alva. A (7) k´eplet speci´ alisan azt is ´ all´ıtja, hogy ha µj = ∞, akkor lim P (n, j, j) = 0. n→∞
El˝osz¨ or elmagyar´ azom a fel´ uj´ıt´ asi t´etel szeml´eletes tartalm´ at, majd azt, hogy hogyan lehet ennek seg´ıts´eg´evel az ezt k¨ ovet˝ o t´etelt bel´ atni. Term´eszetes azt v´ arni, hogy hogy a f¨ uggetlen, pozit´ıv eg´esz ´ert´ek˝ u val´ osz´ın˝ us´egi v´ altoz´ ok S1 , S2 , . . . , r´eszlet¨ osszegei k¨ or¨ ulbel¨ ul ugyanolyan val´ osz´ın˝ us´eggel vesznek fel valamilyen indexre minden el´eg nagy n sz´amot. (Ahhoz, hogy ez a tulajdons´ag teljes¨ ulj¨on fel kellett tenni, hogy a t´etelben defini´alt A halmazban szerepl˝o sz´amok legnagyobb k¨ oz¨ os oszt´oja 1. Ezzel kapcsolatban l´asd a k¨ ovetkez˝ o feladatot.) Ez azt sugallja, hogy ha megjel¨olj¨ uk azokat a (v´eletlen) pontokat, amelyeket az S1 (ω), S2 (ω), . . . r´eszlet¨ osszegek megl´ atogatnak, akkor a megjel¨olt pontok halmaz´ anak az o¨sszes pozit´ıv eg´esz sz´amok halmaz´ aban van valamilyen s˝ ur˝ us´ege, ´es a (6) k´eplet baloldal´ an szerepl˝o kifejez´esnek ez a s˝ ur˝ us´eg a (l´etez˝ o) limesze. Viszont ezt a s˝ ur˝ us´eget k¨ onnyen kisz´ amolhatjuk. Ugyanis a nagy sz´amok t¨orv´enye alapj´ an Snn ´ert´eke tart a µ sz´amhoz 1 val´ osz´ın˝ us´eggel, ha n → ∞. Ez azt jelenti, hogy nagy n indexre van egy olyan [1, An ] intervallum, (v´eletlen An v´egponttal), amelyre An ∼ nµ, ´es az [1, An ] intervallumban pontosan n megjel¨olt pont van. Ez´ert a megjel¨olt pontok s˝ ur˝ us´ege µ1 . Feladat. Legyenek Y1 , Y2 , . . . f¨ uggetlen, egyforma eloszl´ as´ u, pozit´ıv eg´esz ´ert´ekeket felvev˝o val´ osz´ın˝ us´egi v´ altoz´ ok. Tekints¨ uk a fel´ uj´ıt´ asi t´etel megfogalmaz´as´aban defini´alt A = {m: P (Y1 = m) > 0} halmazt. Mutassuk, meg hogy ha a A halmazban szerepl˝o sz´amok legnagyobb k¨ oz¨ os oszt´oja 1, akkor l´etezik olyan (az A halmazt´ ol f¨ ugg˝o) N0 k¨ usz¨ obsz´am, ´es olyan a1 , . . . , ak ∈ A sz´amok, hogy minden n ≥ N0 sz´am fel´ırhat´ o n = r1 a1 + · · · + rk ak alakban, ahol r1 , . . . , rk szigor´ uan pozit´ıv eg´esz sz´amok. Ez´ert M P annak val´ osz´ın˝ us´ege, hogy Yj = n valamilyen M ≥ 1 sz´amra, ha n ≥ N0 , szigor´ uan j=1
pozit´ıv.
6
Seg´ıts´eg. Vegy¨ uk ´eszre, hogy bizonyos sz´amelm´eleti eredm´enyek alapj´ an igaz a k¨ ovetkez˝ o ´ll´ıt´ a as: Ha a1 , . . . , ak eg´esz sz´amok legnagyobb k¨ oz¨ os oszt´oja 1, akkor az s1 a1 + · · · + sk ak = 1 rel´ aci´o teljes¨ ul alkalmas s1 , . . . , sk eg´esz, de nem felt´etlen¨ ul pozit´ıv sz´amokkal. Ha R(a1 + · · · + ak ) ≤ n < (R + 1)(a1 + · · · + ak ), akkor ´ırjuk fel az n sz´amot n = R(a1 + · · · + ak ) + [n − R(a1 + · · · + ak )] alakban, ´es alkalmazzuk a fenti eredm´enyt. A fenti heurisztikus gondolatmenet mutatja, mi´ert hihet˝o, hogy a fel´ uj´ıt´ asi t´etel igaz. M´asr´eszt, egy az al´ abb megfogalmazott lemma eredm´enye szerint ha egy valamely Ej rekurrens ´es aperi´ odikus ´ allapotb´ol indul´ o Markov-l´ancot tekint¨ unk, ´es vessz¨ uk azon id˝ opontokat, amikor ez a Markov l´anc az Ej pontot megl´ atogatja, akkor az egym´ ast k¨ ovet˝ o l´atogat´asi id˝ opontok k¨ oz¨ ott eltelt id˝ oszakaszok hosszai olyan f¨ uggetlen, egyforma eloszl´ as´ u val´ osz´ın˝ us´egi v´ altoz´ ok, amelyek teljes´ıtik a fel´ uj´ıt´ asi t´etel felt´eteleit µ = µj v´ arhat´ o ´ert´ekkel. Ezen ´eszrev´etel seg´ıts´eg´evel megkapjuk a (7) formula bizony´ıt´ as´at. Legyen X0 , X1 , . . . , stacion´aris Markov-l´anc, P (X0 = Ej ) = 1, ´es legyen Ej a Markov-l´anc egy rekurrens ´ allapota. Legyen τ1 = τ1 (Ej ) = min{k: k > 0, Xk = Ej }.
(8)
Defini´ aljuk ezut´ an a τn , n = 1, 2, . . . , meg´ all´ asi szab´alyokat az n sz´am szerinti teljes indukci´ oval a k¨ ovetkez˝ o m´ odon. Ha τn -et m´ ar defini´altuk, akkor legyen τn+1 = τn+1 (Ej ) = min{k: k > τn , Xk = Ej }.
(9)
Szavakkal megfogalmazva, τn az Ej ´ allapotba val´ o n-ik visszat´er´es id˝ opontja. Bel´ atjuk a k¨ ovetkez˝ o lemm´at. Lemma. Tekints¨ unk egy X0 , X1 , . . . , Markov-l´ ancot. Ha Ej a Markov-l´ anc egy rekurrens ´ allapota, ´es P (X0 = Ej ) = 1, akkor a (8) ´es (9) formul´ akban defini´ alt τn , n = 1, 2, . . . , meg´ all´ asi szab´ alyokra az Y1 = τ1 , Yk = τk − τk−1 , k = 2, 3, . . . , val´ osz´ın˝ us´egi v´ altoz´ ok f¨ uggetlenek ´es egyforma eloszl´ as´ uak. Tov´ abb´ a P (Y1 = N ) = fj (N ), N = 1, 2, . . . , ahol fj (N ) a (1) k´epletben van defini´ alva. A Lemma bizony´ıt´ asa. A P (Y1 = N ) = fj (N ), N = 1, 2, . . . , rel´ aci´o ny´ılv´an teljes¨ ul, ´es el´eg megmutatni tetsz˝oleges k ≥ 1, ´es Nj ≥ 1, 1 ≤ j ≤ k + 1 eg´esz sz´amokra, hogy P (Yk+1 = Nk+1 |Y1 = N1 , . . . , Yk = Nk ) = fj (Nk ). Ez ugyanis azt jelenti, hogy Yk+1 felt´eteles eloszl´ asa felt´eve az Yj , 1 ≤ j ≤ k val´ osz´ın˝ us´egi v´ altoz´ ok tetsz˝oleges ´ert´ekeit mindig megegyezik Y1 eloszl´ as´aval. Ez pedig azt jelenti, hogy Yk+1 f¨ uggetlen az (Y1 , . . . , Yk ) vektort´ ol, ´es eloszl´ asa megegyzik Y1 eloszl´ as´aval. A k´ıv´ant azonoss´ag igazol´as´ahoz el´eg megmutatni, hogy minden olyan Ej1 , Ej2 , . . . EjN1 +···+Nk sorozatra, amelyre {ω: X0 (ω) = Ej , X1 (ω) = Ej1 , X2 (ω) = Ej2 , . . . XN1 +···+Nk (ω) = EjN1 +···+Nk } ⊂ {ω: Y1 (ω) = N1 , . . . , Yk (ω) = Nk } 7
P (Yk+1 = Nk+1 |X0 = Ej , X1 = Ej1 , X2 = Ej2 , . . . XN1 +···+Nk = EjN1 +···+Nk ) = fj (Nk ). Viszont ebben az esetben EjN1 +···+Nk = Ej , ´es a Markov tulajdons´ag alapj´ an P (Yk+1 = Nk+1 |X0 = Ej , X1 = Ej1 , X2 = Ej2 , . . . XN1 +···+Nk = EjN1 +···+Nk ) = P (Yk+1 = Nk+1 |XN1 +···+Nk = Ej ) = fj (Nk+1 ). Az utols´ o k´eplet m´ asodik azonoss´aga az´ert igaz, mert annak felt´eteles val´ osz´ın˝ us´eg´et kell kisz´ amolni, hogy az Ej pontb´ ol kiindul´o Markov l´anc Nk+1 id˝ o m´ ulva t´er vissza el˝ osz¨ or az Ej pontba. A lemm´at bebizony´ıtottuk. A Markov-l´ancok ´ atmenetval´ osz´ın˝ us´egeinek aszimptotikus viselked´es´er˝ ol sz´ol´ o t´etel egyszer˝ u k¨ ovetkezm´enye a fenti lemm´anak ´es a fel´ uj´ıt´ asi t´etelnek. Val´ oban, tekints¨ uk a lemma m´ asodik ´ all´ıt´ as´aban szerepl˝o τn meg´ all´ asi szab´alyokat. Ezek fel´ırhat´ oak τn = n P Yk alakban, ahol Y1 , Y2 , . . . f¨ uggetlen egyforma eloszl´ as´ u val´ osz´ın˝ us´egi v´ altoz´ ok, ´es
k=1
az az esem´eny, hogy az Ej pontb´ ol indul´ o bolyong´as az n-ik id˝ opontban visszat´er az Ej allapotba azzal az esem´ennyel egyezik meg, hogy az τ1 (ω), τ2 (ω), . . . , visszat´er´esi id˝ ´ ok valamelyike felveszi az n ´ert´eket. Mivel ezeket a val´ osz´ın˝ us´egi v´ altoz´ okat el˝ o´all´ıtottuk, mint f¨ uggetlen, egyforma eloszl´ as´ u Y1 , Y2 , . . . val´ osz´ın˝ us´egi v´ altoz´ ok r´eszlet¨ osszegeit, azt kell meggondolnunk, hogy ezekre alkalmazhat´o a fel´ uj´ıt´ asi t´etel, ´es az az a´ltalunk megfogalmazott eredm´enyt adja.
Val´ oban, megadtuk az Y1 val´ osz´ın˝ us´egi v´ altoz´ o eloszl´ as´at, ´es abb´ol l´atszik, hogy Y1 v´ arhat´ o ´ert´eke a (2) formul´ aban defini´alt µj sz´am. M´asr´eszt azon pozit´ıv eg´esz sz´amok halmaz´ anak, amelyeket az Y1 val´ osz´ın˝ us´egi v´ altoz´ o pozit´ıv val´ osz´ın˝ us´eggel vesz fel, (azaz a A halmazban szerepl˝o sz´amoknak) a legnagyobb k¨ oz¨ os oszt´oja 1 az Ej a´llapot aperi´ odikus tulajdons´aga miatt. Val´ oban, ha ezen sz´amok mindegyike oszthat´o volna valamely d ≥ 2 sz´ammal, akkor a τn val´ osz´ın˝ us´egi v´ altoz´ ok ´ert´ekei 1 val´ osz´ın˝ us´eggel oszthat´ok lenn´enek d-vel minden n = 1, 2, . . . sz´amra, ´es ez azt jelenten´e, hogy az Ej allapot peri´ ´ odusa oszthat´o d-vel. ´Igy a fel´ uj´ıt´ asi t´etel megadja a k´ıv´ant a´ll´ıt´ ast. Az el˝ obb t´argyalt eredm´eny bizony´ıt´ as´aban azt bizony´ıtottuk, illetve haszn´ altuk fel, hogy (diszkr´et idej˝ u) Markov l´ancok teljes´ıtik az u ´gynevezett er˝ os Markov tulajdons´agot. Ez egyszer˝ u, de fontos tulajdons´ag, amelyet ´erdemes ismertetni. E tulajdons´ag definici´ oj´anak megad´as´ahoz be kell vezetni a meg´ all´ asi szab´aly fogalm´ at. A meg´ all´ asi szab´aly szeml´eletes tartalma az, hogy ez olyan utas´ıt´ as (v´eletlen id˝ opontbeli) meg´ all´ asra, amely v´egrehajthat´o, azaz az n id˝ opontbeli inform´ aci´ok alapj´ an, de a j¨ ov˝obeli fejl˝od´est nem felt´etlen¨ ul ismerve el lehet d¨onteni, hogy az n-ik id˝ opontban meg´ all´ıtsuk-e a folyamatot vagy sem. El˝osz¨ or az ´ altal´ anos esetben fogalmazom meg a definici´ ot, akkor amikor az n id˝ opontig szerzett inform´ aci´ok egy Fn σ-algebr´aban vannak o¨sszegy¨ ujtve. Meg´ all´ asi szab´ aly definici´ oja. Legyen adva σ-algebr´ ak n¨ ovekv˝ o F1 ⊂ F2 ⊂ F3 ⊂ · · · ⊂ A sorozata egy (Ω, A, P ) val´ osz´ın˝ us´egi mez˝ on. Azt mondjuk, hogy egy pozit´ıv eg´esz ´ert´ekeket (´es esetleg a ∞) ´ert´eket) felvev˝ o τ (ω) val´ osz´ın˝ us´egi v´ altoz´ o meg´ all´ asi szab´ aly e σ-algebr´ ak rendszer´ere n´ezve, ha {ω : τ (ω) = n} ∈ Fn minden n = 1, 2, . . . sz´ amra. 8
Ezut´an megadom a definici´ o v´ altozat´ at abban az esetben, ha σ-algebr´ak helyett val´ osz´ın˝ us´egi v´ altoz´ ok egy sorozata van adva. Meg´ all´ asi szab´ aly definici´ oja. Legyen val´ osz´ın˝ us´egi v´ altoz´ ok ξ1 (ω), ξ2 (ω), . . . sorozata egy (Ω, A, P ) val´ osz´ın˝ us´egi mez˝ on. Egy pozit´ıv eg´esz ´ert´ekeket (´es esetleg a ∞) ´ert´eket) felvev˝ o τ (ω) val´ osz´ın˝ us´egi v´ altoz´ o meg´ all´ asi szab´ aly e val´ osz´ın˝ us´egi v´ altoz´ ok sorozat´ ara n´ezve, ha meg´ all´ asi szab´ aly a Fn = B(ξk (ω), 1 ≤ k ≤ n) σ-algebr´ ak n¨ ovekv˝ o rendszer´ere n´ezve. Feladat: Mutassuk meg, hogy a meg´ all´ asi szab´aly definici´ oj´at ekvivalens m´ odon fogalmazzuk ´ at, ha az {ω : τ (ω) = n} ∈ Fn felt´etelt az {ω : τ (ω) ≤ n} ∈ Fn felt´etellel helyettes´ıtj¨ uk (minden n = 1, 2, . . . sz´amra). E fogalom bevezet´ese ut´ an megfogalmazom az er˝ os Markov tulajdons´agot. Er˝ os Markov tulajdons´ ag definici´ oja diszkr´ et idej˝ u Markov-l´ ancokra. Legyen X0 , X1 , . . . (stacion´ arius) Markov-l´ anc. Azt mondjuk, hogy a Markov-l´ anc teljes´ıti az er˝ os Markov tulajdons´ agot, ha a Markov-l´ anc tetsz˝ oleges olyan τ meg´ all´ asi szab´ aly´ ara, amelyre P (τ (ω) < ∞) = 1 P (Xτ +1 = Eu1 , Xτ +2 = Eu2 , . . . , Xτ +j = Euj |X0 = Ev0 , . . . , Xτ = Evτ ) = P (X1 = Eu1 , X2 = Eu2 , . . . , Xj = Euj |X0 = Evτ ) minden olyan n, u1 , . . . , un ´es v1 , . . . vk sz´ amokra, amelyekre a fenti k´eplet baloldal´ an szerepl˝ o felt´etel nem nulla val´ osz´ın˝ us´eg˝ u esem´eny. A Markov tulajdons´ag (stacion´ arius) Markov-l´ancokra azt mondja ki, hogy r¨ogz´ıtve egy n id˝ opontot, ´es egy trajekt´ori´ at a [0, n] intervallumon egy Markov-folyamatnak az n id˝ opont ut´ ani viselked´ese, felt´eve, hogy a [0, n] id˝ ointervallumban az el˝ o´ırt trajekt´ori´ at j´ arta be ugyanolyan, mint egy olyan Markov-folyamat´e, amely a 0 id˝ opontban ennek a trajekt´ori´ anak a v´egpontj´ab´ ol indul. Az er˝ os Markov tulajdons´ag ezt a tulajdons´agot fogalmazza meg abban az ´ altal´ anosabb esetben, amikor a Markov-folyamatnak nem egy determinisztikus, hanem egy v´eletlen meg´ all´ asi szab´aly ´ altal defini´alt id˝ opontja ut´ ani viselked´es´et k´ıv´anjuk le´ırni. B´ar ezt a fogalmat csak diszkr´et idej˝ u Markov-l´ancokra fogalmaztuk meg, az er˝ os Markov tulajdons´ag fogalm´at lehet (s˝ot ´erdemes) defini´alni altal´ ´ anos Markov-folyamatokra is. Bevezetem a k¨ ovetkez˝ o definici´ okat. Markov-l´ anc null rekurrens ´ allapot´ anak a definici´ oja. Legyen X0 , X1 , . . . Markov-l´ anc egy E = {E1 , E2 , . . . } ´ allapott´eren. Azt mondjuk, hogy a Markov-l´ anc egy Ej allapota null rekurrens ´ ´ allapot, ha az Ej ´ allapotb´ ol ind´ıtott Markov-l´ anc egy val´ osz´ın˝ us´eggel visszat´er az Ej ´ allapotba, de a visszat´er´es idej´enek a v´ arhat´ o ´ert´eke v´egtelen. Markov-l´ anc pozit´ıv rekurrens ´ allapot´ anak a definici´ oja. Legyen X0 , X1 , . . . Markov-l´ anc egy E = {E1 , E2 , . . . } ´ allapott´eren. Azt mondjuk, hogy a Markov-l´ anc egy Ej ´ allapota pozit´ıv rekurrens ´ allapot, ha az Ej ´ allapotb´ ol ind´ıtott Markov-l´ anc egy 9
val´ osz´ın˝ us´eggel visszat´er az Ej ´ allapotba, ´es a visszat´er´es idej´enek a v´ arhat´ o ´ert´eke v´eges. Egy pozit´ıv rekurrens aperi´ odikus ´ allapotot ergodikusnak nevez¨ unk. A k¨ ovetkez˝ o t´etelben megfogalmazott eredm´eny r´eszben ¨ osszefoglal´ o jelleg˝ u. Ebben felsorolom azokat a m´ ar bizony´ıtott eredm´enyeket is, amelyek a P (n, j, k) a´tmenetval´ osz´ın˝ us´egek seg´ıts´eg´evel jellemzik a tranziens, null rekurrens ´es pozit´ıv rekurrens allapotokat. Ezenk´ıv¨ ´ ul nagy n id˝ o eset´en, aszimptotikus formul´ at is adunk a P (n, i, j) atmenetval´ ´ osz´ın˝ us´egekre, azaz annak a val´ osz´ın˝ us´eg´ere, hogy az Ej a´llapotba jutunk az (att´ol esetleg k¨ ul¨ onb¨oz˝ o) Ei ´ allapotb´ol. Ahhoz, hogy ezeket az eredm´enyeket megkapjuk, el˝ osz¨ or bevezetek n´eh´ any jel¨ol´est, ´es megadok n´eh´ any egyszer˝ u, de hasznos formul´ at. Vezess¨ uk be az fi,j (n) = P (Xn = Ej , Xm 6= Ej , ha 1 ≤ m < n|X0 = Ei ), ´es F (i, j) =
∞ X
fi,j (n)
n = 1, 2, . . . ,
n = 1, 2, . . . ,
(10)
(10′ )
n=1
mennyis´egeket. Az fi,j (n) sz´am annak a val´ osz´ın˝ us´ege, hogy az Ei a´llapotb´ol elindul´ o Markov-l´anc az n id˝ opontban jut el˝ osz¨ or az Ej ´ allapotba, ´es Fi,j annak a val´ osz´ın˝ us´ege, hogy az Ei ´ allapotb´ol elind´ıt´ıtott Markov-l´anc valamikor k´es˝obb eljut az Ej a´llapotba. Igaz a k¨ ovetkez˝ o azonoss´ag: P (n, i, j) =
n X
fi,j (l)P (n − l, j, j),
ha n ≥ 1,
(11)
l=1
mert fi,j (l)P (n − l, j, j) annak a val´ osz´ın˝ us´ege, hogy az Ei ´ allapotb´ol kiindul´o Markovl´anc az l-ik l´ep´esben veszi fel el˝ osz¨ or az Ej ´ert´eket, 1 ≤ l ≤ n, ´es ezut´ an n−l l´ep´esben az Ej ´ allapotb´ol visszajut az Ej ´ allapotba. Most megfogalmazom a k¨ ovetkez˝ o eredm´enyt. T´ etel egy Markov-l´ anc egy ´ allapot´ anak jellemz´ es´ er˝ ol. Legyen X0 , X1 , . . . Markov-l´ anc valamely E = {E1 , E2 , . . . } ´ allapott´eren P (n, i, j) = P (Xn = Ej |X0 = Ei ) atmenetval´ ´ osz´ın˝ us´egekkel. a) Az Ej ´ allapot akkor ´es csak akkor tranziens, ha ∞ X
P (n, j, j) < ∞.
n=1
Ebben az esetben ∞ X
P (n, i, j) < ∞
n=1
10
minden Ei ´ allapotra.
b) Az Ej ´ allapot akkor ´es csak akkor null rekurrens ´ allapot, ha ∞ X
P (n, j, j) = ∞ ´es
n=1
lim P (n, j, j) = 0.
n→∞
Ebben az esetben lim P (n, i, j) = 0
n→∞
minden Ei ´ allapotra.
c) Egy aperi´ odikus Ej ´ allapot akkor ´es csak akkor ergodikus, (azaz akkor ´es csak akkor teljes¨ ul a lim P (n, j, j) = µ1j > 0 rel´ aci´ o alkalmas µj > 0 sz´ ammal, ha µj = n→∞ ∞ P nfj (n) < ∞, ahol az fj (n) mennyis´eg az (1) k´eplettel van megadva. Az itteni n=1
´es a (2) k´epletben szerepl˝ o µj sz´ am megegyezik. Ha az Ej ´ allapot ergodikus, akkor lim P (n, i, j) = F (i, j)
n→∞
1 µj
minden Ei ´ allapotra.
(12)
Az ebben a k´epletben szerepl˝ o F (i, j) sz´ amot a (10) ´es (10′ ) k´epletben defini´ altuk. Markov-l´ anc egy ´ allapot´ anak jellemz´es´er˝ ol sz´ ol´ o t´etel bizony´ıt´ asa. Az a) r´esz els˝ o a´ll´ıt´ as´at a Markov-l´ancok rekurrens ´es tranziens ´ allapotainak jellemz´es´er˝ ol sz´ol´ o t´etel tartalmazza. Az a) r´esz m´ asodik ´ all´ıt´ asa k¨ ovetkezik az a) r´esz els˝ o a´ll´ıt´ as´ab´ ol ´es a (11) formul´ ab´ ol, mert ebb˝ol k¨ ovetkezik, hogy ! ∞ ! ∞ ∞ X n ∞ X X X X P (n, i, j) = fi,j (l)P (n − l, j, j) = fi,j (l) P (m, j, j) < ∞. n=1
n=1 l=1
m=0
l=1
A b) r´esz els˝ o ´ all´ıt´ asa k¨ ovetkezik a Markov-l´ancok rekurrens ´es tranziens a´llapotainak ´es a Markov-l´ancok ´ atmenetval´ osz´ın˝ us´egeinek aszimptotikus viselked´es´er˝ ol sz´ol´ o t´etelekb˝ol. Ez ut´ obbi eredm´eny csak aperi´ odikus (azaz 1 peri´ odus´ u) a´llapotokr´ol sz´ol. ¯ j = Xdj , j = 0, 1, . . . , Viszont, ha az Xj ´ allapot peri´ odusa d ≥ 2, akkor tekinthetj¨ uk az X ¯ j = 0) = 1, Markov-l´ancot. Ennek peri´ P (X odusa 1, ez´ert erre alkalmazva a Markovl´ancok a´tmenetval´ osz´ın˝ us´egeinek aszimptotikus viselked´es´er˝ ol sz´ol´ o eredm´enyt kapjuk, hogy lim P (Xnd = Ej ) = 0. M´asr´eszt P (Xnd+r = Ej ) = 0, ha 0 < r < d. Ez´ert a b) n→∞ r´esz els˝ o a´ll´ıt´ asa igaz az ´ altal´ anos esetben. A b) r´esz m´ asodik ´ all´ıt´ asa k¨ ovetkezik annak els˝ o fel´eb˝ ol ´es a (11) formul´ ab´ ol, mert P (n, i, j) ≤ sup P (m, j, j) m≥ n 2
n/2 X l=1
fi,j (l) +
∞ X
fi,j (l),
l=n/2
´es a b) eset felt´etelei mellett mind a k´et ¨ osszeg nagyon kicsi nagy n indexre. 11
A c) r´esznek is csak a m´ asodik, a (12) formul´ aban megfogalmazott a´ll´ıt´ asa u ´j. Az els˝ ot tartalmazza a Markov-l´ancok ´ atmenetval´ osz´ın˝ us´egeinek aszimptotikus viselked´es´er˝ ol sz´ol´ o t´etel. A hi´ anyz´o r´eszt az els˝ o r´esz ´es a (11) formula seg´ıts´eg´evel l´athatjuk be hasonl´oan a b) r´esz indokl´ as´ahoz. Val´ oban
P (n, i, j) =
n/2 X
n X
fi,j (l)P (n − l, j, j) +
l=1
fi,j (l)P (n − l, j, j) = Σ1 (n) + Σ2 (n).
l=n/2+1
Viszont lim Σ1 (n) = lim
n→∞
n→∞
n/2 X fi,j (l) l=1
´es 0 ≤ lim sup Σ2 (n) ≤ lim
n→∞
n→∞
µj
∞ X
=
F (i, j) , µj
fi,j (l) = 0,
l=n/2
ahonnan k¨ ovetkezik az ´ all´ıt´ as. Feladat: Tekints¨ unk egy az orig´ob´ ol indul´ o bolyong´ast a sz´amegyenesen. Mutassuk meg, hogy a bolyong´as egy val´ osz´ın˝ us´eggel eljut az 1 pontba, viszont az 1 pontba jut´ as idej´enek a v´ arhat´ o ´ert´eke v´egtelen. Seg´ıts´eg: Alkalmazzuk az el˝ oz˝ o t´etel eredm´eny´et. Megadom egy Markov-l´anc hat´ar´ atmenetval´ osz´ın˝ us´egeinek egy m´ as tipus´ u jellemz´es´et is. Ennek alapgondolata a k¨ ovetkez˝ o. Ha megadjuk a Markov-l´anc egy olyan kezdeti (´ ugynevezett stacion´arius) eloszl´ as´at, amely az id˝ o sor´ an nem v´ altozik, akkor bizhatunk abban, hogy ennek eloszl´ asai megegyeznek az el˝ oz˝ o t´etelben megadott hat´ar´ert´ekekkel. ´Ily m´ odon ki tudjuk sz´amolni az µ1j hat´ar´ert´ekeket an´elk¨ ul, hogy a k¨ ozvetlen¨ ul nehezen kisz´ am´ıthat´ o v´ arhat´ o ´ert´ekeket kellene meghat´ aroznunk. Ehelyett egy (esetleg v´egtelen) line´aris egyenletrendszert kell megoldanunk. E m´ odszer t´argyal´ as´aban sz¨ uks´eg¨ unk van az al´ abbi definici´ ora. Markov-l´ anc stacion´ arius eloszl´ as´ anak a definici´ oja. Legyen X0 , X1 , . . . , Markov-l´ anc valamely E = {E1 , E2 , . . . } ´ allapott´eren P (i, j) = P (X1 = Ej |X0 = Ei ) egy l´ep´eses ´ atmenetval´ osz´ın˝ us´egekkel. Azt mondjuk, hogy egy u1 ≥ 0, u2 ≥ 0, . . . , nemnegat´ıv sz´ amokb´ ol ´ all´ o sorozat a Markov-l´ anc stacion´ arius eloszl´ as´ at adja meg, ha ez a sorozat teljes´ıti a X uj = 1 (13) j:Ej ∈E
uj =
X
ui P (i, j)
minden j = 1, 2, . . . sz´ amra.
i:Ei ∈E
egyenleteket. 12
(14)
A (13) ´es (14) formul´ aknak term´eszetes szeml´eletes tartalma van. Ha olyan Markovl´ancot tekint¨ unk, amelynek 0 id˝ opontbeli eloszl´ asa P (X0 = Ej ) = uj minden j = 1, 2, . . . sz´amra, P akkor a (13) k´eplet alapj´ an a Markov-l´anc opontbeli eloszl´ asa P 1 id˝ ui P (i, j) = uj minden P (X0 = Ei )P (X1 = Ej |X0 = Ei ) = P (X1 = Ej ) = i:Ei ∈E
i:Ei ∈E
j = 1, 2, . . . sz´amra. Ez azt jelenti, hogy a Markov-l´ancnak ugyanaz a P (X1 = Ej ) = uj , j = 1, 2, . . . , az eloszl´ asa az n = 1 id˝ opontban. De ekkor indukci´ oval kapjuk, hogy ugyanez a Markov-l´anc eloszl´ asa minden n = 1, 2, . . . id˝ opontban.
A kor´ abbi eredm´enyek alapj´ an term´eszetes azt v´ arni, hogy bizonyos nem t´ ul megszor´ıt´ o felt´etelek teljes¨ ul´ese eset´en a Markov-l´ancnak egyetlen stacion´arius eloszl´ asa van, arjuk, hogy ez a sz´amsorozat kiel´eg´ıti amelyet az uj = µ1j k´eplettel adhatunk meg. Azt v´ a (13) ´es (14) k´epleteket, valamint a Markov-l´anc tetsz˝oleges kezdeti eloszl´ as eset´en tart a stacion´arius eloszl´ ashoz, ha az id˝ o tart a v´egtelenhez. Ilyen tipus´ u eredm´enyt fogunk bizony´ıtani. Csak abban az esetben v´ arhatjuk, hogy egy Markov-l´ancnak l´etezik az el˝ obb le´ırt stacion´arius eloszl´ asa, ha annak ´ allapotai pozit´ıv rekurrens, aperi´ odikus a´llapotok. Ez a felt´etel biztos´ıtja, hogy az uj = µ1j sz´amok pozit´ıvak. Annak ´erdek´eben, hogy l´assuk azt, hogy a k´es˝obb megfogalmazott eredm´eny j´ ol haszn´ alhat´ o, el˝ osz¨ or a´ttekintj¨ uk egy Markov-l´anc ´ allapotter´enek szerkezet´et. Megmutatjuk, hogy az a´llapotteret term´eszetes m´ odon fel lehet bontani alkalmas oszt´alyok uni´ojak´ent u ´gy, hogy az egy oszt´alyban lev˝ o ´ allapotok egyszerre tranziens, null vagy pozit´ıv rekurrens a´llapotok, ´es mindegyik¨ uknek ugyanannyi a peri´ odusa. Az ´ allapott´er alkalmas felbont´as´anak megtal´ al´ as´aban a k¨ ovetkez˝ o eredm´eny j´ atszik kulcsfontoss´ ag´ u szerepet. T´ etel Markov-l´ anc ´ allapotainak tulajdons´ agair´ ol. Legyen X0 , X1 , . . . Markovl´ anc valamely E = {E1 , E2 , . . . } ´ allapott´eren P (n, i, j) = P (Xn = j|X0 = i) ´ atmenetval´ osz´ın˝ us´egekkel. Legyen Ej rekurrens ´ allapota a Markov-l´ ancnak, ´es defini´ aljuk az allapott´er k¨ ´ ovetkez˝ o az Ej ´ allapott´ ol f¨ ugg˝ o C(j) ⊂ E r´eszhalmaz´ at. Ek ∈ C(j) akkor ´es csak akkor, ha l´etezik olyan r pozit´ıv eg´esz sz´ am, hogy P (r, j, k) > 0, azaz az Ej allapotb´ ´ ol pozit´ıv val´ osz´ın˝ us´eggel el lehet jutni az Ek ´ allapotba. A C(j) halmaz minden eleme rekurrens ´ allapot. Ha Ek ∈ C(j), El ∈ C(j) akkor ′ F (k, l) = 1 a (10 ) k´epletben defini´ alt F (·, ·) mennyis´eggel, azaz az Ek ´ allapotb´ ol kiindul´ o Markov-l´ anc 1 val´ osz´ın˝ us´eggel el´eri az El ´ allapotot. A C(j) halmazban lev˝ o ´ allapotok mindegyike egyszerre null vagy pozit´ıv rekurrens ´ allapot, ´es mindegyik¨ uk peri´ odusa megegyezik. Tov´ abb´ a minden Ek ∈ C(j) (rekurrens) ´ allapotra az Ek ´ allapott´ ol f¨ ugg˝ o C(k) ⊂ E halmazra C(k) = C(j). A Markov-l´ anc ´ allapotainak tulajdons´ agair´ ol sz´ ol´ o t´etel bizony´ıt´ asa. El˝osz¨ or azt mutatom meg, hogy ha P (n, j, k) > 0 valamely n ≥ 1 sz´amra, azaz a (rekurrens) Ej allapotb´ol ind´ıtott Markov-l´anc pozit´ıv val´ ´ osz´ın˝ us´eggel eljut az Ek a´llapotba, akkor F (k, j) = 1, azaz az Ek ´ allapotb´ol ind´ıtott Markov-l´anc 1 val´ osz´ın˝ us´eggel eljut az Ej allapotba. Val´ ´ oban, ha ez nem lenne igaz, akkor az 1 − F (k, j) > 0 ´es P (n, j, k) > 0 rel´ aci´ok miatt pozit´ıv lenne annak a val´ osz´ın˝ us´ege, hogy az Ej ´ allapotb´ol indul´ o Markovl´anc az n id˝ opont ut´ an nem t´er vissza az Ej ´ allapotba, mert az n id˝ opontban az Ek 13
´llapotba jut, ´es onnan nem l´ep soha az Ej ´ a allapotba. Ez viszont ellentmond annak a t´enynek, hogy az Ej ´ allapot rekurrens, ez´ert a Markov-l´anc 1 val´ osz´ın˝ us´eggel v´egtelen sokszor visszat´er az Ej ´ allapotba. Ha k ∈ C(j), akkor l´eteznek olyan r ´es r¯ sz´amok, amelyekre P (r, j, k) > 0 ´es P (¯ r, k, j) > 0. Tov´ abb´a P (r + r¯ + n, k, k) ≥ P (¯ r, k, j)P (n, j, j)P (r, j, k). Ebb˝ ol az egyenl˝otlens´egb˝ol, illetve abb´ol a t´enyb˝ol, hogy a Ej ´ allapot rekurrens tulajdons´aga ∞ ∞ P P P (n, k, k) = ∞, ´es az Ek P (n, j, j) = ∞ k¨ ovetkezik, hogy ekvivalens azzal, hogy n=1
n=1
´llapot szint´en rekurrens. Tov´ a abb´a, ha az Ej ´ allapot vagy Ek ´ allapot egyik´eb˝ ol egy El pozit´ıv val´ osz´ın˝ us´eggel el´erhet˝ o, akkor ez az El ´ allapot a Ej ´es Ek a´llapotok m´ asik´ ab´ ol is pozit´ıv val´ osz´ın˝ us´eggel el´erhet˝ o, (esetleg el˝ osz¨ or azt az ´ allapotot l´atogatva meg, ahonnan tudjuk, hogy az El halmaz megl´ atogathat´ o). Ez azt jelenti, hogy C(j) = C(k), ha Ek ∈ C(j). Ez speci´ alisan azt a k¨ ovetkezm´enyt is maga ut´ an vonja, hogy Ek , El ∈ C(j) eset´en F (k, l) = 1. Val´ oban (a param´eterek m´ as szereposzt´as´aban) l´attuk, hogy ez a rel´ aci´o k¨ ovetkezik abb´ol, hogy Ek ∈ C(l). Megmutatom, hogy abban az esetben, ha l´etezik egy olyan Ek ∈ C(j), amelyik null rekurrens ´ allapot, akkor Ej is null rekurrens ´ allapot. Innen k¨ ovetkezik, hogy a C(j) oszt´alyban lev˝ o´ allapotok egyidej˝ uleg null vagy pozit´ıv rekurrens a´llapotok. Az eml´ıtett tulajdons´ag az´ert ´erv´enyes, 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 ´es P (r, j, k) > 0 sz´amokkal, ez´ert a lim P (n, k, k) = 0 rel´ aci´ob´ ol n→∞
k¨ ovetkezik, hogy lim P (n, j, j) = 0. n→∞
A t´etel bizony´ıt´ as´anak befejez´es´ehez elegend˝ o azt megmutatni, hogy ha Ek , El ∈ C(j), ´es az A(k) = {n : P (n, k, k) > 0} halmaz elemei oszthat´ok egy d sz´ammal, akkor az A(l) = {n : P (n, l, l) > 0} halmaz elemei szint´en oszthat´ok ezzel a d sz´ammal. Innen k¨ ovetkezik, hogy a C(j) halmaz elemei ugyanolyan peri´ odus´ u´ allapotok. A fent megfogalmazott ´ all´ıt´ as igazol´asa ´erdek´eben vegy¨ uk ´eszre, hogy l´eteznek olyan r1 > 0 ´es r2 > 0 sz´amok, amelyekre P (r1 , k, l) > 0 ´es P (r2 , l, k) > 0. Tov´ abb´a r1 + r2 ∈ A(k), mert a Markov-l´anc pozit´ıv val´ osz´ın˝ us´eggel visszajuthat r1 + r2 l´ep´esben az Ek a´llapotb´ol az Ek ´ allapotba, r1 l´ep´esben az El majd tov´ abbi r2 l´ep´esben az Ek a´llapotba jutva. Ez´ert r1 + r2 oszthat´o a d sz´ammal. Tov´ abb´a, ha n ∈ A(l), azaz P (n, l, l) > 0 valamely n sz´amra, akkor P (n + r1 + r2 , k, k) ≥ P (r1 , k, l)P (n, l, l)P (r2 , l, k) > 0, ez´ert n + r1 + r2 oszthat´o a d sz´ammal. A fentiekb˝ol k¨ ovetkezik, hogy n oszthat´o d-vel, ´es ezt kellett bel´ atnunk. Bevezetem a k¨ ovetkez˝ o k´et definici´ ot. Z´ art oszt´ alyok definici´ oja egy Markov-l´ anc ´ allapotter´ eben. Legyen adva egy X0 , X1 , . . . Markov-l´ anc valamely E = {E1 , E2 , . . . } ´ allapotter´en P (j, k) 1 l´ep´eses ´ atmenetval´ osz´ın˝ us´egekkel. Azt mondjuk, hogy egy allapott´er egy z´ art P C ⊂ E halmaz az ´ P (j, k) = 1, azaz, ha a Markov-l´ anc oszt´ aly´ at alkotja, ha minden Ej ∈ C ´ allapotra Ek ∈C
egy C halmazbeli ´ allapotb´ ol indul, akkor egy val´ osz´ın˝ us´eggel a k¨ ovetkez˝ o l´ep´esben is egy ilyen ´ allapotban marad. Irreducibilis, z´ art oszt´ alyok definici´ oja egy Markov-l´ anc ´ allapotter´ eben. Azt 14
mondjuk, hogy egy Markov-l´ anc ´ allapotter´enek egy z´ art oszt´ alya irreducibilis, ha ¨ onmag´ an ´es az u ¨res halmazon k´ıv¨ ul nincs m´ as olyan r´eszhalmaza, amely z´ art oszt´ aly. Egy Markov-l´ ancot irreducibilisnak h´ıvunk, ha a teljes ´ allapott´er irreducibilis (z´ art) oszt´ aly. Az el˝ oz˝ o eredm´enyb˝ol kiolvashat´ o, hogy ha Ej egy rekurrens a´llapot, akkor az Ej allapot az ¨ ´ osszes olyan ´ allapottal egy¨ utt, amelyek az Ej ´ allapotb´ol indul´ o Markovl´ancban pozit´ıv val´ osz´ın˝ us´eggel el´erhet˝ oek z´art oszt´alyt alkotnak. S˝ot, ez egy irreducibilis z´art oszt´aly. Ugyanis, ha P (n, j, k) > 0 valamely n ≥ 1 sz´amra, akkor l´etezik allapotoknak olyan Ej0 , Ej1 , . . . , Ejn , j0 = j, jn = k sorozata, amelyre P (1, jl−1 , jl ) > 0 ´ minden 1 ≤ l ≤ n sz´amra. Ez´ert mindegyik Ejl , 1 ≤ l ≤ n, ´ allapot, ´ıgy speci´ alisan az Ek ´ allapot is, benne van minden az Ej ´ allapotot tartalmaz´ o z´art oszt´alyban. A tranziens ´ allapotok oszt´alyoz´ asa nem ilyen egyszer˝ uen ´ attekinthet˝ o. Az egyik lehet˝ os´egre a k¨ ovetkez˝ o feladat mutat p´eld´at. Feladat. Legyen X1 , X2 , . . . bolyong´ as a d-dimenzi´ os t´eren. Ez irreducibilis Markovl´ anc (azaz egyetlen irreducibilis oszt´ alyb´ ol ´ all), amelynek elemei 2 peri´ odikusak. Ha d = 1 vagy d = 2 akkor ennek az oszt´ alynak az elemei null rekurrens ´ allapotok, ha d ≥ 3 akkor tranziens ´ allapotok. L´ atni fogunk p´eld´at olyan Markov-l´ancokra is, amelyeknek tranziens a´llapotai nem tartoznak egyetlen z´art oszt´alyba sem. Bebizony´ıtom az el˝ oz˝ o t´etel seg´ıts´eg´evel az irreduciblis z´art oszt´alyok n´eh´ any tulajdons´ag´ at. T´ etel Markov-l´ anc irreducibilis z´ art oszt´ alyainak tulajdons´ agair´ ol. Legyen C egy X0 , X1 , . . . , P (n, j, k) = P (Xn = Ek |X0 = Ej ) ´ atmenetval´ osz´ın˝ us´egekkel rendelkez˝ o Markov-l´ anc E = {E1 , E2 , . . . } ´ allapotter´enek irreducibilis, z´ art oszt´ alya. Ekkor minden Ek ∈ C ´es El ∈ C, ´ allapotp´ arra az El ´ allapot el´erhet˝ o az Ek ´ allapotb´ ol, azaz l´etezik olyan r pozit´ıv eg´esz sz´ am, amelyre P (r, k, l) > 0. Egy irreducibilis oszt´ aly minden elem´enek ugyanaz a peri´ odusa, ´es egy irreducibilis oszt´ aly minden eleme egyidej˝ uleg, tranziens, null-rekurrens vagy pozit´ıv rekurrens ´ allapot. Ha Ej a Markov-l´ anc rekurrens ´ allapota, akkor az el˝ oz˝ o t´etelben defini´ alt C(j) halmaz, amely azokb´ ol az ´ allapotokb´ ol ´ all, amelyeket az Ej ´ allapotb´ ol pozit´ıv val´ osz´ın˝ us´eggel el lehet ´erni, irreducibilis, z´ art oszt´ aly. Minden olyan z´ art, irreducibilis oszt´ aly, amely tartalmaz egy Ej rekurrens ´ allapotot megegyezik egy ilyen C(j) oszt´ allyal. A t´etel bizony´ıt´ asa. Adva egy C z´art oszt´aly ´es egy Ek ∈ C ´ allapot defini´aljuk azt a C (k) ⊂ C halmazt, amely azokb´ ol az Ep ∈ C ´ allapotokb´ ol ´ all, amelyekre P (n, k, p) > 0 valamely n sz´amra. Azt ´ all´ıtom, hogy C (k) is z´art oszt´aly. Innen k¨ ovetkezik a T´etel els˝ o ´ all´ıt´ asa, mert ha a C halmaznak van olyan ´ allapota, amely nem ´erhet˝ o el az Ek allapotb´ol, azaz ha l´etezik olyan El ∈ C ´ ´ allapot, amelyre P (n, k, l) = 0 minden pozit´ıv (k) eg´esz n sz´amra, akkor C a C halmaz olyan nem u ¨res, val´ odi r´eszhalmaza, (mert C (k) nem u ¨res halmaz, az El ´ allapotot viszont nem tartalmazza), amely z´art oszt´aly. Ez azt jelenti, hogy ebben az esetben C nem irreducibilis. 15
Vil´ agos, hogy
P
P (n, k, l) = 1 minden n = 1, 2, . . . sz´amra, mert E \ C (k)
l:El ∈C (k)
csak olyan El ´ allapotokat tartalmaz, amelyekre P (n,P k, l) = 0 minden n = 1, 2, . . . sz´amra. Azt ´ all´ıtom, hogy ha El ∈ C (k) , akkor a P (n, l, p) = 1 rel´ aci´onak is p:Ep ∈C (k)
teljes¨ ulnie kell minden n = 1, 2, . . . sz´amra, amib˝ ol k¨ ovetkezik, hogy C (k) z´art oszt´aly. A bizony´ o ´ all´ıt´ as igaz, mert ellenkez˝ o esetben lenne olyan n ≥ 1 sz´am, amelyP ıtand´ re P (n, l, p) < 1. Ekkor l´etezik olyan r sz´am, amelyre P (r, k, l) > 0, ´es p:Ep ∈C (k) P P P P (n + r, k, ¯l) ≤ P (r, k, ¯l) + P (r, k, l) P (n, l, p) = 1 − P (r, k, l) + ¯ ¯ p:Ep ∈C (k) l:El¯∈C (k) l:El¯∈E\{El } P P (r, k, l) P (n, l, p) < 1, ´es ez ellentmond´as. p:Ep ∈C (k)
Az irreducibilis oszt´alyok m´ ar bizony´ıtott tulajdons´ag´ ab´ ol k¨ ovetkezik az el˝ oz˝ o t´etel bizony´ıt´ as´anak befejez´es´ehez hasonl´oan, hogy egy ilyen oszt´aly minden elem´enek ugyanannyi a peri´ odusa. Az el˝ oz˝ o t´etelben l´attuk, hogy egy rekurrens Ej a´llapotra a C(j) halmaz az ´ allapott´er egy z´art oszt´alya. Tov´ abb´a, ha C¯ ⊂ C(j) nem u ¨res z´art oszt´aly, ¯ ¯ akkor l´etezik egy Ek ∈ C elem, ´es ez´ert C(j) = C(k) ⊂ C. Ez´ert C(j) irreducibilis z´art oszt´aly. Tov´ abb´a, ha egy irreducibilis z´art oszt´aly tartalmaz egy rekurrens Ej a´llapotot, akkor tartalmazza a z´art C(j) oszt´alyt is, ez´ert megegyezik vele. Innen k¨ ovetkezik, hogy egy irreducibilis z´art oszt´alynak vagy mindegyik eleme tranziens a´llapot vagy megegyezik valamelyik C(j) halmazzal, ahol Ej rekurrens ´ allapot. Egy ilyen oszt´aly minden eleme null rekurrens vagy pozit´ıv rekurrens ´ allapot. A t´etel bizony´ıt´ as´at befejezt¨ uk. Megfogalmazom a fenti eredm´enyek al´ abbi k¨ ovetkezm´eny´et.
K¨ ovetkezm´ eny. Legyen X0 , X1 , . . . Markov-l´ anc P (n, j, k) = P (Xn = Ek |X0 = Ej ) ´ atmenetval´ osz´ın˝ us´egekkel egy E = {E1 , E2 . . . } ´ allapott´eren. Bontsuk fel az E allapotteret az E = R ∪ T k´eplettel az R rekurrens ´es T tranziens ´ ´ allapotokb´ ol ´ all´ o halmazok uni´ ojak´ent. A R halmaz felbonthat´ o C(j) diszjunkt, irreducibilis, z´ art oszt´ alyok uni´ ojak´ent. Ha Ek , El ∈ C(j) az R halmaz egy irreducibilis, z´ art C(j) oszt´ aly´ ara, akkor F (k, l) = 1 a (10′ ) k´epletben defini´ alt F (·, ·) f¨ uggv´ennyel. Bizony´ıt´ as. A megfogalmazott eredm´enyek k¨ ovetkeznek a Markov-l´anc irreducibilis z´art oszt´alyainak ´es egy Markov-l´anc ´ allapotainak tulajdons´agair´ ol sz´ol´ o t´etelek eredm´enyeib˝ol. Azt kell m´eg megmutatnunk, hogy ha k´et az ut´ obbi t´etel megfogalmaz´as´aban defini´alt C(j) ´es C(k) halmaz nem diszjunkt, akkor C(j) = C(k). De ebben az esetben l´etezik egy El ∈ C(j) ∩ C(k) ´ allapot, ´es C(j) = C(l) = C(k). A fent megfogalmazott k¨ ovetezm´enyben egy Markov-l´anc rekurrens a´llapotainak halmaz´ at felbontottuk irreducibilis, z´art halmazok uni´ojak´ent. A tranziens a´llapotok halmaz´ anak nincs ilyen egy´ertelm˝ u le´ır´asa. Ennek megmutat´ asa ´erdek´eben a bolyong´asok ´ allapotter´enek le´ır´as´ar´ ol sz´ol´ o feladatot kieg´esz´ıtem a k¨ ovetkez˝ o p´eld´aval. P´ elda. Defini´ aljuk a k¨ ovetkez˝ o Markov-l´ ancot a k´et-dimenzi´ os t´er eg´esz koordin´ at´ aj´ u r´ acspontjain: Ha a Markov-l´ anc valamely (j, k), j 6= 0 pontban van, akkor a k¨ ovetkez˝ o 1 osz´ın˝ us´eggel l´ep a (j−1, k), (j+1, k), (j, k+1), (j, k−1) szomsz´ed l´ep´esban egyforma 4 val´ 16
pontok valamelyik´ebe. Ha a Markov-l´ anc valamely (0, k) alak´ u pontban van, akkor a k¨ ovetkez˝ o l´ep´esben 12 val´ osz´ın˝ us´eggel l´ep a (0, k + 1) vagy a (0, k − 1) pontba. Ennek a Markov-l´ ancnak a (0, k), k = 0, ±1, ±2, . . . alak´ u pontok a rekurrens ´ allapotai, amelyek irreducibilis z´ art oszt´ alyt alkotnak. Ennek elemei null-rekurrens, 2 peri´ odus´ u´ allapotok. A (j, k), j 6= 0 alak´ u pontok tranziensek. Egy ilyen ´ allapotb´ ol kiindul´ o Markov-l´ anc 1 val´ osz´ın˝ us´eggel eljut a rekurrens ´ allapotokb´ ol ´ all´ o halmazba, ez´ert nincs olyan irreducibilis z´ art oszt´ aly, amely ezeket tartalmazza. Feladat: Bizony´ıtsuk be a fenti p´elda ´ all´ıt´ as´at. Egy irreducibilis Markov-l´ancokr´ ol sz´ol´ o ´ all´ıt´ ast fogjuk bebizony´ıtani, azaz olyan Markov-l´ancot fogunk tekinteni, amelynek ´ allapottere egyetlen, z´art oszt´aly. Az ismertetett t´etel felt´etelt ad arra, hogy mikor van egy ilyen Markov-l´ancnak stacion´arius eloszl´ asa. T´ etel irreducibilis Markov-l´ ancok stacion´ arius eloszl´ as´ ar´ ol. Legyen X0 , X1 , . . . irreducibilis, aperi´ odikus Markov-l´ anc P (n, j, k) = P (Xn = Ek |X0 = Ej ) ´ atmenetval´ osz´ın˝ us´egekkel egy E = {E1 , E2 , . . . } ´ allapott´eren. a) Ha a Markov-l´ anc ´ allapotai pozit´ıv rekurrensek, akkor az uj = lim P (n, i, j) > n→∞
0 hat´ ar´ert´ekek l´eteznek, uj = µ1j , ahol a µj sz´ amok a (2) formul´ aban vannak defini´ alva. Az uj sz´ amok, Ej ∈ E, a Markov-l´ anc stacion´ arius eloszl´ as´ at defini´ alj´ ak, azaz teljes´ıtik a (13) ´es (14) formul´ akat. b) Megford´ıtva, ha a Markov-l´ ancnak van uj , Ej ∈ E, stacion´ arius eloszl´ asa, akkor a Markov-l´ anc ergodikus, azaz pozit´ıv rekurrens ´ allapotokkal rendelkezik, (´es aperi´ odikus). A Markov-l´ anc (egyetlen) stacion´ arius eloszl´ asa teljes´ıti az uj = µ1j , Ej ∈ Ej , azonoss´ agot. A t´etel bizony´ıt´ asa. Tekints¨ uk el˝ osz¨ or azt az esetet, amikor az a) r´esz felt´etelei teljes¨ ulnek. Az egy Markov-l´anc egy ´ allapot´ anak jellemz´es´er˝ ol sz´ol´ o t´etelben bizony´ıtott (12) formul´ ab´ ol ´es a Markov-l´anc ´ allapotainak tulajdons´agair´ ol sz´ol´ o t´etelb˝ ol k¨ ovetkezik, 1 1 1 hogy lim P (n, i, j) = F (i, j) µj = µj . Azt kell m´eg bel´ atnunk, hogy az uj = µj , Ej ∈ E, n→∞
sz´amok teljes´ıtik a (13) ´es (14) azonoss´agot. El˝osz¨ or azt mutatom meg, hogy uj =
X
uk P (m, k, j)
minden m = 1, 2, . . . , sz´amra.
(15)
k:Ek ∈E
Ennek ´erdek´eben ´ırjuk fel a P (n + m, i, j) =
X
P (n, i, k)P (m, k, j)
k:Ek ∈E
´es pr´ ob´ aljunk n → ∞ limeszt venni az azonoss´ag mind a k´et oldal´ an, felhaszn´alva azt, hogy lim P (n + m, i, j) = uj ´es lim P (n, i, k) = uk . Mivel a jobb oldalon szerepl˝o n→∞
n→∞
17
P (m, k, j) egy¨ utthat´ok ¨ osszege (r¨ ogz´ıtett j-re ´es a k v´ altoz´ o szerint o¨sszegezve) lehet divergens is, egyel˝ ore csak az al´ abbi a k´ıv´antn´ al gyeng´ebb ¨ osszef¨ ugg´est tudjuk fel´ırni (felhaszn´ alva, hogy a jobb-oldalon szerepl˝o sz´amok mind nem-negat´ıvak): X uj ≥ uk P (m, k, j) (15a) k:Ek ∈E
Hasonl´ oan a
P
P (n, i, k) = 1 azonoss´agb´ol kapjuk n → ∞ hat´ar´ atmenettel, hogy
k:Ek ∈E
s=
X
uk ≤ 1.
(16)
k:Ek ∈E
Ezt az egyenl˝otlens´eget felhaszn´alva, ´es ¨ osszegezve a (15a) egyenl˝otlens´egeket a j v´ altoz´ o szerint, azt kapjuk, hogy X X X s= uj ≥ uk P (m, k, j) j:Ej ∈E
=
X
k: Ek ∈E
mert
P
j:Ej ∈E k:Ek ∈E
uk
X
j:Ej ∈E
P (m, k, j) =
X
uk = s,
k: Ek ∈E
P (m, k, j) = 1 minden k indexre. Mivel az utols´ o egyenl˝otlens´egsor bal
j:Ej ∈E
´es jobb oldala egyenl˝o (´es v´eges), a felhaszn´alt (15a) egyenl˝otlens´egekben minden¨ utt azonoss´agnak kell ´ allni, teh´at a (15) formula ´erv´enyes. Ha a (15) formul´ at m = 1 v´ alaszt´ assal tekintj¨ uk, megkapjuk a (14) k´epletet. Tekints¨ uk u ´jb´ ol a (15) formul´ at tetsz˝oleges j sz´ammal, ´es tartsunk v´egtelenhez az m param´eterrel. Ekkor felhaszn´alva a (16) formul´ at (pontosabban csak azt, hogy az ott tekintett ¨ osszeg v´eges) azt kapjuk, hogy X X uj = uk uj = uj uk . k:Ek ∈E
Mivel uj =
1 µj
k:Ek ∈E
> 0, innen k¨ ovetkezik a (13) rel´ aci´o.
R´ at´erek a b) r´esz b´ızony´ıt´ as´ara. Megmutatom n szerinti teljes indukci´ oval a Chapman–Kolmogorov egyenlet seg´ıts´eg´evel, hogy a b) esetben teljes¨ ul a (14) k´eplet k¨ ovetkez˝ o a´ltal´ anos´ıt´ asa is. X uj = ui P (n, i, j) minden j = 1, 2, . . . ´es n = 1, 2, . . . sz´amra. (14′ ) i:Ei ∈E
Val´ oban, ha a (14′ ) formula igaz az n sz´amra, akkor X X X ui P (n + 1, i, j) = ui P (n, i, k)P (k, j) i:Ei ∈E
i:Ei ∈E
=
X
k:Ek ∈E
k:Ek ∈E
P (k, j)
X
i:Ei ∈E
18
ui P (n, i, k) =
X
k:Ek ∈E
P (k, j)uk = uj ,
teh´at a (14′ ) azonoss´ag igaz n + 1-re is. Alkalmazzunk n → ∞ hat´ar´ atmenetet a (14′ ) k´epletben. Azt a´ll´ıtom, hogy a Markov-l´anc ergodikus, minden i ´es j indexre l´etezik a lim P (n, i, j) = µ1j > 0 n→∞
(2) k´epletben defini´alt hat´ar´ert´ek, ´es uj =
X
i:Ei ∈E
ui
1 µj
minden j = 1, 2, . . . sz´amra.
(17)
Val´ oban, mivel irreducibilis Markov-l´ancot tekint¨ unk, a Markov-l´anc minden a´llapota egyszerre tranziens, null-rekurrens vagy pozit´ıv rekurrens. Viszont az els˝ o k´et ′ esetben lim P (n, i, j) = 0, ez´ert a (14 ) formul´ aban elv´egzett hat´ar´ atmenet azt adn´a, n→∞
hogy uj = 0 minden j indexre. Ez viszont ellentmond a (13) rel´ aci´onak. Ez´ert a Markovl´anc a´llapotai pozit´ıv rekurensek. Mivel feltett¨ uk, hogy a Markov-l´anc aperi´ odikus, ez´ert ergodikus, az ´ atmenet val´ osz´ın˝ us´egeknek az el˝ oz˝ o bekezd´esben fel´ırt hat´ar´ert´ekeik vannak, ´es teljes¨ ul a (17) formula. A (17) ´es (13) formul´ak alapj´ an viszont uj =
X
i:Ei ∈E
ui
1 1 X 1 = ui = µj µj µj
minden j = 1, 2, . . . sz´amra.
i:Ei ∈E
Ez azt jelenti, hogy egy ergodikus Markov-l´ancnak uj = stacion´arius eloszl´ asa.
1 µj ,
Ej ∈ Ej , az egyetlen
Feladat: L´ assuk be az el˝ oz˝ o feladat eredm´eny´enek a seg´ıts´eg´evel, hogy egy X0 , X1 , . . . , irreducibilis, ergodikus Markov-l´anc eloszl´ asa tetsz˝oleges kezdeti eloszl´ as eset´en konverg´al a Markov-l´anc stacion´arius eloszl´ as´ahoz, ha n → ∞, azaz lim P (Xn = Ej ) = uj n→∞ minden uj ´ allapotra. A kor´ abbi eredm´enyekben feltettem, hogy a tekintett Markov-l´anc aperi´ odikus. Ezt els˝ osorban k´enyelmi szempontok miatt tettem. Peri´ odikus Markov-l´ancok vizsg´alata hasonl´oan t¨ort´enhet, ´es az eredm´enyek is hasonl´oak, csak a jel¨ol´es v´ alik kiss´e bonyolultabb´ a. Ezenk´ıv¨ ul peri´ odikus Markov-l´ancok vizsg´alata visszavezethet˝ o az aperi´ odikus Markov-l´ancok eset´ere. Itt csak r¨oviden ´ attekintem azt, hogy milyen eredm´enyek ´erv´enyesek, ´es milyen ´eszrev´etel seg´ıts´eg´evel kaphatjuk meg azokat. Legyen X0 , X1 , . . . irreducibilis Markov-l´anc egy E = {E1 , E2 , . . . } a´llapott´eren P (n, j, k) ´ atmenetval´ osz´ın˝ us´eggel. Tegy¨ uk fel, hogy a Markov-l´anc a´llapotai pozit´ıv rekurrensek, ´es peri´ odusaik egyenl˝oek valamilyen d ≥ 1 sz´ammal. (Tudjuk, hogy egy irreducibilis Markov-l´anc minden ´ allapota egyszerre, tranziens, null vagy pozit´ıv rekurrens, ´es minden ´ allapotnak ugyanaz a peri´ odusa.) Tekints¨ uk az X0 , X1 , . . . Markov-l´anc ¯ mellett az Xn = Xdn , n = 0, 1, 2, . . . Markov-l´ancot is, amelynek a´llapottere megegyezik az eredeti Markov-l´anc E ´ allapotter´evel, ´es ´ert´eke az n id˝ opontban egyenl˝o az eredeti Markov-l´anc ´ert´ek´evel az nd id˝ opontban. Ez ut´ obbi Markov-l´anc aperi´ odikus, P¯ (j, k) = P (d, j, k) egy l´ep´eses ´ atmenetval´ osz´ın˝ us´egekkel, minden ´ allapota pozit´ıv rekurrens, de allapottere nem felt´etlen¨ ´ ul irreducibilis. Viszont al´ abb megadom e Markov-l´anc a´llapotter´enek a felbont´as´at d darab C0 , . . . , Cd−1 irreducibilis oszt´aly uni´ojara. 19
R¨ ogz´ıts¨ uk mondjuk az E1 ∈ E ´ allapotot, ´es tekints¨ uk minden Ek ∈ E a´llapotra az Nk = {n: P (n, 1, k) > 0} halmazt, azaz azon id˝ opontok halmaz´ at, amely id˝ opontok alatt az E1 ´ allapotb´ol pozit´ıv val´ osz´ın˝ us´eggel jutunk az Ek ´ allapotba. Nem neh´ez bel´ atni, hogy az X0 , X1 , . . . Markov-l´anc d peri´ odusa miatt l´etezik olyan 0 ≤ p ≤ d − 1 sz´am, hogy n = p mod d minden n ∈ Nk sz´amra. Nevezz¨ uk ezt a p sz´amot az Ek a´llapot r(k) rangj´ anak. Defini´ aljuk a Cp ⊂ E, 1 ≤ p ≤ d, halmazokat u ´gy, hogy Ek ∈ Cp akkor ´es ¯0, X ¯ 1 , . . . Markov-l´anc csak akkor, ha r(k) = p. N´emi munk´ aval be lehet l´atni, hogy a X E ´ allapotter´enek felbont´asa irreducibilis z´art oszt´alyokra a Cp , 0 ≤ p ≤ d − 1, halmazokb´ol ´ all. Tov´ abb´a, ha Ek ∈ Cp , El ∈ Cq valamely p ´es q sz´amokkal, akkor P (n, k, l) > 0 csak akkor lehets´eges, ha n = q − p mod d. Ezenk´ıv¨ ul, ha Ek ∈ Cp , ´es P (n, k, l) > 0 valamely n id˝ opontra, akkor El ∈ Cq azzal a q sz´ammal, amelyre n = q − p mod d. A fenti ¨ osszef¨ ugg´esek seg´ıts´eg´evel, ´es haszn´ alva a m´ ar bizony´ıtott eredm´enyeket az ¯0, X ¯ 1 , . . . Markov-l´anc Cp , 1 ≤ p ≤ d − 1, irreducibilis, z´art oszt´alyaira kapjuk, hogy a X d duj = lim P (dn + q − p, i, j) = ha Ei ∈ Cp ´es Ej ∈ Cq n→∞ µj hat´ar´ert´ek l´etezik. Itt a µj sz´am a (2) k´epletben van defini´alva, ´es P (dn + r, i, j) = 0, ha ak a Markov-l´anc r 6= q − p mod p. Tov´ abb´a az is igaz, hogy az uj = µ1j sz´amok alkotj´ (egyetlen) stacion´arius eloszl´ as´at. A r´eszletek bizony´ıt´ as´at elhagyom. R´ at´erek v´eges ´ allapotter˝ u, azaz v´eges sok k¨ ul¨ onb¨oz˝ o ´ert´eket felvev˝o Markov-l´ancok r¨ovid t´argyal´ as´ara. V´eges ´ allapotter˝ u Markov-l´ancok rendelkeznek n´eh´ any extra tulajdons´aggal, amelyeket a k¨ ovetkez˝ o t´etelben fogalmazok meg. Ezenk´ıv¨ ul a sztochaszikus m´ atrixok n´eh´ any line´aris algebrai tulajdons´aga seg´ıt v´eges ´ allapotter˝ u Markov-l´ancok vizsg´alat´aban. T´ etel v´ eges ´ allapotter˝ u Markov-l´ ancok tulajdons´ agair´ ol. Egy v´eges ´ allapotter˝ u Markov-l´ ancnak mindig van pozit´ıv rekurrens ´ allapota, viszont nincs null rekurrens allapota. Egy tranziens ´ ´ allapotb´ ol elind´ıtott Markov-l´ anc 1 val´ osz´ın˝ us´eggel beker¨ ul a Markov-l´ anc rekurrens ´ allapotaib´ ol ´ all´ o halmazba. A t´etel bizony´ıt´ asa. Mivel egy v´eges Markov-l´anc n l´ep´eses ´ atmenetval´ osz´ın˝ us´egeit is egy sztochasztikus m´ atrix adja meg, amelynek m´erete nem f¨ ugg az n sz´amt´ol, ´es egy sztochasztikus m´ atrix sor¨ osszege 1, ez´ert, r¨ogz´ıtve a sztochasztikus m´ atrix i-edik sor´ at valamely i sz´ammal, l´etezik olyan j index ´es pozit´ıv eg´esz sz´amok nk sorozata, amelyekre lim sup P (nk , i, j) > 0. Viszont egy ilyen j indexhez tartoz´o Ej a´llapot pozit´ıv nk →∞
rekurrens, mert sem tranziens, sem null rekurrens nem lehet. Mivel a Markov-l´anc rekurrens ´ allapotaib´ ol ´ all´ o halmaz felbonthat´ o diszjunkt irreducibilis z´art oszt´alyok uni´oj´ara, ´es egy irreducibilis z´art oszt´aly elemei egyidej˝ uleg pozit´ıv vagy null rekurrens allapotok, ez´ert tekintve a Markov-l´anc megszor´ıt´ ´ as´at egy irreducibilis z´art oszt´alyra az el˝ oz˝ o ´ervel´es alapj´ an kapjuk, hogy a Markov-l´ancnak nincs null rekurrens a´llapota. V´eg¨ ul, ha egy tranziens Ei ´ allapotb´ol elind´ıtott Markov-l´anc pozit´ıv val´ osz´ın˝ us´eggel elker¨ uln´e a Markov-l´anc rekurrens ´ allapotaib´ ol ´ all´ o halmazt, akkor (´ ujb´ ol a Markovl´anc v´eges ´ allapottere miatt) l´etezne a Markov-l´ancnak olyan Ej tranziens a´llapota, amelyre lim sup P (nk , i, j) > 0 alkalmas nk sz´amorozattal, ´es ez ellentmond´as. nk →∞
20
Egy Markov-l´anc viselked´es´er˝ ol nagyon hasznos inform´ aci´ot ad az a Markov-l´anc ´tmenetval´ a osz´ın˝ us´egeit megad´o sztochasztikus m´ atrix spektrum´anak, azaz saj´at´ert´ekeinek ´es saj´ atvektorainak az ismerete. Vegy¨ uk ´eszre, hogy egy sztochasztikus m´ atrixnak, ha jobbr´ol szorozzuk meg oszlopvektorokkal, akkor a csupa 1 koordin´ at´ ab´ ol a´ll´ o vektor saj´ atvektor 1 saj´ at´ert´ekkel. Tov´ abb´a 1-n´el nagyobb saj´ at´ert´ekkel rendelkez˝ o (oszlop) saj´ atvektor nem lehets´eges. Azt is tudjuk a line´aris algebr´ab´ ol, hogy egy m´ atrixot ak´ar balr´ol szorozzuk meg egy sorvektorral, ak´ar jobbr´ol egy oszlopvektorral, ugyanazok lesznek a saj´ at´ert´ekei. (A saj´ atvektorai l´enyegesen k¨ ul¨ onb¨ozhetnek.) Feladat. L´ assuk be, hogy egy sztochasztikus m´ atrixnak nem lehet 1-n´el nagyobb saj´at´ert´ekkel rendelkez˝ o (oszlop) saj´ atvektora. Seg´ıts´eg: Mutassuk meg, hogy az eredeti vektor legnagyobb abszolut ´ert´ek˝ u koordin´at´ aj´anak az abszolut ´ert´eke nagyobb vagy egyenl˝o, mint a k´epvektor b´armely koordin´ at´ aj´anak az abszolut ´ert´eke. Tudjuk teh´at, hogy egy sztochasztikus m´ atrixnak l´etezik egy 1 saj´ at´ert´ekkel rendelkez˝ o (sor) saj´ atvektora. Enyhe plusz feltev´esek mellett azt is lehet tudni, hogy ennek osszes koordin´ ¨ at´ aja pozit´ıv, ´es sz´ep esetekben az is igaz, hogy a sztochasztikus m´ atrix osszes t¨obbi saj´ ¨ at´ert´eke szigor´ uan kisebb, mint 1. Ilyen esetben a sztochasztikus m´ atrix n-ik hatv´any´ anak viselked´es´er˝ ol nagyon ´ert´ekes inform´ aci´ot nyerhet¨ unk. Ugyanis fel´ırva a m´ atrix a´ltal meghat´ arozott line´aris transzform´ aci´ot olyan koordin´ atarendszerben, ahol annak a lehet˝ o legegyszer˝ ubb az alakja (ez a Jordan f´ele norm´ alalak haszn´ alat´at jelenti) be lehet l´atni, hogy a k¨ ovetkez˝ o aszimptotikus rel´ aci´o ´erv´enyes. Tekints¨ unk egy tetsz˝oleges nem negat´ıv ´ert´ek˝ u koordin´ at´ akb´ ol ´ all´ o sorvektort, amelyben a koordin´ at´ ak ¨ osszege 1. Ha alkalmazzuk erre a vektorra az ´ atmenetval´ osz´ın˝ us´egek a´ltal meghat´ arozott sztochasztikus m´ atrix n-ik hatv´any´ at, akkor olyan vektort kapunk, amely e m´ atrix 1 saj´ at´ert´ek˝ u saj´ atvektor´at´ ol az (n v´ altoz´ o f¨ uggv´eny´eben) exponenci´alisan kis k¨ ul¨ onbs´eggel t´er el. Ez azt jelenti, hogy a m´ atrix saj´atvektora adja meg a Markov-l´anc stacion´arius eloszl´ as´at, ´es ha a Markov-l´ancot tetsz˝oleges kezdeti eloszl´ assal ind´ıtjuk el, akkor a Markov-l´anc eloszl´ asa az n id˝ o f¨ uggv´eny´eben exponenci´alis sebess´eggel konverg´ al a stacion´arius eloszl´ ashoz. Az el˝ obb v´ azolt gondolatmenet azt mutatja, hogy hasznos olyan eredm´enyeket bizony´ıtani, amelyek megmondj´ak, hogy egy sztochasztikus m´ atrixnak mikor van egyetlen 1 saj´ at´ert´ek˝ u saj´ atvektora. A Markov-l´ancok elm´elet´eben Perron egy t´etele, illetve annak Frobenius ´ altal bizony´ıtott a´ltal´ anos´ıt´ asa hasznos. Ezek az eredm´enyek olyan m´ atrixokkal foglalkoznak, amelyeknek ¨ osszes egy¨ utthat´oja nem negat´ıv. Perron t´etel´et fogom kimondani, ´es r¨oviden jelzem, hogy milyen ´ altal´ anos´ıt´ as´at adta ennek az eredm´enynek Frobenius. Perron t´ etele. Legyen egy A n × n m´eret˝ u n´egyzetes m´ atrix minden eleme szigor´ uan pozit´ıv sz´ am. Az A m´ atrix det(A − λI) karakterisztikus polinomj´ anak, (ahol I az n × nes diagon´ alis egys´egm´ atrix) legnagyobb abszolut ´ert´ek˝ u gy¨ oke szigor´ uan pozit´ıv, egyszeres gy¨ ok, ´es a karakterisztikus polinom ¨ osszes t¨ obbi gy¨ ok´enek az abszolut ´ert´eke szigor´ uan kisebb, mint ez a saj´ at´ert´ek. Az A m´ atrixnak a karakterisztikus polinom legnagyobb saj´ at´ert´ek´ehez tartoz´ o egyszeres saj´ atvektor´ anak mindegyik koordin´ at´ aja szigor´ uan pozi21
t´ıv sz´ am. Ha az A m´ atrix sztochasztikus m´ atrix, azaz minden sor¨ osszege 1-gyel egyenl˝ o, akkor karakterisztikus polinomj´ anak a legnagyobb gy¨ oke 1. Perron t´etele alkalmazhat´o olyan v´eges ´ allapotter˝ u Markov-l´anc vizsg´alat´aban, amelynek o¨sszes egy-l´ep´eses ´ atmenetval´ osz´ın˝ us´egei szigor´ uan pozit´ıvak. Sz´ amunkra a k¨ ovetkez˝ o eredm´eny ´erdekes. A Perron t´ etel egy k¨ ovetkezm´ enye Markov l´ ancok viselked´ es´ er˝ ol. Teljes´ıtse egy E1 , . . . , Em ´ allapotokat tartalmaz´ o Markov l´ anc Π ´ atmenetval´ osz´ın˝ us´eg m´ atrixa a Perron t´etel felt´eteleit. Ekkor a Markov l´ anc irreducibilis, ´es qj = P (X0 = Ej ), 1 ≤ j ≤ m, stacion´ arius eloszl´ asa megegyezik a Π m´ atrix azon 1 saj´ at´ert´ek˝ u q = (q1 , . . . , qm ) m P saj´ atvektor´ aval, amelyre qk = 1. A Markov l´ anc tetsz˝ oleges 0 id˝ opontbeli eloszl´ asa k=1
eset´en a Markov l´ anc n id˝ opontbeli eloszl´ asa (az n v´ altoz´ o szerint) exponenci´ alis sebess´eggel tart a q eloszl´ ashoz, amikor n → ∞.
A k¨ ovetkezm´eny bizony´ıt´ asa. Mivel a tekintett Markov l´anc b´armely a´llapot´ ab´ ol a Markov l´anc b´armely m´ as ´ allapot´ aba pozit´ıv val´ osz´ın˝ us´eggel el lehet jutni (1 l´ep´esben), a Markov l´anc irreducibilis. A Markov l´anc stacion´arius eloszl´ asa megegyezik a Perron t´etel ´ all´ıt´ asa szerint l´etez˝ o q vektorral. A k¨ ovetkezm´eny ´ all´ıt´ as´anak igazol´as´ahoz azt kell m P m´eg megmutatni, hogy tetsz˝oleges p = (p1 , . . . , pm ), pj ≥ 0, 1 ≤ j ≤ k, pj = 1 alak´ u j=1
vektorra lim pΠn = q, ´es a konvergencia exponenci´alis sebess´eg˝ u ebben a rel´ aci´oban. n→∞
Tekints¨ uk a Π m´ atrix J Jordan-f´ele norm´ alalakj´ at, ´es azt az e(1) , . . . , e(m) b´azist, amelyben a Π m´ atrix ezt a Jordan f´ele norm´ alakot veszi fel. Ekkor e(1) = q, a m´ atrix 1 saj´ at´ert´ek˝ u saj´ atvektora, egy 1 × 1 m´eret˝ u Jordan kalick´ aban van, ´es a Jordan-f´ele norm´ alalakban szerepl˝o ¨ osszes t¨obbi saj´ at´ert´ek szigor´ uan kisebb, mint 1. Ez´ert, ha a m P Markov l´anc p = (p1 , . . . , pm ) eloszl´ asvektor´at fel´ırjuk p = c1 q + cj e(j) alakban, j=2
(n) (n) (p1 , . . . , pm )
= pΠ eloszl´ as´ara a p(n) = akkor a Markov l´anc n id˝ opontbeli p = m P c1 q + c(j, n)e(j) rel´ aci´o teljes¨ ul alkalmas exponenci´alisan kicsi c(j, n) egy¨ utthat´okkal, (n)
n
j=2
azaz l´etezik olyan 0 < λ < 1 sz´am, amelyre ´erv´enyes a lim c(j, n)λ−n = 0 rel´ aci´o n→∞ m P cj e(j) minden 2 ≤ j ≤ m sz´amra. Azt kell m´eg ´eszrevenni, hogy a p = c1 q + j=2 ! m n m m P (n) P P P (j) = c1 , rel´ aci´oban c1 = 1, mert 1 = lim pj = lim c1 qj + es c(j, n) n→∞ j=1
ahol e
(j)
=
(j) (j) (e1 , . . . , em ),
n→∞
j=1
j=2
s=1
2 ≤ j ≤ m.
A Perron t´etelben tekintett m´ atrixok irreducibilis ´es 1 peri´ odus´ u Markov-l´ancok vizsg´alat´aban haszn´ alhat´ oak. Algebrai m´ odon jellemezhet˝ oek az irreducibilis Markovl´ancok ´ atmenetval´ osz´ın˝ us´egei ´ altal meghat´ arozott sztochasztikus m´ atrixok a´ltal´ anosan is. Be lehet vezetni a nem-negat´ıv elem˝ u, u ´gynevezett irreducibilis m´ atrixok fogalm´ at az 22
´ltal´ a anos esetben, amely az irreducibilis Markov-l´ancok ´ altal meghat´ arozott sztochasztikus m´ atrixok term´eszetes ´ altal´ anos´ıt´ asa. A Perron t´etel Frobenius a´ltal bizony´ıtott altal´ ´ anos´ıt´ asa irreducibilis, nem-negat´ıv elem˝ u m´ atrixok legnagyobb abszolut ´ert´ek˝ u saj´at´ert´ekeinek ´es a hozz´ ajuk tartoz´o saj´ atvektorok jellemz´es´et adja meg. Ennek megfogalmaz´ asa, amelyet ebben az ismertet´esben elhagyok, bonyolultabb, mint az eredeti Perron t´etel´e. Ez a bonyolults´ ag azzal f¨ ugg ¨ ossze, hogy Frobenius eredm´enye nemcsak az aperi´ odikus, hanem az irreducibils, peri´ odikus Markov-l´ancok viselked´es´et is le´ırja. Kieg´ esz´ıt´ es. A fel´ uj´ıt´ asi t´ etel bizony´ıt´ asa. Legyenek Y1 , Y2 . . . f¨ uggetlen, egyforma eloszl´ as´ u pozit´ıv eg´esz ´ert´ek˝ u val´ osz´ın˝ us´egi n P v´ altoz´ ok, Sn = Yk , n = 1, 2, . . . , ´es defini´aljuk a k¨ ovetkez˝ o mennyis´egeket: fk = k=1
P (Y1 = k), k = 1, 2, . . . , µ = EY1 =
∞ P
kfk , B(ω) = {S1 (ω), S2 (ω) . . . }, un =
k=1
P ({ω: n ∈ B(ω)}), n = 1, 2, . . . , ´es u0 = 1. Vegy¨ uk ´eszre, hogy teljes¨ ulnek a ∞ X
fk = 1,
´es
fk ≥ 0
minden k = 1, 2, . . . sz´amra,
(A1)
k=1
valamint az un = f1 un−1 + f2 un−2 + · · · fn u0 ,
n = 1, 2, . . .
(A2)
rel´ aci´ok. Az (A1) formula azt fejezi ki, hogy az Y1 val´ osz´ın˝ us´egi v´ altoz´ o ´ert´eke 1 val´ osz´ın˝ us´eggel egy pozit´ıv eg´esz sz´am. Az (A2) formula az´ert igaz, mert fj un−j annak a val´ osz´ın˝ us´ege, hogy Y1 = j, ´es Y2 + · · · Yl = n − j valamilyen l ≥ 2 sz´amra, ha 1 ≤ j < n, ´es fn u0 annak a val´ osz´ın˝ us´ege, hogy Y1 = n. (Vegy¨ uk ´eszre, hogy mivel az Yj val´ osz´ın˝ us´egi v´ altoz´ ok f¨ uggetlenek ´es azonos eloszl´ as´ uak, ez´ert um = P ({ω: Y2 (ω) + · · · Yl (ω) = m valamely l = 2, 3, . . . , sz´amra}.) Tov´ abb´a a fel´ uj´ıt´ asi t´etel felt´etelei szerint az A = {j : fj > 0} halmazban szerepl˝o sz´amok legnagyobb k¨ oz¨ os oszt´oja 1. Ez´ert a fel´ uj´ıt´ asi t´etel k¨ ovetkezik az al´ abb megfogalmazott ´es k´es˝obb bebizony´ıtand´ o eredm´enyb˝ol. T´ etel A. Legyenek f1 , f2 , . . . pozit´ıv eg´esz sz´ amok, amelyek teljes´ıti az (A1) rel´ aci´ ot, ´es amelyekre az A = {j : fj > 0} halmazban szerepl˝ o sz´ amok legnagyobb k¨ oz¨ os oszt´ oja 1. Legyen u0 = 1, ´es defini´ aljuk az un , n = 1, 2, . . . , sz´ amokat rekurz´ıve az (A2) formula seg´ıts´eg´evel. Ekkor ∞ X 1 lim un = , ahol µ = fk . (A3) n→∞ µ k=1
A µ = ∞ esetben az (A3) formula a lim un = 0 azonoss´ agot adja. n→∞
A T´etel A ´ all´ıt´ as´at a k¨ ovetkez˝ o Propozici´ o seg´ıts´eg´evel fogjuk bebizony´ıtani. 23
Propozici´ o. Teljes¨ uljenek a T´etel A felt´etelei. Vezess¨ uk be a T´etel A jel¨ ol´eseit haszn´ alva az η = lim sup un mennyis´eget. Ekkor l´etezik olyan n1 < n2 < . . . sz´ amsorozat, n→∞
amelyre igaz, hogy
lim unj +k = η = lim sup un
j→∞
minden k = 0, ±1, ±2, . . . sz´ amra.
(A4)
n→∞
El˝osz¨ or megmutatom, hogy hogyan k¨ ovetkezik a T´etel A a Propozici´ o a´ll´ıt´ as´ab´ ol. Vezess¨ uk be a ρk = fk+1 + fk+2 + · · · , k = 0, 1, 2, . . . , mennyis´egeket. Ekkor az ∞ P (A1) k´eplet szerint ρ0 = 1, ´es a µ mennyis´eget µ = ρk alakban ´ırhatjuk. Val´ oban, k=0
µ=
∞ X
k=1
kfk =
∞ X
k(ρk−1 − ρk ) =
k=1
∞ X
ρk .
k=0
Tov´ abb´a az (A2) formul´ ab´ ol k¨ ovetkezik az al´ abbi azonoss´ag. ρ0 uN + ρ1 uN −1 + · · · + ρN u0 = 1 minden N = 0, 1, 2, . . . sz´amra.
(A5)
Val´ oban az (A2) formul´ at ¨ osszegezve 1 ≤ n ≤ N -re kapjuk, hogy u1 + · · · + uN = uN −1 f1 + uN −2 (f1 + f2 ) + · · · + u0 (f1 + · · · + fN ) = uN −1 (ρ0 − ρ1 ) + uN −2 (ρ0 − ρ2 ) + · · · + u0 (ρ0 − ρN ) = ρ0 (uN −1 + · · · + u0 ) − (ρ1 uN −1 + ρ2 uN −2 + · · · + ρN u0 ). Innen, mivel ρ0 = 1 ´es u0 = 1 uN = u0 − (ρ1 uN −1 + ρ2 uN −2 + · · · + ρN u0 ) = uN + 1 − (ρ0 uN + ρ1 uN −1 + ρ2 uN −2 + · · · + ρN u0 ), ahonnan k¨ ovetkezik az (A5) azonoss´ag. Megjegyz´es: Defini´ aljuk P (Yj = k) = fk , j = 1, 2, . . . , eloszl´ as´ u f¨ uggetlen, egyforma p P eloszl´ as´ u Y1 , Y2 , . . . val´ osz´ın˝ us´egi v´ altoz´ ok Sp = Yj , p = 1, 2, . . . r´eszlet¨ osszegeinek j=1
a sorozat´at. Ekkor az un sz´am annak a val´ osz´ın˝ us´ege, hogy e r´eszlet¨ osszeg sorozat valamelyik tagja felveszi az n ´ert´eket. Az (A5) azonoss´ag azt a t´enyt fejezi ki, hogy e r´eszlet¨ osszeg sorozat minden N = 0, 1, 2, . . . sz´amra 1 val´ osz´ın˝ us´eggel felvesz egy az N sz´amn´ al nagyobb ´ert´eket. Ugyanis az uk ρN −k , 0 ≤ k ≤ N , sz´am annak a val´ osz´ın˝ us´ege, hogy az S0 , S1 , . . . sorozat megl´ atogatja a k-pontot, majd ezut´ an egy az N sz´amn´ al nagyobb ´ert´eket vesz fel.
Bizony´ıtsuk be a T´etel A ´ all´ıt´ as´at (a Propozici´ o seg´ıts´eg´evel) el˝ osz¨ or a µ = ∞ esetben. Alkalmazzuk az (A5) formul´ at olyan N = nj indexekre, amelyek teljes´ıtik a 24
Propozici´ o´ all´ıt´ as´at, azaz lim unj −k = η = lim sup un minden k > 0 sz´amra, ´es hajtsuk j→∞
n→∞
v´egre a j → ∞ hat´ar´ atmenetet. Ekkor az (A5) formul´ ab´ ol, illetve a µ =
∞ P
ρk = ∞
k=0
azonoss´agb´ol k¨ ovetkezik, hogy η = lim sup un = 0. Viszont mivel un ≥ 0 minden n ≥ 0 n→∞
indexre, innen ad´ odik a lim un = 0 rel´ aci´o ebben az esetben. n→∞
A µ < ∞ esetben mutassuk meg el˝ osz¨ or azt, hogy η = µ1 . Az (A2) formul´ ab´ ol l´athat´ o, hogy 0 ≤ un ≤ 1 minden n indexre. Alkalmazzuk az (A5) formul´ at az N = nj sz´amokkal, ahol az nj sz´amok a Propozici´ oban szerepl˝o indexeket jel¨olik, ´es tartsunk a j index-szel v´egtelenhez. Nem neh´ez bel´ atni, felhaszn´alva a lim unj −k ρk = ρk η rel´ aci´ot j→∞
minden fix k indexre, hogy a µ =
∞ P
ρk < ∞ esetben a j → ∞ hat´ar´ atmenet az (A5)
k=0
formul´ aban az
η(ρ0 + ρ1 + · · · ) = 1 azonoss´aghoz vezet, ahonnan η =
1 µ.
A T´etel A bizony´ıt´ as´anak befejez´es´ehez el´eg azt megmutatni, hogy ak´arhogy r¨ogz´ıt¨ unk egy ε > 0 sz´amot nem lehet a pozit´ıv eg´esz sz´amok olyan nj r´eszsorozat´at tal´ alni, amelyre lim unj = η0 valamely 0 ≤ η0 ≤ η − ε sz´ammal. Val´ oban, ha lenne ilyen j→∞
ε n ≥ n0 eset´eben alkalmas sorozat, akkor felhaszn´alva azt, hogy 0 ≤ un ≤ η + 2µ n0 k¨ usz¨ obindex-szel, ´es 0 ≤ un ≤ 1 minden n-re az (A5) formula baloldal´ an szerepl˝o kifejez´est a k¨ ovetkez˝ o m´ odon becs¨ ulhetn´enk fel¨ ulr˝ ol N = nj indexre el´eg nagy j sz´amra.
ρ0 uN + ρ1 uN −1 + · · · + ρN u0 ∞ X ε ε ρ0 + (ρ1 + · · · + ρK ) η + + ρj ≤ η0 + 2µ 2µ j=K+1
≤ (η0 − η) + η
K X
ρl +
l=0
ε 2µ
K X
ρl +
l=0
ε ε ε ε ≤ −ε + 1 + + ≤ 1 − , 4 2 4 4
ha el˝ osz¨ or a K, majd att´ol f¨ ugg˝oen a j indexet v´ alasztjuk el´eg nagyra. A sz´amol´ asban ∞ P kihaszn´aljuk az ηµ = 1 ´es µ = ρl azonoss´agokat. A kapott egyenl˝otlens´eg ellentl=0
mond az (A5) rel´ aci´onak. Ez´ert a k´ıv´ant tulajdons´ag´ u η0 nem l´etezik, hanem teljes¨ ul a lim un = η = µ1 azonoss´ag. n→∞
A bizony´ıt´ as befejez´es´ehez be kell m´eg bizony´ıtani a Propozici´ ot. Ennek ´erdek´eben v´ alasszuk ki a pozit´ıv eg´esz sz´amok egy olyan nj r´eszsorozat´at, amelyre l´etezik minden k = 0, ±1, ±2, . . . sz´amra a lim unj +k = wk hat´ar´ert´ek, tov´ abb´a w0 = η = lim sup un . j→∞
n→∞
Ilyen r´eszsorozat l´etezik. Val´ oban, mivel az un sorozat korl´ atos, ez´ert ki lehet (0) (0) v´ alasztani pozit´ıv eg´esz sz´amok egy olyan n1 , n2 , . . . r´eszsorozat´at, amelyre teljes¨ ul a lim un(0) = lim sup un = η rel´ aci´o. Ezut´an szukcessz´ıve ki lehet v´ alasztani n→∞
j
n→∞
25
(l)
(l)
a term´eszetes sz´amok egym´ asba skatuly´azott n1 , n2 , . . . , r´eszsorozatait minden l = 1, 2, . . . sz´amra u ´gy, hogy teljes¨ ulj¨on a lim un(l)+k = wk rel´ aci´o minden |k| ≤ l eg´esz n→∞
sz´amra valamely wk k´ıv´ant tulajdons´ag´ u Propozici´ oban el˝ o´ırt teljes¨ ul´ese eset´en wk
j
hat´ar´ert´ekkel. Ezut´an a szok´ asos ´ atl´ os elj´ar´ assal megkaphatjuk a unj sorozatot. Azt ´ all´ıtom, hogy az ´ıgy kapott sorozat teljes´ıti a tulajdons´agokat. Azt kell bel´ atni, hogy a Propozici´ o felt´eteleinek = η minden k = 0, ±1, ±2, . . . sz´amra.
Az eddig bizony´ıtott ´ all´ıt´ asokb´ol csak az k¨ ovetkezik, hogy 0 ≤ wk ≤ η minden k = 0, ±1, ±2, . . . sz´amra, ´es w0 = η. Ahhoz, hogy a m´eg bizony´ıtand´ o a´ll´ıt´ ast igazoljuk, el˝ osz¨ or megmutatom, hogy teljes¨ ul a wk =
∞ X
fl wk−l
(A6)
l=1
azonoss´ag minden k = 0, ±1, ±2, . . . sz´amra. Val´ oban, defini´aljuk a (j) Vk
=
unj +k , ha nj + k ≥ 0 0, ha nj + k < 0
sz´amokat minden j = 1, 2, . . . ´es k = 0, ±1, ±2, . . . indexre. Ekkor az (A2) formula alapj´ an ∞ X (j) (j) Vk = fl Vk−l , l=1
´es innen j → ∞ hat´ar´ atmenettel megkapjuk az (A6) formul´ at. Megfogalmazom a k¨ ovetkez˝ o Lemmm´at. Lemma. Legyen wk , k = 0, ±1, ±2, . . . , val´ os sz´ amok olyan sorozata, amely teljes´ıti az (A6) rel´ aci´ ot valamely az (A1) formul´ at kiel´eg´ıt˝ o fk sorozattal. Legyen tov´ abb´ a0≤ wk ≤ η minden k = 0, ±1, ±2, . . . indexre, w0 = η, ´es legyen az A = {j : fj > 0} halmazban szerepl˝ o sz´ amok legnagyobb k¨ oz¨ os oszt´ oja 1. Ekkor wk = η minden k = 0, ±1, ±2, . . . indexre. A Propozici´ o az (A6) rel´ aci´o ´es a Lemma k¨ ovetkezm´enye. Ez´ert elegend˝ o a Lemm´ at bel´ atni. A lemma bizony´ıt´ asa. Mivel az fk sorozat teljes´ıti az (A1) rel´ aci´ot, ´es 0 ≤ wk ≤ w0 = η minden k indexre, az (A6) formula adja k = 0 v´ alaszt´ assal, hogy w−k = η minden k ∈ A indexre. Ezut´an az (A6) rel´ aci´ot k, −k ∈ A, alak´ u sz´amokra alkalmazva kapjuk, hogy w−(k1 +k2 ) = η, ha k1 , k2 ∈ A. Folytatva ezt az elj´ar´ ast azt kapjuk, hogy minden k = α1 k1 + · · · + αs ks alak´ u line´aris kombin´aci´ora, ahol α1 , . . . , αs pozit´ıv eg´esz sz´amok, ´es k1 , . . . , ks ∈ A igaz a w−k = η rel´ aci´o. M´asr´eszt azt ´ all´ıtom, hogy mivel a A halmazban lev˝ o sz´amok legnagyobb k¨ oz¨ os oszt´oja 1, l´etezik olyan k0 k¨ usz¨ obindex, hogy minden k ≥ k0 sz´am fel´ırhat´ o a fenti alak´ u k = α1 k1 + · · · + αs ks line´aris kombin´aci´ok´ent. Val´ oban, alapvet˝ o sz´amelm´eleti 26
eredm´enyek alapj´ an l´eteznek olyan a1 , . . . , aj ∈ A sz´amok, ´es β1 , . . . , βj eg´esz, (nem j P felt´etlen¨ ul pozit´ıv) egy¨ utthat´ok, amelyekre teljes¨ ul a βs as = 1 rel´ aci´o. Legyen A = s=1
a1 + · · · + aj , ´es ´ırjunk minden k pozit´ıv eg´esz sz´amot k = tA + p, 0 ≤ p < A, alakban. j P βs as azonoss´ag megadja minden el´eg nagy sz´am Ekkor a k = t(a1 + · · · + aj ) + p k´ıv´ant alak´ u el˝ o´all´ıt´ as´at.
s=1
A fentiekb˝ol k¨ ovetkezik, hogy l´etezik olyan k0 k¨ usz¨ obindex, hogy wk = η, ha k ≤ −k0 . Viszont ha wl = η minden l ≤ k sz´amra valamely k sz´amra, akkor az (A1) ´es (A6) formula (a k + 1 indexre alkalmazva) azt adja, hogy wk+1 = η. Ezen ´eszrev´etel alapj´ an teljes indukci´ oval kapjuk, hogy wk = η minden k indexre. A lemm´at bebizony´ıtottuk.
27
