Sztochasztikus folyamatok 3. feladatsor

A spektrális rés / Megszámlálható Markov láncok

1 A spektrális rés

3.1 (a) Lássa be, hogy egy véges állapotterű, irreducibilis Markov átmenetmátrix spektrális rése akkor és csak akkor 1, ha van olyan 0 < m < +∞, hogy tetszőleges μ_{0} kezdeti eloszlásból indítva az X_{1}, X_{2}, … Markov-láncot, ha n_{2} − n_{1} ≥ m, akkor X_{n_{1}} és X_{n_{2}} független valószínűségi változók.

(b) Mathematica segítségével számítsa ki a 0. feladatsor 3. feladatában definiált Markov-lánc átmenetmátrixának Jordan-féle normálalakját.

3.2 Tekintsük az X_{1}, X_{2}, … véges állapotterű, irreducibilis Markov láncot, melynek átmenetmátrixa P és spektrális rése r. Tegyük fel, hogy mátrix sajátértékei mind különbözőek.

(a) Ha a Markov lánc stacionárius, mi a megfordított Markov lánc spektrális rése?

(b) Mi annak a ”lusta” Markov láncnak a spektrális rése, aminek a bolyongója minden lépésben feldob egy szabályos érmét, és ha fej, akkor a P átmenetmátrix szerint lép egyet, ha pedig írás, akkor helyben marad?

(c) Mi az X_{2}, X_{4}, X_{6}, … ”ritkított” Markov-lánc spektrális rése?

(d) Mi annak a ritkított Markov láncnak a spektrális rése, amit úgy kapunk, hogy minden n-re X_{n}-et mindentől függetlenül p valószínűséggel töröljük?

(e) Legyen Y_{1}, Y_{2}, … egy másik, az előbbitől teljesen független Markov lánc, aminek átmenetmátrixa Q és spektrális rése r_{2}. Mi a Z_{n} = (X_{n}, Y_{n}) Markov lánc spektrális rése? Segítség: az új átmenetmátrix sajátvektorai mind összeeszkábálhatóak a régi mátrixok sajátvektoraiból.

3.3 Legyen φ : S → Ŝ az X_{1}, X_{2}, ⋯ ∈ S reverzibilis Markov lánc kontrakciója. Lássa be, hogy a φ(X_{1}), φ(X_{2}), … Markov lánc spektrális rése nagyobb vagy egyenlő az eredeti Markov lánc spektrális résénél.

3.4 Határozza meg a 2. feladatsor 10. feladatában definiált Markov lánc összes 1 abszolútértékű sajátértékéhez tartozó jobb-és baloldali sajátvektorát.

3.5 Lássa be a 2. feladatsor 8. feladatának felhasználásaával, hogy ha P egy szigorúan szubsztochasztikus irreducibilis átmenetmátrix, azaz ha P elemei nemnegatívak, minden sorösszeg kisebb vagy egyenlő 1-nél, van olyan sor, aminek az összege kisebb, mint 1, és a G := {(x, y) : P_{x,y} > 0} irányított gráf erősen összefüggő, akkor I − P invertálható mátrix.

3.6 Vegyük azt a sztochasztikus mátrixot az S = {1, 2} állapottéren, amire P_{1,1} = \frac{1}{2}, P_{2,2} = \frac{3}{4}. P^{100} elemei körülbelül hány tizedesjegyben térnek el lim_{n→∞} P^{n} elemeitől? P^{100} =?

3.7 Tekintsük azt az X_{1}, X_{2}, … Markov-láncot, aminek az állapottere S = {1, 2, 3} és átmenet-mátrixa

P = [ \begin{matrix}0.5 & 0.5 & 0 \\ 0.5 & 0.25 & 0.25 \\ 0 & 0 & 1 \end{matrix} ] .

Tegyük fel, hogy μ_{0}(3) = 0 teljesül a kezdeti eloszlásra.

(a) Körülbelül hány nullával kezdődik P(X_{n} ≠ 3), ha 1 ≪ n?

(b) Lássa be, hogy az az Y_{1}^{n}, Y_{2}^{n}, …, Y_{n}^{n} sztochasztikus folyamat is (nem feltétlenül homogén) Markov lánc, aminek állapottere S = {1, 2} és aminek eloszlását a következő módon definiáljuk:

P(Y_{1}^{n} = i_{1}, …, Y_{n}^{n} = i_{n}) := P(X_{i} = i_{1}, …, X_{n} = i_{n}|X_{n} ≠ 3)

Mik a P(Y_{k+1}^{n} = j|Y_{k}^{n} = i) átmenetvalószínűség-mátrixok?

(c) Fix k esetén számítsa ki a

