Sztochasztikus folyamatok 8. feladatsor Martingálok II.

8.1 Lássa be, hogy ha T_{1} és T_{2} megállási idők az (F_{n})_{n=1}^{∞} filtrációra nézve, akkor T_{1} ∧ T_{2} is megállási idő.

8.2 Legyenek X_{i}, i = 1, 2, … független és azonos eloszlású valószínűségi változók, melyeknek közös

eloszlása

P(X_{i} = 1) = p, P(X_{i} = −1) = q = 1 − p.

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

(a) Mutassuk meg, hogy Z_{n} := (q/p)^{S_{n}} martingál, melynek várható értéke 1.

(b) a ∈ ℕ esetén jelölje T_{a} = min{n : S_{n} = a} az a elérési idejét. A martingál-megállítási tétel segítségével számolja ki a P(T_{a} < T_{b}) valószínűséget, ahol a < 0, b > 0.

(c) Mely C > 0 és λ > 0 választások mellett lesz

Z_{n} := C^{n}λ^{S_{n}}

martingál? Melyik korábbi feladat átfogalmazása ez?

8.3 Legyenek X_{1}, X_{2}, … független, azonos eloszlású, véges μ várhatóértékű valószínűségi változók és ν tőlük független, véges várható értékű nemnegatív egész értékű valószínűségi változó. Legyen F_{n} = σ(X_{1}, X_{2}, …, X_{n}, ν · 11[ν ≤ n]). Lássa be, hogy M_{n} = S_{n} − nμ martingál és ν megállási idő az F_{n} filtrációra nézve, és hogy E(∑_{n=1}^{ν} X_{n}) = E(ν)μ.

8.4 Legyenek X_{1}, X_{2}, … független, azonos eloszlású, véges μ várhatóértékű, pozitív valószínűségi változók, T (n) = ∑_{k=1}^{n} X_{k} az n-edik felújítási időpont és N(t) = max{n : T (n) ≤ t} a (0, t] intervallumba eső felújítások száma. F_{n} := σ(X_{1}, X_{2}, …, X_{n}) = σ(T (1), T (2), …, T (n)).

(a) Mutassa meg, hogy tetszőleges t-re N(t) + 1 megállási idő, és hogy

E(T (N(t) + 1)) = E(N(t))μ + μ

Segítség: Igaz, hogy semelyik órán tanult martingál-megállítási tétel nem alkalmazható, de a dominált konvergencia-tétel feltételeit kézzel le lehet ellenőrizni...

(b) Igaz-e, hogy E(T (N(t))) = E(N(t))μ?

8.5 Tekintsük az irreducibilis, szubsztochasztikus P mátrixot, és a hozzá tartozó Markov láncot (amit úgy kapunk, hogy hozzáveszünk egy elnyelő állapotot, és a maradék valószínűségekkel mindenhonnan az elnyelő állapotba lépünk). A Perron-Frobenius-tétel miatt P legnagyobb abszolútértékű λ sajátértéke 0 < λ < 1, a sajátérték egyszeres, a hozzá tartozó jobb oldali v sajátvektor csupa pozitív elemből áll, és a többi sajátártékhez tartozó sajátvektor nem ilyen. Lássa be, hogy annak a valószínűsége, hogy X_{n} még nem az elnyelő állapot, legfeljebb \frac{v(X_{0})}{v_{min}}λ^{n}, ahol v_{min} a v vektor legkisebb elemét jelöli.

8.6 A Wright-Fisher modell Van m golyó egy dobozban, az n-edik lépésben X_{n} darab piros és m − X_{n} darab kék. Az n + 1edik golyó-leosztást úgy kapjuk, hogy m-szer húzunk visszatevéssel az n-edik dobozból, és olyan színű golyókat rakunk az új dobozba, amilyeneket kihúztunk.

(a) A Markov láncnak van két elnyelő állapota. Mekkora valószínűséggel melyikben nyelődik el?

(b) Lássa be, hogy \frac{X_{n}(m−X_{n})}{(1− \frac{1}{m})^{n}} martingál. A 5. feladat segítségével mondjon egy olyan n-et, hogy a fele piros-fele kék állapotból indított Markov lánc az n-edik lépésben már legalább \frac{1}{2} valószínűséggel valamelyik egyszínű állapotban lesz.

8.7 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} = z és minden y ∈ S-re legyen

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

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

∑_{x∈S} r(x)P_{x,y} = r(y),

azaz az r(x) számokból képezett sorvektor az 1 sajátértékhez tartozó baloldali sajátvektora a Markov lánc P átmenetmátrixának. Segítség: ∑_{i=1}^{n} (11_{{X_{i}=y}} − E(11_{{X_{i}=y}}|F_{i−1})) korlátos növekményű martingál és T véges várható értékű megállási idő a természetes filtrációra nézve.

