Sztochasztikus folyamatok 2. feladatsor

Véges Markov láncok stacionárius eloszlása

2.1 Legyen X_{n} egy diszkrét S állapotterű Markov lánc, melynek átmenet mátrixa (P_{α,β})_{α,β∈S} és kezdeti eloszlása: P(X_{0} = α) = π(α).

(a) Bizonyítandó, hogy az X_{t} Markov lánc, mint sztochasztikus folyamat akkor és csak akkor stacionárius, ha ∑_{α∈S} π(α)P_{α,β} = π(β).

(b) Mutassa meg, hogy stacionárius Markov lánc megfordítottja is stacionárius Markov lánc. Mi a megfordított Markov lánc átmenetmátrixa? Milyen összefüggést kell teljesítenie a Markov lánc stacionárius eloszlásának és átmenetmátrixának ahhoz, hogy a megfordított sztochasztikus folyamat ugyanolyan eloszlású legyen, mint az eredeti? Megj: az ilyen Markov láncokat reverzibilisnek nevezzük.

2.2 Legyen X_{1}, X_{2}, … irreducibilis Markov lánc az S véges állapottéren. Lássa be, hogy Y_{i} := (X_{i}, X_{i+1}) is irreducibilis Markov lánc a G = {(x_{1}, x_{2}) : P_{x_{1},x_{2}} > 0} állapottéren. Mi az így származtatott Markov lánc átmenetmátrixa, stacionárius eloszlása? Igaz-e hogy ha az eredeti Markov lánc reverzibilis, akkor a származtatott Mrkov lánc is reverzibilis?

2.3 Dobókockát azonos valószínűséggel és az előző mozgatásoktól függetlenül, diszkrét időegységenként átfordítjuk az egyik oldaláról a szomszédos négy oldal valamelyikére. Írjuk le a Markov lánc átmenetvalószínűségeinek mátrixát és találjuk meg a stacionárius eloszlását.

2.4 Legyen G olyan irányítatlan véges gráf, ami esetleg tartalmaz hurokéleket és párhuzamos éleket. A bolyongó mindig egyenletesen választ az aktuális csúcsból kiinduló utak közül (tehát a hurokélek duplán számítanak). Mi a bolyongás stacionárius eloszlása?

2.5 Tekintsük azt a bolyongást az S = {1, 2, …, 100} állapottéren. ami a szélekről mindig 1-el beljebb lép, a belső pontokban pedig \frac{1}{3} valószínűséggel balra, \frac{2}{3} valószínűséggel jobbra lép. Mi a stacionárius eloszlás?

2.6 A Boze-Einstein-eloszlás, avagy Markov lánc Monte Carlo Egy bűvésznek van r doboza és n megkülönböztethetetlen nyula. Minden másodpercben mindkét kezével egyszerre belenyúl valamelyik kalapba (a két kézzel egymásól függetlenül, mindkettővel egyenletesen választ kalapot). Ha a bal kézre eső kalapban van nyúl, akkor átteszi a jobb kézre eső kalapba, egyébként pedig nem csinál semmit. Hosszú idő elteltével mekkora lesz egy adott nyúl-konfiguráció valószínűsége?

2.7 Tekintsünk egy Markov láncot a {0, 1, 2, 3, 4, 5} hatelemű állapottéren, melynek átmenet mátrixa

P = [ \begin{matrix}0.5 & 0.5 & 0.0 & 0.0 & 0.0 & 0.0 \\ 0.3 & 0.7 & 0.0 & 0.0 & 0.0 & 0.0 \\ 0.0 & 0.0 & 0.1 & 0.0 & 0.9 & 0.0 \\ 0.25 & 0.25 & 0.0 & 0.0 & 0.25 & 0.25 \\ 0.0 & 0.0 & 0.7 & 0.0 & 0.3 & 0.0 \\ 0.0 & 0.2 & 0.0 & 0.2 & 0.2 & 0.4 \end{matrix} ] .

Azonosítsuk a Markov lánc irreducibilis osztályait. Melyek ezek közül lényegesek és melyek a lényegtelenek? Tegyük fel, hogy a lánc n = 0 időpontban a 0 állapotból indul. Mennyi annak a valószínűsége, n ≫ 1 (nagyon kései) időpontban a 0 állapotban lesz? Válaszoljuk mg ugyanezt a kérdést, ha feltesszük, hogy a Markov lánc n = 0-kor az 5 állapotból indul.

