Sztochasztikus folyamatok 3 és feledik feladatsor Markov lánc NSZT, CHT

3b.1 Legyen P irreducibilis átmenetmátrix az S véges állapottér felett és legyen π = πP a hozzá tartozó stacionárius eloszlás. Ha f, g : S → ℝ, akkor definiáljuk a stacionárius mértékre vonatkozó belső szorzatukat a következő módon:

⟨f, g⟩_{π} := ∑_{x∈S} f(x)g(x)π(x)

Ekkor \sqrt{⟨f, f⟩_{π}} = ∥f∥_{2} az (S, π) mértéktér szerinti L_{2}-normája f-nek.

(a) Lássa be, hogy D_{π}^{2}(f) = ⟨f, f⟩_{π} − ⟨11, f⟩_{π}^{2}.

(b) Mi a P mátrix ⟨ , ⟩_{π}-ra vonatkozó adjungáltjának valószínűségszámítási jelentése? Milyen Markov-láncoknak lesz önadjungált a P -je?

(c) Mi a valószínűségszámítási jelentése a ⟨11, f⟩_{π} = ⟨11, P f⟩_{π} azonosságnak?

(d) Legyen X_{1}, X_{2} a stacionárius állapotból indított Markov lánc első két lépése. Lássa be, hogy ha f : S → ℝ, akkor

\frac{1}{2}D^{2}(f(X_{2}) − f(X_{1})) = ⟨f, (I − P)f⟩_{π}

3b.2 Lássa be, hogy reverzibilis Markov láncok spektrális rését a következő szélsőérték-probléma megoldásával is megkaphatjuk:

r = min_{f} \{ \frac{\frac{1}{2}D^{2}(f(X_{2}) − f(X_{1}))}{D^{2}(f(X_{1}))}\}

ahol f a nemkonstans függvényeken fut végig. Segítség: E_{π}(f) = 0 és D_{π}^{2}(f) = 1 feltehető, Lagrange-féle multiplikátor-módszer.

3b.3 (a) Legyen X nemnegatív egész értékű valószínűségi változó, melynek véges a második momentuma, azaz E(X^{2}) < ∞. Fejezzük ki az S := ∑_{k=1}^{∞} kP(X ≥ k) mennyiséget E(X) és D^{2}(X) segítségével.

(b) A 2.8-as feladat jelöléseivel adjon felső becslést E(T^{2})-re!

3b.4 Nagy számok törvénye Markov láncokra Legyen X_{0}, X_{1}, X_{2}, … véges állapotterű, irreducibilis, aperiodikus Markov lánc, jelölje P az átmenetmátrixát, μ_{0} a kezdeti eloszlását és π a stacionárius eloszlását. Legyen i ∈ S az állapottér tetszőleges eleme. Jelölje T_{0} az i első elérésének időpontját, T_{k} pedig a k-adik visszatérés időpontját i-be. Legyen f : S → ℝ. Legyen Y_{0} = ∑_{n=0}^{T_{0}−1} f(X_{n}) és k ≥ 1-re Y_{k} = ∑_{n=T_{k−1}}^{T_{k}−1} f(X_{n}).

(a) Lássa be, hogy E(Y_{1}) = E(T_{1} − T_{0}) · ⟨11, f⟩_{π}.

(b) Jelölje ν(N) a bolyongó i-ben tett látogatásainak számát az N időpont előtt. Lássa be a Kolmogorov-féle NSZT és a felújításelmélet alaptrükkje segítségével, hogy \frac{ν(N)}{N} majdnem biztosan π(i)-hez konvergál.

(c) Bizonyítsa be, hogy majdnem biztosan

lim_{N→∞} \frac{∑_{n=0}^{N−1} f(X_{n})}{N} = ⟨11, f⟩_{π}

(d) Általánosítsa az állítást periodikus, irreducibilis Markov-láncokra.

3b.5 Centrális határeloszlás-tétel Markov láncokra Az előző feladat feltevéseivel és jelöléseivel dolgozunk tovább. Tegyük fel továbbá, hogy a Markov lánc aperiodikus, és hogy ⟨11, f⟩_{π} = 0. Bizonyítsa be, hogy \frac{∑_{n=0}^{N−1} f(X_{n})}{\sqrt{N}} eloszlásban konvergál egy N(0, σ^{2}) normális eloszlású valószínűségi változóhoz. Segítség: a becsléseknél jól jön, hogy f-nek a szupremum-normája véges és hogy a visszatérési idő szórásnégyzete véges.