8.8 Legyen S diszkrét (véges vagy megszámlálható) állapottér és felette a (P_{x,y})_{x,y∈S} sztochasztikus mátrix. Az f : S → ℝ függvényről azt mondjuk, hogy (a P átmenet mátrix szerint) szuperharmonikus az x ∈ S pontban, ha

∑_{y∈S} P_{x,y}f(y) ≤ f(x).

Rögzítsünk egy z ∈ S állapotot. Legyen A_{z} azon f : S → ℝ függvények halmaza, melyekre

(i) f(z) = 1, (ii) minden y ∈ S-re 0 ≤ f(y) ≤ 1, (iii) f szuperharmonikus minden x ≠ z pontban.

(a) Legyen X_{n} Markov lánc az S-en, melynek átmenetmátrixa P, de tegyük a z állapotot elnyelővé. Lássa be, hogy f ∈ A_{z} esetén f(X_{n}) szupermartingál.

(b) Értelmezzük a g_{z} : S → ℝ függvényt a következőképpen:

g_{z}(x) = inf_{f∈A_{z}} f(x).

Mutassuk meg, hogy g_{z} ∈ A_{z}.

(c) Mutassuk meg, hogy bármely x ≠ z pontban

∑_{y∈S} P_{x,y}g_{z}(y) = g_{z}(x),

azaz a g_{z} függvény harmonikus az S \ {z} halmazon. Útmutatás: Feltéve, hogy ∑_{y∈S} P_{x,y}g_{z}(y) < g_{z}(x) valamely x ≠ z pontban, mutassuk meg, hogy g_{z} csökkenthető lenne egy picivel az x pontban, úgy, hogy szuperharmonikus tulajdonsága megmaradna minden y ≠ z pontban.

(d) Mutassuk meg, hogy ha g_{z}(x) < 1 valamely x ≠ z pontban, akkor

inf_{y∈S} g_{z}(y) = 0.

Útmutatás: Feltéve, hogy inf_{y∈S} g_{z}(y) =: ε > 0 tekintsük a h_{z}(x) = (g_{z}(x) − ε)/(1 − ε) függvényt.

(e) Legyen ĝ_{z}(x), x ∈ S, annak a valószínűsége, hogy az x állapotból indított lánc valaha is eléri a z elnyelő állapotot, azaz ĝ_{z}(x) = P_{x}(T_{z} < +∞) . Bizonyítandó, hogy ĝ_{z}(x) harmonikus az S \ {z} halmazon, és hogy ĝ_{z} ∈ A_{z}.

(f) Legyen M_{n} = g_{z}(X_{n}). A martingál konvergenciatétel és a dominált konvergenciatétel segítségével lássa be, hogy g_{z}(x) ≥ ĝ_{z}(x).

(g) A fentiek segítségével lássuk be a következő tételt:

Tétel. Legyen egy S diszkrét állapotterű irreducibilis Markov lánc átmenet mátrixa P. Ha létezik egy z ∈ S állapot és egy f : S → ℝ függvény, melyre igaz, hogy

(i) ∀y ∈ S : 0 ≤ f(y) ≤ 1 és f(z) = 1, (ii) f szuperharmonikus az S \ {z} halmazon, (iii) valamely y ≠ z-re f(y) < 1. Ekkor a Markov lánc tranziens.

8.9 Egy szerencsejátékos minden fogadási menetben egyenlő valószínűséggel nyer vagy veszít 1 petákot. Azzal a szilárd elhatározással kezd el játszani, hogy amikor n petáknyi nyereséget vagy m petáknyi veszteséget ér el, abbahagyja a játékot.

(a) Számoljuk ki annak a valószínűségét, hogy nyereséggel távozik.

(b) Számoljuk ki fogadásainak várható számát.

8.10 A ”most piros” játék szabályai a következőek: a játékvezetőnél van egy jól megkevert franciakártya-pakli, aminek a lapjait egyenként megmutatja a játékosnak, akinek az utólsó lap megmutatása előtt valamikor azt kell mondania, hogy ”most piros”, és ha a következő lap színe tényleg piros, akkor a játékos nyert. Mi a legjobb stratégiája?

8.11 Legyen X_{n} diszkrét idejű születési-halálozási folyamat, melynek átmenet valószínűségei:

P_{i,i+1} = p_{i},  P_{i,i−1} = 1 − p_{i} =: q_{i},  p_{0} = 1.

Értelmezzük a

g : ℕ → ℝ_{+}, g(k) := 1 + ∑_{j=1}^{k−1} ∏_{i=1}^{j} \frac{q_{i}}{p_{i}}

függvényt.

(a) Bizonyítandó, hogy

Z_{n} := g(X_{n})

