Példasor a ”Tömegkiszolgálás informatikai rendszerekben” című tárgyhoz

Összeállította: Rácz András

A *-gal megjelölt példák kicsit bonyolultabbak vagy időigényesek.

1. Diszkrét idejű Markov láncok

1. feladat. Tekintsük az {X_{n}} diszkrét Markov láncot az S = {1, 2} állapottéren és az alábbi állapotátmeneti mátrixszal

P = ( \begin{matrix}1 − α & α \\ β & 1 − β \end{matrix} ) .

Ha α, β > 0, add meg az n-edik lépés utáni állapoteloszlást és mutasd meg, hogy létezik határeloszlás!

2. feladat. Legyen i és j egy diszkrét idejű Markov lánc két állapota. Bizonyítsd be, hogy ha i és j egymásból kölcsönösen elérhető, vagyis ∃n ≥ 0, p_{ij}^{(n)} > 0 és ∃m ≥ 0, p_{ji}^{(m)} > 0, akkor pozitív annak a valószínűsége, hogy i-ből elérjük a j-t anélkül, hogy közben visszatérnénk i-be.

3. feladat.* Bizonyítsd be, hogy ha a lánc irreducibilis és visszatérő, akkor annak a valószínűsége, hogy i-ből indulva valaha is elérünk j-be 1-gyel egyenlő!

4. feladat. Milyen a, b számokra lesz a következő átmenetvalószínűség-mátrixszal adott végtelen állapotú Markov lánc stabil?

Π = ( \begin{matrix}1 − a − b & a & b & 0 & 0 & … \\ 1 − a − b & a & b & 0 & 0 & … \\ 0 & 1 − a − b & a & b & 0 & … \\ 0 & 0 & 1 − a − b & a & b & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

Legyen a = 0 és b = 1/4. Mi ekkor a határeloszlás?

5. feladat. Tegyük fel, hogy egy autót 0.5 valószínűséggel mosnak le egy adott percben (ugyanekkora valószínűséggel egyet sem mosnak le). Legyen 0.6 annak a valószínűsége, hogy egy adott percben nem érkezik új autó az autómosóba és 0.4 valószínűséggel egy autó érkezik. Stacionárius eloszlást feltéve mi a valószínűsége annak, hogy nem tudok beállni az autómosóba, ha ott az éppen mosott autóval együtt csak három autó várakozhat.

6. feladat. Tekintsük az X_{n+1} = X_{n}+W_{n+1} mod 4 egyenlet által megadott {X_{n}} Markov láncot, ahol a W_{n} sorozat egymástól és X_{0}-tol független, azonos eloszlású, nemnegatív, egész értékű valószínűségi változókból áll (ciklikus bolyongás). W_{n} milyen eloszlása esetén lesz {X_{n}} stabil és mi lesz {X_{n}} határeloszlása?

7. feladat. Tekintsük az adott átmenet mátrixú láncot.

Π = ( \begin{matrix}0 & 1 & 0 & 0 & 0 \\ 1/2 & 0 & 1/2 & 0 & 0 \\ 0 & 1/2 & 0 & 1/2 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \end{matrix} )

(a) Irreducibilis-e a lánc?

(b) Aperiodikus-e a lánc?

(c) Pozitív visszatérő-e a lánc?

8. feladat. Legyen a Markov lánc átmeneti mátrixa a következő:

Π = ( \begin{matrix}1/2 & 1/2 & 0 \\ 0 & 1/2 & 1/2 \\ 1 & 0 & 0 \end{matrix} )

Tegyük fel, hogy X_{0} eloszlása (0, 1, 0). Mi lesz az X_{3} eloszlása?

9. feladat. Tekintsük a következő játékot. Ha i Ft-ja van a játékosnak (0 < i < N), akkor p valószínűséggel nyer 1 Ft-ot, és 1 − p valószínűséggel veszít 1 Ft-ot (0 < p < 1). Ha 0 Ft-ja van, akkor 1 − p valószínűséggel nem változik a pénze és p valószínűséggel nyer 1 Ft-ot. Ha N Ft-ja van, akkor p valószínűséggel nem változik a vagyona, és 1 − p valószínűséggel veszít 1 Ft-ot. Írd fel az átmeneti mátrixot! A Markov lánc stabil-e? Ha igen, akkor add meg a határeloszlást! Ha nem, akkor indokold meg, hogy miért nincs határeloszlás!

10. feladat. Tekintsük a három állapottal rendelkező Markov láncot, melynek átmeneti mátrixa

Π = ( \begin{matrix}0.1 & 0.3 & 0.6 \\ 0.2 & 0.4 & 0.4 \\ 0.8 & 0.1 & 0.1 \end{matrix} )

Tegyük fel, hogy a lánc kiindulási állapotának eloszlása: P{X_{0} = 1} = 0.7, P{X_{0} = 2} = 0.2, P{X_{0} = 3} = 0.1. Mi lesz X_{1} eloszlása?

11. feladat. Döntsd el, hogy a megadott átmeneti mátrixszal rendelkező Markov lánc

(a) irreducibilis-e?

(b) aperiodikus-e?

Π = ( \begin{matrix}0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & p & q & 0 \\ 0 & 0 & 0 & 0 & 1 \\ q & 0 & 0 & 0 & p \end{matrix} )

ahol p ≠ 0, q ≠ 0, p + q = 1.

12. feladat. Bizonyítsd be, hogy az aperiodikusság öröklődő tulajdonság irreducibilis láncok esetén!

13. feladat. Legyen X_{1}, … X_{n}, … független azonos eloszlású valószínűségi változók sorozata, P{X_{n} = 0} = 1/2, P{X_{n} = 1} = 1/2 eloszlással. Legyen Y_{n} = X_{1} + … + X_{n}. Bizonyítsd be, hogy {Y_{n}} Markov tulajdonságú!

14. feladat. Tekintsük a következő π átmenetmátrix által megadott Markov láncot.

Π = ( \begin{matrix}1/4 & 0 & 1/4 & 0 & 0 & 1/2 \\ 0 & 1/4 & 1/4 & 0 & 1/2 & 0 \\ 0 & 1/2 & 0 & 0 & 1/2 & 0 \\ 1/4 & 0 & 0 & 0 & 1/4 & 1/2 \\ 0 & 1/2 & 0 & 0 & 1/2 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} )

