Seria 2. Łańcuchy Markowa

1. Błądzenie przypadkowe na półprostej X_{n} = [X_{n−1} + W_{n}]_{+}, gdzie W_{i} są niezależnymi zmiennymi losowymi o wartościach ℤ. Oblicz P (x, y), P (x, 0). Pokaż, że jeśli P(W_{n} < 0) > 0 to z dowolnego stanu x ∈ ℤ_{+} dojdziemy z niezerowym p-stwem do 0. Zauważ, że jeśli P(W_{n} < 0) = 0 wówczas nie da się osiągnąć stanu 0 spoza tego stanu. Czy mozna znaleźć zmienną W taką, że przestrzeń stanów składa się z dwóch zbiorów pochłaniających?

2. Rozważmy proces odnowienia, to znaczy niech {Y_{0}, Y_{1}, Y_{2}, ...} będą zmiennymi iid z rozkładu na ℕ, definujemy proces Z_{n} = ∑_{i=0}^{n} Y_{n}. Niech p(n) będzie funkcja p-stwa dla Y_{i}. Definiujemy

r = sup(n : p(n) > 0).

Przez rekurencję wstepującą będziemy nazywać proces

V^{+}(n) := inf(Z_{m} − n : Z_{m} > n), n ⩾ 0.

Pokaż, że zbiór A = {1, 2, ..., r} jest pochlaiający oraz, że łańcuch zredukoway do A jest nieredukowalny.

3. Model kolejek. Definiujemy model GI/G/1 w którym:

(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 chwila T′_{n}, czyli N(T′_{n}−). Pokaż, że bez dodatkowych załozeń o H, N_{n} nie musi być łańcuchem Markowa.

4. Pokaż, że jeśli H(−∞, t] = 1 − e^{−μt}, t ⩾ 0, wówczas N_{n} jest łańcuchem Markowa. Oblicz p-stwa przejścia. Taki model nazywa się GI/M/1.

5. W analogiczny sposób definiujemy N_{n}^{∗} liczbę klientów tuż po chwili T′_{n} z wykładniczym rozkladem czasów obsługi. Taki model nazywamy M/G/1. Znajdź p-stwa przejścia w tym modelu.

6. Udwodnij że modele GI/M/1 i M/G/1 są nieredukowalne na ℤ_{+}.

7. Nieograniczone błądzenie przypadkowe na ℤ. Niech d będzie NWD {n : Γ(n) > 0}. Pokaż, że każdy ze zbiorów D_{r} = {md + r : m ∈ ℤ} jest pochłaniający. Pokaż, że jeśli Γ(−∞, 0) > 0 i Γ(0, ∞) > 0 to łańcuch jest nieredukowalny po obcięciu do D_{r}.

8. Znajdź funkcję przejścia dla błądzenia losowego na półprostej. Pokaż, że błądzenie na półprostej jest φ-nierdukowalne dla φ(0, ∞) = 0, φ({0}) = 1 wtedy i tylko wtedy, gdy

P(W < 0) = Γ(−∞, 0) > 0.

Nadto w tym przypadku jeśli C jest zwarte, to C ↦ {0}.

9. Nieograniczone błądzenie przypadkowe. Niech rozkład Γ procesu W ma rozklad absolutnie ciągły względem miary Lebesgue’a, która jest dodatni i odzielona od zera w środku układu współrzędnych.