Zadania Egzaminacyjne z Łańcuchów Markowa

Uwaga Za każde zadanie można dostać 10 punktów. Rozwiązania można albo przesyłać do mnie bezpośrednio e-mailem albo składac najpóźniej do 5 lutego do 17:00 w mojej skrzynce na MIM UW. Na dyskusję o rowiązaniach i wpisy wyznaczony został piątek 6 lutego 12-14 na MIM

1. Udowodnij Prawo Iterowanego Logarytmu (Hartman-Wintner LIL). Pokaż, że jeśli (X_{i})_{i⩾1} są niezależne o tym samym rozkładzie takie, że EX_{i} = 0, σ^{2} = EX_{i}^{2} < ∞, wtedy

lim sup_{n→∞} \frac{S_{n}}{\sqrt{2nL_{2}n}} = − lim inf_{n→∞} \frac{S_{n}}{\sqrt{2nL_{2}n}} = σ, p.n.,

gdzie S_{n} = X_{1} + ... + X_{n}, L_{2}x = log log max(x, e^{e}). Na odwrót z faktu, że zachodzi LIL wynika, że EX_{i}^{2} < ∞ i EX_{i} = 0. Uwaga Istnieją dwie metody dowodu tego faktu (cf. Ledoux-Talagrand Probability in Banach Spaces). Następujące wskazówki prowadzą do jednej z nich.

(a) Pokaż, że jeśli EX^{2} < ∞, EX = 0, to istnieje ciąg liczb (η_{i}) dodatnich malejących do 0 takich, że

∑_{i} \frac{1}{L_{2}i}P(|X| > η_{i}(\frac{i}{L_{2}i})^{1/2}) < ∞.

(b) Definiujemy zmienne

Y_{i} = X_{i}1_{|X_{i}|⩽η_{i}(i/L_{2}i)^{1/2}} − E(X_{i}1_{|X_{i}|⩽η_{i}(i/L_{2}i)^{1/2}}).

(c) Korzystając z nierówności Levy’ego i nierówności Bernstein’a dla zmiennych ograniczonych tzn. kiedykolwiek są Z_{i} niezależne, to

P( max_{1⩽k⩽n} | ∑_{i=1}^{k} Z_{i}| > t) ⩽ 3P(| ∑_{i=1}^{n} Z_{i}| > t/3),

oraz

P(∑_{i=1}^{n} Z_{i} > t) ⩽ exp(−\frac{t^{2}}{2(v^{2} + M/3)}),

gdzie v^{2} = E ∑_{i=1}^{n} Z_{i}^{2}, |Z_{i}| ⩽ M, udowodnij LIL dla zmiennych Y_{i}, to znaczy pokaż, że

lim sup \frac{S_{n}}{\sqrt{2v_{n}^{2}L_{2}v_{n}^{2}}} = 1,

gdzie v_{n}^{2} = ∑_{i=1}^{n} EY_{i}^{2}.

(d) W dowodzie ograniczenia z dołu przez σ dla lim sup w LIL wykorzystaj odwrotną nierówność Kolmogorowa tzn.

P(∑_{i=1}^{n} Z_{i} > t) ⩾ exp(−\frac{(1 + γ)t^{2}}{2v^{2}} ),

jeśli t ⩾ K(γ)b oraz tM ⩽ ε(γ)v^{2}.

(e) Wywnioskuj, że

lim sup_{n→∞} \frac{∑_{i=1}^{n} Y_{i}}{\sqrt{2nL_{2}n}} = σ, p.n.

(f) Pokaż, że

\frac{1}{\sqrt{2nL_{2}n}}| ∑_{i=1}^{n} X_{i}1_{|X_{i}|>η_{i}(i/L_{2}i)^{1/2}}| ⩽ (\frac{1}{n} ∑_{i=1}^{n} X_{i}^{2})^{1/2}(\frac{1}{2L_{2}n} ∑_{i=1}^{n} 1_{|X_{i}|>η_{i}(i/L_{2}i)^{1/2}})^{1/2}.

Uzasadnij że wyrażenie po prawej zbiega do 0 prawie na pewno (SLN-mocne prawo wielkich liczb, analiza 1).

(g) Podobnie wykaż, że

\frac{1}{\sqrt{2nL_{2}n}}| ∑_{i=1}^{n} EX_{i}1_{|X_{i}|>η_{i}(i/L_{2}i)^{1/2}}|

zbiega do 0 prawie na pewno.

(h) Wywnioskuj LIL dla EX_{i} = 0, EX_{i}^{2} < ∞.

(i) Na odwrót załóżmy, że LIL jest spełnione to znaczy

lim sup \frac{|S_{n}|}{\sqrt{2nL_{2}n}} < ∞, p.n.

Chcemy pokazać, że EX_{i} = 0, EX_{i}^{<}∞. Zauważ, że można ograniczyć rozumowanie do zmiennych symetrycznych.

(j) Z prawa 0 − 1 wydedukuj, że lim sup_{n→∞} \frac{|S_{n}|}{\sqrt{nL_{2}n}} = M p.n. dla pewnego M < ∞.

(k) Uzasadnij, że

2 lim sup_{n→∞} \frac{∑_{i=1}^{n} X_{i}1_{|X_{i}|⩽c}}{\sqrt{2nL_{2}n}} ⩽ 2M, p.n.

(l) Wykorzystując twierdzenie LIL pokaż, że EX^{2}1_{|X⩽c|} ⩽ M^{2} i dokończ dowód.

2. Udowodnij, że jeśli istnieje σ-skończona miara niezmiennicza π dla łańcucha X, to nastepujące warunki są równoważne

(a) dla każdego f, g ∈ L^{1}(π), gdzie ∫ gdπ ≠ 0 mamy