martingál a természetes filtrációra nézve.

(b) Rögzítsük a 0 < i < n számokat. Számoljuk ki annak a valószínűségét, hogy az i állapotból indított folyamat előbb éri el az n állapotot, mint a 0-t.

8.12 Elcserélt kalapok — turbo változat.

n személy egy kupacba dobja a kalapját és véletlenszerűen kihúznak a kupacból egyet-egyet. Azok, akik a véletlenül éppen a saját kalapjukat húzták, boldogan hazamennek. A maradók újból egy kupacba dobják a náluk lévő kalapokat és újból véletlenszerűen kihúznak egyet-egyet. Akik most véletlenül pont a saját kalapjukat húzzák, hazamennek. Ez folytatódik, mindaddig, amíg mindenki meg nem találja a saját kalapját. Legyen R a menetek száma (pl. R = 1, ha az elsű húzásnál mindenki éppen a saját kalapját húzza). Számoljuk ki E(R)-t.

8.13 Két (korrekt) kockával dobunk és feljegyezzük az számok összegét. Mindaddig dobunk ameddig a 7, 2, 12, 7, 2 eredménysorzat meg nem jelenik. Mennyi a dobások számának várhatú értéke?

8.14 Legyenek X_{1}, …, X_{n} független valószínűségi változók. Legyen φ olyan n változós függvény, hogy tetszőleges x_{1}, …, x_{n}-re és 1 ≤ k ≤ n-re és x̂_{k}-ra

|φ(x_{1}, …, x_{k}, …, x_{n}) − φ(x_{1}, …, x̂_{k}, …, x_{n})| ≤ 1

Legyen Y := φ(X_{1}, …, X_{n}). Bizonyítandó, hogy tetszőleges a ≥ 0-ra

P (Y − E(Y) ≥ a) ≤ e^{−a^{2}/2n},
P (Y − E(Y) ≤ −a) ≤ e^{−a^{2}/2n}.

8.15 Tekintsük az {1, 2, …, n} halmaz egy véletlen f leképezését önmagára, azaz f(1), …, f(n) függetlenek és egyenletes eloszlásúak {1, 2, …, n}-en. Bizonyítandó, hogy

P (|\frac{|R(f)|}{n} − (1 − (1 − \frac{1}{n})^{n})| ≥ \frac{λ}{\sqrt{n}}) ≤ 2 exp(−\frac{λ^{2}}{2} )

8.16 n hosszú 0 − 1 sorozatok Hamming távolsága egyenlő azon koordináták számával, ahol a két

sorozat különbözik:

ρ(x, y) := ∑_{i=1}^{n} |x_{i} − y_{i}|.

Legyen A tetszőleges részhalmaza az n hosszú 0−1 sorozatok {0, 1}^{n} halmazának és X_{1}, X_{2}, …, X_{n} független, azonos eloszlású valószínűségi változók, melyeknek közös eloszlása P(X_{i} = 0) = 1/2 = P(X_{i} = 1). Legyen

D_{A} := min_{x∈A} ρ(X, x).

Tetszőleges a > 0-ra találjunk felső korlátot a P (|D_{A} − E(D_{A})| ≥ a) valószínűségre.

8.17 Vegyünk egy valószínűségi eloszlást a A, C, T, G (adenin, citozin, timin és guanin) betűk halmazán, és képezzünk két n hosszú i.i.d. sorozatot (DNS-molekulát) ilyen eloszlású betükből. Jelöljük a sorozatokat u_{1}, …, u_{n}-el és v_{1}, …, v_{n}-el. Azt mondjuk, hogy a két sorozatban van m hosszú közös részsorozat, ha van olyan i_{1} ≤ ⋯ ≤ i_{m} és j_{1} ≤ ⋯ ≤ j_{m}, hogy u_{i_{1}} = v_{j_{1}}, …, u_{i_{m}} = v_{j_{m}}. Jelölje M_{n} a leghosszabb közös részsorozat hosszát.

(a) Lássa be, hogy E(M_{n}) sorozatra teljesül a E(M_{n+m}) ≥ E(M_{n}) + E(M_{m}) egyenlőtlenség, és ebből vezesse le, hogy E(\frac{M_{n}}{n}) konvergál sup_{n} E(\frac{M_{n}}{n})-hez.

(b) Bizonyítsa be az alábbi becslést:

P(|M_{n} − E(M_{n})| ≥ λ\sqrt{n}) ≤ 2e^{− \frac{λ^{2}}{8}}

8.18 A 7.13 feladat feltételei mellett (Pólya urna, kezdetben egy piros és egy kék golyó) Mutassuk meg, hogy annak a valószínűsége, hogy a piros golyók aránya valaha is eléri a 3/4-et, kisebb mint 2/3.