P̂_{i,j} = lim_{n→∞} P(X_{k+1} = j|X_{k} = i, X_{n} ≠ 3)

átmenetvalószínűség-mátrixot.

3.8 A diszkrét Fourier-transzformáció a konvolúciót szorzásba viszi Tekintsük az egyszerű, szimmetrikus bolyongást a modulo L maradékosztályokon, ahol L páratlan szám. Jelölje P a Markov lánc átmenetmátrixát. Ekkor

P_{x,y} = \frac{1}{2}11[ x ≡ y + 1 mod L ] + \frac{1}{2}11 [x ≡ y − 1 mod L ]

Legyen U az az L × L-es mátrix, amire U_{x,y} = exp(2πi\frac{xy}{L}), 0 ≤ x, y ≤ L − 1. Ellenőrízze, hogy U^{−1} = \frac{1}{L}U^{∗}, ahol U^{∗} az U konjugált transzponáltja. Mutassa meg, hogy U^{−1}P U diagonális mátrix. Lássa be a L’Hospital-szabály segítségével, hogy P spektrális rése körülbelül \frac{1}{2} \frac{π^{2}}{L^{2}} , ha 1 ≪ L.

2 Megszámlálható Markov láncok

3.9 Tekintsük a következő sorbanállási problémát: X_{n} a sorbanálló vásárlók száma n-kor. Minden (n, n+1], n ∈ ℕ időintervallumban p ∈ (0, 1) valószínűséggel egy új vásárló érkezik és a sor végére áll. Ettől függetlenül, ugyanebben az időintervallumban a sor elején álló vásárlót q ∈ (0, 1) valószínűséggel kiszolgálják és ő elhagyja a sort. Legfeljebb egy új vásárló érkezhet és legfeljebb egy vásárlót szolgálnak ki egységnyi időintervallumonként. A különböző időintervallumokban történő események egymástól függetlenek.

(a) Markov lánc-e az X_{n} folyamat? Ha igen, írjuk le az állapotterét és átmenetmátrixát és állapítsuk meg, hogy irreducibilis-e, illetve, aperiodikus-e.

(b) Mely (p, q) paraméter értékekre lesz az X_{n} Markov lánc pozitív rekurrens, null rekurrens illetve tranziens?

(c) A pozitív rekurrens esetben határozzuk meg a Markov lánc π stacionárius (invariáns) eloszlását. Mennyi a sor átlagos hossza a stacionárius állapotban? Segítség: Detailed balance...

(d) A tranziens esetben határozzuk meg annak a valószínűségét, hogy kezdetben j hosszú sorral indulva, valaha is kiürül a sor.

3.10 Tekintsük a következő Markov láncot az S = {0, 1, 2, … } állapottéren. Adottak a p_{1}, p_{2}, … pozitív számok melyek összege 1: ∑_{j=1}^{∞} p_{j} = 1.

Ha a Markov lánc a 0 állapotba ér, a (p_{j})_{j=1}^{∞} eloszlás szerint választja ki következő állapotát. Ha valamely j > 0 állapotban van, akkor determinisztikus módon a j − 1 állapotba lép.

(a) Írjuk fel a Markov lánc átmenetmátrixát. Irreducibilis és aperiodikus-e a Markov lánc?

(b) A Markov lánc nyilvánvaló módon rekurrens. (Miért?) Milyen feltételnek kell a (p_{j})_{j=1}^{∞} eloszlásnak eleget tennie ahhoz, hogy a Markov lánc pozitív rekurrens legyen? Útmutatás: Számoljuk ki a 0-ba való első visszatérés idejének várható értékét.

3.11 Tekintsük az X_{n} Markov láncot az S = {0, 1, 2, … } állapottéren, melynek átmenet valószínűségei:

\begin{matrix}P(X_{n+1} = j + 2|X_{n} = j) = p, \\ P(X_{n+1} = max(j − 1, 0)|X_{n} = j) = 1 − p, \end{matrix} j ∈ S.

Mely p értékekre lesz a Markov lánc tranziens, null rekurrens, illetve pozitív rekurrens? Segítség: generátorfüggvény-módszer!

3.12 Tekintsünk egy elágazó folyamatot, melynél egy szülő gyermekei számának eloszlása (p_{i})_{i=0}^{∞}. Ebből irreducibilis Markov láncot csinálunk, úgy, hogy ha a populáció kihal, a következő lépésben egy új egyedet ültetünk be kívülről. Mely (p_{i})_{i=0}^{∞} eloszlásokra lesz az így értelmezett Markov lánc pozitív rekurrens, null rekurrens, illetve tranziens?