lim_{n→∞} \frac{S_{n}(f)}{S_{n}(g)} = \frac{π(f)}{π(g)}, P_{μ} − p.n.,

gdzie S_{n}(f) = ∑_{i=1}^{n} f(X_{i}), μ-dowolny rozkład początkowy.

(b) Łańcuch X jest Harris powracalny.

3. Niech (X_{n})_{n⩾0} będzie ergodycznym łańcuchem Markowa z rozkładem stacjonarnym π. Niech ∫ f^{2}dπ < ∞ oraz

∑_{n=1}^{∞} ∫ f(x)P^{n}f(x)π(dx)

jest zbieżny. Pokaż, że S_{n}(f)/\sqrt{n} → N (0, σ^{2}) (według rozkładu) Sróbuj uzasadnić, że

σ^{2} = ∫ f^{2}(x)π(dx) + 2 ∫ (∑_{n=1}^{∞} P^{n}f(x)π(dx)),

jeśli założymy, że ∑_{n=1}^{∞} f(·)P^{f}(·) zbiega w L^{1}(π). (Dla uproszczenia można założyć że istnieje atom).

4. Niech X będzie ergodycznym łańcuchem Markowa. Mówimy, ze łańcuch jest ergodyczny stopnia 2 jeśli dla dowolnego A ∈ B_{+}(X) mamy E_{π}τ_{A} < ∞. Udowodnij, że ergodyczność stopnia 2 jest równoważna z tym, że CLT zachodzi dla wszystkich funkcji f ograniczonych takich, że π(f) = 0. To znaczy S_{n}(f)/\sqrt{n} → N (0, σ^{2}). Nadto

σ^{2} = ∫ f^{2}(x)π(dx) + 2 ∫ (∑_{n=1}^{∞} P^{n}f(x)π(dx)),

Można dla uproszczenia założyć, że istnieje atom α.

5. Mówimy, że łańcuch jest jednostajnie ergodyczny jeśli

lim_{n→∞} sup_{x∈X} ∥P^{n}(x, ·) − π∥_{tv} = 0,

gdzie ∥ · ∥_{tv} jest normą całkowitego wahania. Uzasadnij, że dla jednostajnie ergodycznych łańcuchów Markowa cała przestrzeń jest małym zbiorem. Uzasadnij, że istnieje κ > 1 takie, że sup_{x∈X} E_{x}κ^{τ_{C}}, dla dowolnego małego zbioru C i pewnego κ > 1.

6. Załóżmy, że łańcuch X jest jednostajnie ergodyczny. Niech π(f) = 0, π(f^{2}) < ∞, pokaż, że zachodzi CLT, czyli

\frac{S_{n}(f)}{\sqrt{n}} → N (0, σ^{2}),

gdzie

σ^{2} = ∫ f^{2}(x)π(dx) + 2 ∫ (∑_{n=1}^{∞} P^{n}f(x)π(dx)).

Dla uproszczenia można załozyć, że atom istnieje.

7. W modelu GI/G/1:

(a) Klienci przybywają do systemu w niezależnych odtępach czasu T_{1}, T_{2}, T_{3}, ... o tym samym rozkladzie zmiennej T, to znaczy P(T ⩽ t) = G(−∞, t]. Klienci będą pojawiac się w chwilach T′_{0} = T_{0} = 0, T′_{1} = T_{0} + T_{1},T′_{2} = T_{0} + T_{1} + T_{2},...

(b) n-ty Klient wymaga obsługi zajmującej S_{n} czasu, gdzie S_{n} pochodzą z tego samego rozkladu zmiennej S, to znaczy P(S_{n} ⩽ t) = H(−∞, t]. Zatem łączny czas obsługi n-klientów wynosi S′_{i} = S_{0} + S_{1} + ... + S_{i}.

(c) Klienci obsługiwani są przez jeden serwer w kolejności zgłoszeń. Niech N(t) będzie liczbą klientów przebywających w systemi w chwili t. Niech nadto N_{n} będzie liczbą klientów w systemie tuż przed chwilą T′_{n}, czyli N(T′_{n}−).

(d) Zakładamy, że H(−∞, t] = 1 − e^{−μt}, t ⩾ 0, oraz G(−∞, t) = 1 − e^{−λt}, t ⩾ 0.

pokaż, że jeśli λ > μ, to istnieje rozkład stacjonarny. Co się stanie w przypadku kiedy λ ⩽ μ.

8. Dla błądzenia z barierą to znaczy

P (i, i + 1) = p, x ⩾ 0; P(x, x − 1) = 1 − p, x > 0 P (0, 0) = 1 − p,

wypisz wzór na funkcjęgenerującą rzokład P_{x}(τ_{0} = n), to znaczy

f(x, z) = ∑_{n=0}^{∞} P_{x}(τ_{0} = n)z^{n}.

Wykorzystaj postać f(x, z) aby wykazać, że jeśli p < 1/2, to 2\sqrt{p(1 − p)} jest tempem zbieżności do rozkladu stacjonarnego, to znaczy

∑_{n=0}^{∞} ∥P^{n}(x, ·) − π(·)∥_{tv}λ^{n} < ∞,

dla λ < 1/(2\sqrt{p(1 − p)}).

9. Niech W będzie zmienną na ℝ taką, że EW = 0 oraz 0 < EW^{2} < ∞. Pokaż, że wóczas błądzenie losowe na półprostej to znaczy X_{n} = (X_{0} + ∑_{i=1}^{n} W_{i})_{+}, gdzie (W_{i})_{i⩾1} są i.i.d. o rozkładzie W jest powracalne. Co jeśli EW^{2} = ∞?