2.8 Legyen X_{n} irreducibilis Markov lánc az {1, 2, …, N} állapottéren. Bizonyítsuk be, hogy léteznek C < ∞ és ρ < 1 konstansok, úgy, hogy bármely i és j állapotokra

P(X_{m} ≠ j, m = 0, 1, …, n|X_{0} = i) ≤ Cρ^{n}.

Mutassuk meg, hogy ebből következik E(T ) < ∞, ahol T a j állapot első elérésének ideje. Útmutatás: Létezik δ > 0, úgy, hogy bármely i és j állapotokra, annak a valószínűsége, hogy i-ből indulva az első N lépés során a Markov lánc eléri a j állapotot, nagyobb, mint δ. Miért?

2.9 Tekintsük azt a Markov-láncot, aminek az állapottere S = {x, y, z} és átmenet-mátrixa

P = [ \begin{matrix}0.2 & 0.4 & 0.4 \\ 0.1 & 0.5 & 0.4 \\ 0.6 & 0.3 & 0.1 \end{matrix} ] .

(a) Határozza meg a stacionárius eloszlást!

(b) Az x-ből indított Markov-lánc várhatóan hányat lép, amíg y-ba ér? Határozza meg a megtett lépések számának eloszlását is!

(c) Az x-ből indított Markov-lánc várhatóan hányszor jár z-ben, mielőtt y-ba érne? Számolja ki kétféleképpen is!

2.10 Tekintsünk egy Markov láncot az {1, 2, 3, 4, 5} ötelemű állapottéren, melynek átmenetmátrixa:

P = [ \begin{matrix}0 & 1/3 & 2/3 & 0 & 0 \\ 0 & 0 & 0 & 1/4 & 3/4 \\ 0 & 0 & 0 & 1/2 & 1/2 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \end{matrix} ] .

(a) Irreducibilis-e a Markov lánc?

(b) Mennyi a periódusa a Markov láncnak?

(c) Számoljuk ki közelítőleg a P_{2,1}^{(1000)}, P_{2,2}^{(1000)} és P_{2,4}^{(1000)} ezer lépéses átmenet valószínűségeket.

(d) Tegyük fel, hogy a Markov lánc az 1 állapotból indul és jelöljük T -vel az 1-be való első visszatérés idejét. Számoljuk ki T eloszlását és várható értékét. Minden további számolás nélkül adjuk meg π(1)-et (heurisztikusan).

(e) Számoljuk ki az invariáns (stacionárius) eloszlást. Ennek ismeretében mondjuk meg (heurisztikusan), hogy mennyi az első visszatérés idejének várható értéke, feltéve, hogy a folyamat a 2 állapotból indult.

2.11 Legyenek X_{1}, X_{2}, … egymásutáni kockadobások számszerű eredményei és S_{n} = X_{1} + X_{2} + ⋯ + X_{n}. Legyen

T_{1} = min{n ≥ 1 : S_{n} osztható 8-cal},
T_{2} = min{n ≥ 1 : S_{n} − 1 osztható 8-cal}.

Számoljuk ki E(T_{1})-et és E(T_{2})-t. Útmutatás: Tekintsük (S_{n} mod 8)-at mint Markov láncot {0, 1, 2, …, 7}- en.

2.12 A felújítási paradoxon Legyenek X_{1}, X_{2}, … független és X-el azonos eloszlású, pozitív egész értékeket felvevő valószínűségi változók (ú.n. felújítási idők), és tegyük fel hogy P(X ≤ M) = 1 valamilyen M ∈ ℕ-re. Legyen 1 ≤ x ≤ Mre p_{x} := P(X = x). T_{0} = 0, T_{k} = ∑_{i=1}^{k} X_{i} (felújítási időpontok). Legyen α_{n} a legutóbbi felújítás óta eltelt idő az n időpontban, β_{n} pedig a következő felújítási időpontig hátralevő idő (és ha n = T_{k} maga egy felújítási időpont, akkor legyen α_{n} = 0, β_{n} = X_{k+1}). Legyen γ_{n} = α_{n} + β_{n} annak a felújítási intervallumnak a hossza, amibe n beleesik.

(a) Mutassa meg, hogy Y_{n} := (α_{n}, β_{n}) Markov láncot alkot. Milyen feltétel kell, hogy teljesüljön X eloszlására, hogy a Markov lánc aperiodikus legyen?