Stabil-e ez a lánc?

15. feladat. Tekintsük a következő átmenetmátrix által megadott Markov láncot.

Π = ( \begin{matrix}0 & 1/2 & 1/2 \\ 1/2 & 0 & 1/2 \\ 1/2 & 0 & 1/2 \end{matrix} )

Pozitív visszatérő-e?

16. feladat. Ha tegnap esett az eső, akkor legyen α annak a valószínűsége, hogy ma is esni fog. Ha tegnap nem esett akkor annak a valószínűsége, hogy ma esni fog legyen β. Számítsd ki az eső valószínűségének határeloszlását!

17. feladat. Tegyük fel, hogy egy áruházban egy bizonyos árucikkre a heti kereslet független azonos eloszlású valószínűségi változó, a következő eloszlással

P{heti kereslet = j} = a_{j} j ≥ 0.

Tegyük fel, hogy az áruház a következő (s, S) rendszer szerint rendel hetente új árut. Ha a hét elején az árukészlet legalább s, akkor nem rendelnek; míg ha ennél kevesebb akkor pontosan annyit rendelnek, hogy S-re föltöltsék az árukészletet. Vagyis, ha a készlet x, akkor a rendelés

\{ \begin{matrix}0, & ha x ≥ s \\ S − x, & ha x < s \end{matrix}

Azok a vásárlói igények, amelyeket nem tudnak azonnal kielégíteni, elvesznek. Jelöljük X_{n}-nel az árukészletet az n-edik hét végén és az n-edik héten a vásárlói igényt γ_{n}-nel. Add meg X_{n} állapotátmeneti mátrixát!

18. feladat. (Random walk) Tekintsük a következő állapotátmeneti mátrixszal adott végtelen állapotú Markov láncot (véletlen bolyongás): p_{i,i−1} = p, p_{i,i+1} = q = 1 − p ∀i ≥ 1, p_{0,0} = p, p_{0,1} = q = 1 − p. Bizonyítsd be az alábbi állításokat:

(a) az állapotok nem visszatérők, ha p ≠ \frac{1}{2} (b) az állapotok nulla-visszatérők, ha p = \frac{1}{2}

19. feladat.* (Doubly stochastic) Egy átmenetvalószínűségi mátrixot duplán sztochasztikusnak nevezünk, ha az oszlopok összege is 1-et ad, vagyis ∑_{i} p_{ij} = 1 ∀j ∈ S.

(a) Bizonyítsd be, hogy egy véges állapotú duplán sztochasztikus állapotátmeneti mátrix esetén minden állapot pozitív visszatérő.

(b) Bizonyítsd, hogy egy végtelen állapotú irreducibilis, duplán sztochasztikus lánc esetén vagy minden állapot nulla visszatérő vagy nem-visszatérő.

20. feladat.* Add meg egy M véges állapotú, irreducibilis, aperiodikus és duplán sztochasztikus Markov lánc határeloszlását!

21. feladat. (Virus mutation) Tegyük fel, hogy egy vírus N különböző mutációban fordulhat elő. Minden egyes generáció vagy megmarad az eredeti mutációban 1 − α valószínűséggelvagy α valószínűséggel egy másik mutációba alakul át. Mi a valószínűsége annak, hogy az n-edik generáció ugyanaz a mutáció mint a kezdeti?

22. feladat. Legyen {X_{n}} Markov lánc Π átmenetvalószínűség mátrixszal. Bizonyítsd be, hogy ha Y_{n} = X_{kn} akkor {Y_{n}} is Markov lánc Π^{k} átmenetvalószínűségmátrixszal.

23. feladat.* Legyen X_{0} valószínűségi változó, amely értékeit egy megszámlálható I halmazból veszi. Legyen Y_{1}, Y_{2}, … független, a [0, 1] intervallumon egyenletes eloszlású valószínűségi változók sorozata. Tekintsük adottnak a következő G függvényt:

G : I × [0, 1] → I,

és definiáljuk X_{n}-et a következő rekurzió szerint:

X_{n+1} = G(X_{n}, Y_{n+1}).

Bizonyítsd be, hogy {X_{n}} Markov lánc és fejezd ki a Π átmenetvalószínűségi mátrixszot G segítségével!

24. feladat. Legyenek Z_{0}, Z_{1}, … független azonos eloszlású valószínűségi változók, úgy hogy P{Z_{i} = 1} = p, P{Z_{i} = 0} = 1 − p. Legyen S_{0} = 0, S_{n} = Z_{1} + … + Z_{n}. Állapítsd meg az alábbiak közül mely esetekben lesz X_{n} Markov lánc. Azokban az esetekben ahol X_{n} Markov lánc, add meg az állapotteret és az átmenetvalószínűségi mátrixot. Egyébként pedig mutass példát arra, hogy P{X_{n+1} = i|X_{n} = j, X_{n−1} = k} nem független k-tól.

(a) X_{n} = Z_{n}

(b) X_{n} = S_{n}

(c) X_{n} = S_{0} + … + S_{n}

(d) X_{n} = (S_{n}, S_{0} + … + S_{n})

25. feladat. Egy bolha egy háromszög csúcspontjain ugrál, úgy hogy minden lehetséges ugrásnak ugyanakkora a valószínűsége. Mi annak a valószínűsége, hogy az n-edik lépés után ugyanott lesz ahonnan indult? Hogyan alakul ez a valószínűség, hogy ha a bolha kétszer akkora valószínűséggel ugrik az óramutató járásával megegyező irányba, mint azzal ellentétesen?

26. feladat.* Egy szerencsejátékos 2 dollárral kezd játszani és a legrövidebb idő alatt el akarja érni, hogy 10 dollárra növelje vagyonát. A játékszabály a következő. Egy szabályos érmét dobunk föl és a játékosunk el kell találja, hogy fej vagy írás lesz-e a dobásból. Ha eltalálta akkor nyer annyi pénzt amekkora a tétje volt (és természetesen a föltett pénzt is visszakapja), ellenkező esetben elveszti a tétjét. A játékos a következő stratégiát választja. Mindaddig amíg 5 vagy annál kevesebb dollárja van az egészet fölteszi, különben pedig csak annyit tesz föl amennyi nyerése eseten épp arra elegendő, hogy pont 10 dollárja legyen. Bizonyítsd be, hogy a szerencsejátékos 1/5 valószínűséggel fogja elérni célját!

27. feladat.* Legyen {X_{n}} végtelen állapotú Markov lánc a {0, 1 …} állapottéren az alábbi állapotátmeneti valószínűségekkel:

p_{01} = 1, p_{i,i+1} + p_{i,i−1} = 1, p_{i,i+1} = (\frac{i + 1}{i})^{2} p_{i,i−1}, i ≥ 1.

Mutasd meg, hogy ha X_{0} = 0, akkor annak a valószínűsége, hogy X_{n} ≥ 1 ∀ n ≥ 1, 6/π^{2}.

28. feladat. Az alábbi állapotátmeneti mátrixszal adott Markov lánc esetén mely állapotok lesznek visszatérők és melyek nem visszatérők?

Π = ( \begin{matrix}1/2 & 0 & 0 & 0 & 1/2 \\ 0 & 1/2 & 0 & 1/2 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 1/4 & 1/4 & 1/4 & 1/4 \\ 1/2 & 0 & 0 & 0 & 1/2 \end{matrix} )

29. feladat.* Tegyük fel, hogy egy kocka csúcsain lépegetünk az alábbi szabály szerint. Egy adott csúcsból a szomszédos 3 csúcs bármelyikébe egyenlő valószínűséggel lépünk, függetlenül a korábbi lépésektől. Legyen i a kezdeti csúcs és o az i-vel szemközti csúcs. Számítsd ki az alábbi mennyiségeket:

(a) az átlagos lépésszám amíg visszatérünk i-be

(b) az o csúcs érintésének átlagos száma amíg először visszatérünk i-be

(c) az átlagos lépésszám amíg először elérünk o-ba

30. feladat. Egy diák 3 könyvet tart a polcán. Minden reggel véletlenszerűen kiválaszt egy könyvet a három közül, függetlenül korábbi választásaitól. Annak a valószínűsége, hogy az i-edik könyvet választja α_{i}, ahol 0 < α_{i} < 1, i = 1, 2, 3. Minden este a könyvet visszateszi a polc elejére. Jelöljük p_{n}-nel annak a valószínűségét, hogy az n-edik reggelen a diák a könyveit az 1,2,3 sorrendben találja. Add meg a p_{n} valószínűséget n → ∞ esetén.

31. feladat. Tegyük fel, hogy van N darab esernyőnk, amelyeknek egy részét otthon egy másik részét a munkahelyünkön tartjuk. Minden reggel elmegyünk a munkahelyünkre. Ha esik az eső, és van otthon ernyőnk, akkor magunkkal viszünk egy ernyőt. Ugyanígy, ha este elindulunk haza, és esik az eső, és van ernyőnk a munkahelyen, akkor magunkkal viszünk egyet. Ha nem esik az eső, akkor nem viszünk magunkkal ernyőt. Hosszú időre tekintve mi a valószínűsége annak, hogy elázunk, feltéve hogy minden indulásunkkor p valószínűséggel esik az eső függetlenül a korábbi időjárástól.

32. feladat.* Egy operaénekesnő minden este koncertet kellene adjon. Minden este a fellépés után 1/2 valószínűséggel visszavonul, és a további estéken mindaddig nem lép fel újra, amíg a managere ki nem engeszteli. Ezt a manager úgy próbálja elérni, hogy minden nap virágot küld az énekesnőnek mindaddig, amíg az vissza nem tér. Ha x ezer dollárért vásárolt már virágot az \sqrt{x} valószínűséggel fogja kiengeszteli az énekesnőt. Ha a manager minden koncerten 750 dollárt keres, mennyi pénzt érdemes virágra költenie?

33. feladat. Bizonyítsd be, hogy minden független növekményű folyamat Markov folyamat!

34. feladat. Legyen Y_{1,n}, Y_{2,n}, …, Y_{n,n} n független a (0, t) intervallumon egyenletes eloszlású valószínűségi változó. Legyen Z_{n} = min(Y_{1,n}, Y_{2,n}, …, Y_{n,n}).

(a) Add meg a P{Z_{n} > x} valószínűséget.

(b) Legyen t egy függvénye n-nek, úgy hogy lim_{n→∞} n/t = λ. Bizonyítsd be, hogy lim_{n→∞} P{Z_{n} > x} = e^{−λx}.

35. feladat.* Tekintsük az alábbi állapotátmeneti mátrixszal adott Markov láncot

P_{i,i+1} = p_{i}, P_{i,i−1} = q_{i} = 1 − p_{i}, i = 0, 1, 2, …,

ahol p_{0} = 1. Bizonyítsd be, hogy a lánc pozitív visszatérő akkor és csak akkor, ha

∑_{j=0}^{∞} \frac{p_{0} … p_{j}}{q_{1} … q_{j+1}} < ∞

36. feladat. Tekintsünk egy szerencsejátékost, aki minden egyes játék alkalmával p valószínűséggel nyer 1 dollárt és q = 1 − p valószínűséggel veszít 1 dollárt. Ha az egymást követő játékok egymástól függetlenek, mi annak a valószínűsége, hogy i dollárral indulva a játékosnak N dollárja lesz? (Természetesen úgy, hogy közben a vagyona egyszer sem csökken 0-ra).

37. feladat. N darab fehér és N darab fekete golyó van szétosztva két urnába úgy, hogy mindegyikben pontosan N darab golyó van. Definiáljuk a rendszer állapotát a következőképpen. Az i-edik állapot (i = 0, 1 …, N) jelentse azt, hogy az első urnában i darab fekete golyó van. Minden lépesben egy-egy golyót húzunk az első illetve a második urnából. Azt a golyót amelyiket az első urnából húztunk a második urnába tesszük vissza, míg a másodikból húzottat az elsőbe tesszük. Add meg a p_{ij} állapotátmeneti valószínűségeket!

38. feladat. Tekintsük a következő állapotátmeneti valószínűségekkel adott Markov láncot a 0, 1, 2, … végtelen állapottéren.

P_{0,i} = P_{i} > 0, ∑_{i=0}^{∞} P_{i} = 1, ∑_{i=0}^{∞} iP_{i} < ∞

P_{i,i−1} = 1 (i ≥ 1)

Mutasd meg, hogy a lánc irreducibilis, aperiodikus, pozitív visszatérő és add meg a stacionárius eloszlását!

39. feladat. Dobjunk egy szabályos dobókockával n-szer egymás után és tegyük fel, hogy a dobások egymástól függetlenek. Legyen X_{n} az összege az n dobás során kapott értékeknek. Számítsd ki a következő határértéket

lim_{n→∞} P{X_{n} osztható 13-mal}.

40. feladat. Bizonyítsd be, hogy tetszőleges véges állapotú Markov láncnak nincs nulla visszatérő állapota, és nem lehet az összes állapota nem visszatérő!

2. Folytonos idejű Markov láncok

41. feladat. Tegyük fel, hogy bizonyos események λ paraméterű Poisson folyamat szerint generálódnak. A feladatunk az, hogy számoljuk a jelen időpontig bekövetkezett események számát. Azonban minden egyes bekövetkezett eseményt csak p valószínűséggel veszünk észre és számolunk meg. Bizonyítsd be, hogy ez a számoló folyamat Poisson folyamat λp paraméterrel!

42. feladat. Legyen {N(t), t ≥ 0} egy λ paraméterű Poisson folyamat. Számítsd ki a E{N(t)N(t + s)} mennyiséget!

43. feladat. Legyen {N_{1}(t), t ≥ 0} és {N_{2}(t), t ≥ 0} két független Poisson folyamat λ_{1} és λ_{2} paraméterekkel. Mutasd meg, hogy {N_{1}(t) + N_{2}(t), t ≥ 0} is egy Poisson folyamat λ_{1} + λ_{2} paraméterrel. Bizonyítsd be azt is, hogy annak a valószínűsége, hogy az {N_{1}(t) + N_{2}(t), t ≥ 0} összetett folyamat első bekövetkező eseménye \{N_{1}(t), t ≥ 0\}-től származik \frac{λ_{1}}{λ_{1}+λ_{2}} , függetlenül az első esemény bekövetkeztének időpontjától.

44. feladat. A 43. feladatban add meg annak a valószínűséget, hogy N_{1}(t) eléri n-et mielött még N_{2}(t) elérné m-et!

45. feladat. Legyen {N(t), t ≥ 0} egy λ paraméterű Poisson folyamat és Y legyen egy pozitív, {N(t), t ≥ 0}- től független valószínűségi változó. Számítsd ki E{N(Y)} és σ^{2}{N(Y)} mennyiségeket!

46. feladat. Tegyük fel, hogy a vevők egy λ paraméterű Poisson folyamat szerint érkeznek az üzletbe. Végtelen sok kiszolgáló van és a kiszolgálási idő exponenciális eloszlású μ paraméterrel. Mutasd meg, hogy a t-edik időpillanatban az üzletben lévő vevők száma Q(t) egy születési-halálozási folyamatot alkot. Add meg Q(t) határeloszlását!