3b.6 A Green-Kubo formula Az előző feladat jelöléseit és feltevéseit használjuk. Tegyük fel továbbá az egyszerűség kedvéért, hogy μ_{0} = π.

(a) Fejezze ki Cov(f(X_{n}), f(X_{m})) értékét ⟨ , ⟩_{π} és P segítségével.

(b) Lássa be, hogy az I − P operátor megszorítása az E_{π}(f) = 0 függvényekből álló P -invariáns altérre invertálható.

(c) Lássa be, hogy ⟨11, f⟩_{π} = 0 esetén

σ^{2} = lim_{N→∞} D^{2}(\frac{∑_{n=0}^{N−1} f(X_{n})}{\sqrt{N}}) = 2⟨f, (I − P)^{−1}f⟩_{π} − ⟨f, f⟩_{π}

(d) Mit ad a formula, ha P_{x,y} = π(y)? Mi ennek a valószínűségszámítási jelentése?

(e) Tegyük fel, hogy a Markov lánc reverzibilis. Lássa be lineáris algebrai eszközökkel is, hogy σ^{2} ≥ 0.

(f) Tegyük fel, hogy a Markov lánc reverzibilis. Adjon felső becslést σ^{2} értékére a spektrális rés segítségével. Éles ez a felső becslés?

3b.7 Tekintsünk egy aszimmetrikus bolyongást egy fán, azaz: G egy irányítatlan, összefüggő, körmentes gráf, a Markov lánc állapottere S = V (G), és P_{x,y} > 0 akkor és csak akkor, ha {x, y} ∈ E(G) vagy x = y.

(a) A Markov-lánc NSZT és a 2.2 feladat segítségével adjon magyarázatot arra, hogy miért reverzibilis ez a Markov lánc.

(b) Adja meg a stacionárius eloszlását.

3b.8 Legyen N(t) annak a száma, ahányszor Kovácsék kidobták az újságos kupacukat az első t nap alatt. Mi az az m és σ, amire \frac{N(t)−mt}{σ\sqrt{t}} eloszlása N(0, 1)-hez konvergál? A választ számolja ki kétféleképpen is: a felújítási folyamatokra vonatkozó CHT, valamint Markov lánc CHT és a Green-Kubo formula segítségével. Mindkét számoláshoz használhat szoftvert.

3b.9 A közegellenállásról Tekintsük a következő bolyongást periodikus közegben: a bolyongás állapottere ℤ, az egész számok halmaza. Csak első szomszédba tud lépni a bolyongó (vagy helyben marad).

P(X_{n+1} = x − 1 | X_{n} = x) = p(x)
P(X_{n+1} = x + 1 | X_{n} = x) = q(x)
P(X_{n+1} = x | X_{n} = x) = r(x)

Ahol p(x) + q(x) + r(x) = 1, továbbá a közeg periódusa M, azaz p(x + M) = p(x), q(x + M) = q(x), r(x + M) = r(x). A bolyongó X_{0} = 0-ból indul.

(a) Jelölje P_{x,∞} annak a valószínűségét, hogy a bolyongó valaha eléri a −x pontot. Számítsa ki ψ := lim_{x→∞}(P_{x,∞})^{\frac{1}{n}} értékét. log(ψ)-t nevezzük a közeg aszimptotikus (jobbra való) lejtésének.

(b) Legyen Y_{n} := X_{n} mod M aszimmetrikus bolyongás a maradékosztályokon. Lássa be a Markov lánc NSZT segítségével, hogy van olyan w ∈ ℝ, hogy minden x maradékosztályra

π(x − 1) · q(x − 1) = π(x) · p(x) + w

ahol π az Y_{n} Markov lánc stacionárius eloszlása (tehát Y_{n} ”majdnem” reverzibilis).

(c) Legyen X_{0} kezdeti eloszlása olyan, hogy Y_{0} stacionárius eloszlású legyen. Fejezze ki E(X_{n+1} − X_{n}) értékét w segítségével.

(d) Számolja ki w értékét.

(e) Számolja ki a bolyongó aszimptoikus sebességét, azaz lim_{n→∞} \frac{X_{n}}{n} értékét.

(f) Lássa be, hogy ψ < 1 akkor és csak akkor, ha w > 0.

(g) Lássa be, hogy az ugyanolyan aszimptotikus lejtésű közegek közül a homogén közegben mozgó részecske aszimptotikus sebessége a legnagyobb.