(b) Ha aperiodikus a Markov lánc, milyen lesz 1 ≪ n-re mi γ_{n} eloszlása? A stacionárius állapotban mi P(α = y|γ = x), azaz rögzített γ mellett mi az α feltételes eloszlása?

2.13 Legyen X_{n}, n = 0, 1, 2, … irreducibilis Markov lánc a véges S állapottéren, melynek átmenetmátrixát jelöljük P -vel. Legyen

T := min{n > 0 : X_{n} = X_{0}}

a kezdő állapotba való első visszatérés ideje. Tegyük fel, hogy a kezdeti állapot X_{0} = i és minden j ∈ S-re legyen

r(j) := E( ∑_{n=0}^{T −1} 11_{{X_{n}=j}}),

a kezdő állapotba való első visszatérés előtt a j állapotban töltött idő várható értéke. Vegyük észre, hogy ha X_{0} = i, akkor r(i) = 1.

(a) Bizonyítsuk be, hogy

∑_{j∈S} r(j)P_{j,i} = r(i),

azaz az r(j) számokból képezett sorvektor az 1 sajátértékhez tartozó baloldali sajátvektora a Markov lánc P átmenetmátrixának.

(b) A fenti megjegyzésből vezessük le a

π(i) = (E(T |X_{0} = i))^{−1}

azonosságot, ahol π a Markov lánc stacionárius (invariáns) eloszlása.

2.14 Tekintsük az 1.1 feladatban leírt Markov láncot (Kovácsék ujságos kupaca …).

(a) Hosszú idő után mennyi a kupacban lévő újságok számának várható értéke?

(b) Tegyük fel, hogy kezdetben 0 újság van a kupacban. Várhatóan hány nap múlva lesz újból üres a kupac?

2.15 Legyen X_{n} Markov lánc az {1, 2, 3, 4, 5} ötelemű állapottéren, melynek átmenetmátrixa:

P = [ \begin{matrix}0 & 1/2 & 1/2 & 0 & 0 \\ 0 & 0 & 0 & 1/5 & 4/5 \\ 0 & 0 & 0 & 2/5 & 3/5 \\ 1 & 0 & 0 & 0 & 0 \\ 1/2 & 0 & 0 & 0 & 1/2 \end{matrix} ] .

(a) Irreducibilis-e a Markov lánc? Aperiodikus-e a Markov lánc?

(b) Határozzuk meg a Markov lánc stacionárius (invariáns) eloszlását.

(c) Tegyük fel, hogy X_{0} = 1. Mennyi az 1 állapotba való első visszatérésig megtett lépések számának várható értéke?

(d) Újból tegyük fel, hogy X_{0} = 1 Mennyi a 4 állapot első eléréséig megtett lépések számának várható értéke?

(e) Ugyancsak X_{0} = 1 kezdeti feltétel mellett, mennyi annak a valószínűsége, hogy a folyamat előbb éri el az 5 állapotot, mint a 3-at?

2.16 Határozzuk meg az Ehrenfest urna modell (kutyák és bolhák …) stacionárius eloszlását.

2.17 Az X_{t} diszkrét idejű Markov lánc állapotainak halmaza S = {1, 2, 3}, átmenetvalószínűségeinek mátrixa P, stacionárius eloszlása π. Mutassuk meg, hogy ha P_{1,1} = P_{2,2} = P_{3,3} és π(1) = π(2) = π(3), akkor P_{1,2} = P_{2,3} = P_{3,1} és P_{1,3} = P_{3,2} = P_{2,1}. Általánosítható-e az érvelés?

2.18 (Bernoulli-Laplace keverési modell)

Két urnában szétosztunk N fekete és N fehér golyót úgy, hogy mindegyik urnába N golyó kerüljön. Minden egész értékü t időpillanatban véletlenszerűen kiválasztunk egy-egy golyót mindkét urnából és kicseréljük őket. Jelölje X_{t} az első urnában lévő fehér golyók számát közvetlenül a t-edik golyó-csere után.

(a) Mutassuk meg, hogy X_{t} Markov lánc és írjuk fel az egylépéses átmenetvalószínűségek mátrixát.

(b) Mutassuk meg, hogy az egyetlen stacionárius eloszlás

π(k) = \binom{N}{k}^{2} /\binom{2N}{N}.