3.13 Legyen X_{n} Markov lánc az S = {0, 1, 2, … } állapottéren, melynek átmenet mátrixa az alább megadottak egyike. Állapítsuk meg, mely esetekben lesz a Markov lánc pozitív rekurrens, null rekurrens, illetve tranziens. A pozitív rekurrens esetekben számoljuk ki a stacionárius (invariáns) eloszlást.

(a) P_{j,j+1} = (j + 1)/(j + 2), P_{j,0} = 1/(j + 2).

(b) P_{j,j+1} = 1/(j + 2), P_{j,0} = (j + 1)/(j + 2).

(c) P_{j,j+1} = (j^{2} + 1)/(j^{2} + 2), P_{j,0} = 1/(j^{2} + 2).

3.14 Legyenek X_{1}, X_{2}, X_{3}, … független és azonos eloszlású, egész értékű valószínűségi változók, melyeknek van várható értékük és E(X_{i}) = 0. Legyen S_{0} = 0 és

S_{n} = X_{1} + X_{2} + ⋯ + X_{n}.

(Azaz: S_{n} bolyongás ℤ-n, melynek egymásutáni lépései X_{1}, X_{2}, . . ..) Legyen továbbá

G_{n}(x) := E( ∑_{j=0}^{n} 11_{{S_{j}=x}}),

a [0, n] időintervallumban az x rácsponton töltött részidő várható értéke. (E függvényt a bolyongás Green-függvényének nevezzük.)

(a) Bizonyítsuk be, hogy minden n ∈ ℕ és x ∈ ℤ esetén

G_{n}(0) ≥ G_{n}(x).

Útmutatás: Tekintsük az x rácspont első elérésének idejét.

(b) Emlékezzünk a Nagy Számok Gyenge Törvényére: bármely ε > 0 esetén

lim_{n→∞} P(|S_{n}| < εn) = 1.

Ennek segítségével bizonyítsuk be, hogy rögzített ε > 0 mellett

lim_{n→∞} \frac{1}{n} ∑_{|x|<εn} G_{n}(x) = 1.

(c) Az (a) és (b) pontok eredményének felhasználásával bizonyítsuk be, hogy

lim_{n→∞} G_{n}(0) = ∞.

(d) A fentiek alapján lássuk be, hogy az S_{n} Markov lánc rekurrens.

(e) Alkalmazható-e a fenti okoskodás magasabb dimenziós bolyongásra?

3.15 Legyen (p_{k})_{k∈ℤ} valószínűségi eloszlás ℤ-n, melyről feltesszük, hogy

p_{1} > 0, p_{k} = 0, ha k > 1

és várható értéke negatív:

∑_{k=−∞}^{∞} kp_{k} =: μ < 0.

Értelmezzük az X_{n} Markov láncot az S = {0, 1, 2, 3 … } állapottéren, melynek átmenetmátrixa:

P_{i,j} = \{ \begin{matrix}p_{j−i} & ha j > 0, \\ ∑_{k≤0} p_{k−i} & ha j = 0. \end{matrix}

Más szóval: X_{n} bolyongás, melynek lépés eloszlása (p_{k})_{k∈ℤ}, de nem léphet a negatív félegyenesre. Feladatunk célja bebizonyítani, hogy az X_{n} bolyongás pozitív rekurrens.

(a) Tegyük fel, hogy π(j), j ∈ S, egy invariáns eloszlás. Bizonyítsuk be, hogy minden i > 0-ra

π(i) = ∑_{j=i−1}^{∞} π(j)p_{i−j}.

(b) Legyen q_{k} = p_{1−k}, k = 0, 1, 2, . . .. Bizonyítsuk be, hogy az

s = ∑_{k=0}^{∞} s^{k}q_{k}.

egyenletnek létezik egy és csakis egy s^{∗} ∈ (0, 1) megoldása. Útmutatás: (q_{k})_{k=0}^{∞} olyan valószínűségi eloszlás ℕ-en, melynek várható értéke 1-nél nagyobb. A fenti egyenlet jobb oldalán ennek az eloszlásnak a generátorfüggvénye szerepel.

(c) A (b) pont beli s^{∗} érték felhasználásával határozzuk meg az X_{n} Markov lánc stacionárius (invariáns) eloszlását.

3.16 Egy Markov lánc állapotai a nem-negatív egész számok: S = {0, 1, 2, … }. Átmenet valószínűség mátrixa:

P_{k,l} = e^{−λ} ∑_{ν=0}^{k} \binom{k}{ν}p^{ν}q^{k−ν} \frac{λ^{l−ν}}{(l − ν)!}.

(p, q > 0, p + q = 1.) Bizonyítandó, hogy

P_{k,l}^{(n)} → e^{−λ/q} \frac{(λ/q)^{l}}{l!} ,

amint n → ∞.