Tömegkiszolgálás - Összefoglaló

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

%TOC{ depth="3" }%

Elmélet

Mikor nevezünk egy Markov láncot aperiodikusnak?

Egy Markov lánc i. állapota aperiodikus, ha létezik n_i úgy, hogy minden n >= n_i esetén p_i,i⁽ⁿ⁾ > 0. (Azaz, hogy egy küszöbszám felett mindegyik időpontban pozitív valószínűséggel visszatérhet a lánc az adott állapotba.)

Egy Markov lánc aperiodikus, ha minden állapota aperiodikus.

Ha egy irreducibilis Markov láncnak van aperiodikus állapota, akkor minden állapota az.

-- SzaMa - 2005.04.11.

Mikor nevezünk egy Markov láncot irreducibilisnek?

Egy Markov lánc irreducibilis, ha minden i,j eleme S állapotpár esetén létezik n_i,j idő, úgy, hogy p_i,j⁽ⁿ⁾ > 0. (Azaz minden állapotból átjuthat mindegyikbe adott idő alatt)

-- SzaMa - 2005.04.11.

Aperiodikusság boncolgatása

Ha van egy A állapotod, amiből indulva végtelen sok olyan időpont van, hogy bizotsan nem lehetsz A-ban, az periodikus. Például ha jobbra-balra-le-föl egyesével lépdelsz a sakktáblán, az periodikus, mert feketéről mindig fehérre lépsz, fehérről feketére, tehát csakis páros lépésben térhetsz vissza. A definíció szerint: ez nem aperiodikus, mert akármilyen nagy lépésszámot veszel, van fölötte leglább egy olyan lépésszám, amikor nincs esélyed A-ba visszajutni.

Aperiodikusság körökkel: a definíciót úgy is megfogalmazhatjuk, hogy minden n>n_i-re létezik n hosszú A-n átmenő kör (precízen: zárt séta, ahol minden lépés valószínűsége pozitív).

A sakktáblás példában csak páros hosszú körök vannak, tehát nem aperiodikus

Ha van egy n és m hosszú kör, ahol n és m relatív prímek, akkor ezek összekapcsolásával egy érték fölött tetszőleges k hosszúságú kör kirakható (azaz aperiodikus a lánc): az n hosszú körön sétálok, amíg a lépésszámom megegyezik k-val mod m, majd megfelelő számú kört megyek az m hosszú körön.

-- SzaMa - 2005.11.21.

Mikor nevezünk egy diszkrét idejű sztochasztikus folyamatot gyengén stacionáriusnak?

Y₁, Y₂, Y₃ ... sorozat gyengén stac., ha

• *E* (Y_n²) korlátos
  
• *E* (Y_n) = m azonosan
  
• cov(Y_i, Y_j) = cov(Y₀, Y_j-i) = R_j-i
  (azaz a kovariancia csak az időkülönbségtől függ, az időponttól nem)

-- SzaMa - 2005.04.11.

Mikor nevezünk egy diszkrét idejű sztochasztikus folyamatot erősen stacionáriusnak?

X₁, X₂ ... X_n és
X_1+τ, X_2+τ ... X_n+τ
vv. vektorok eloszlása azonos n-től és τ-tól függetlenül. (~ bárhonnan választok két azonos méretű időintervallumot, a folyamat "ugyanúgy viselkedik")

-- SzaMa - 2005.04.11.

Mikor nevezünk egy Markov-láncot pozitív visszatérőnek?

Ehhez kell az egész visszatérőség témakör: 19. oldal.

Gyakorlat

Átmeneti-valószínűség mátrixból eloszlás

http://info.sch.bme.hu/document.php?cmd=download_proc&tmp_page=&doc_id=8275 3. példa

X_n+1 = X_n Π =>
X₀ = (0, 1, 0)
X₁ = (0, 1/2, 1/2)
X₂ = (1/2, 1/4, 1/4)
X₂ = (2/4, 3/8, 1/8)
* Ide nem X₃ -at akartál írni? :) -- Olthyer - 2005.04.14.

Ez a megoldás teljesen jó (még ha egy kicsit IMHO pongyola megfogalmazású is: X_n nem egy vektor, annak az eloszlása az, vagyis, ha pontosak akarnánk lenni, az összes X_n-et P⁽ⁿ⁾-re kéne cserélni), de szerintem gyorsabb, ha az ember alkalmazza a P⁽³⁾=P⁽⁰⁾Π³ összefüggést. Szerintem egyszerűbb, és kevesebb a rettentő idegesítő "láncelszámolás" esélye. -- Földe - 2006.04.13.

-- SzaMa - 2005.04.11.

Véges állapotú Markov lánc stabilitása Π alapján

http://info.sch.bme.hu/document.php?cmd=download_proc&tmp_page=&doc_id=8275 2. példa

Gráfot rajzolva jobban áttekinthető. 1..4 az állapotok. Ha az i. sor j. eleme pozitív, akkor i->j él van.

Mivel a véges állpot van, az irreducibilitás és aperiodikusság elégséges feltétele a stabilitásnak. Irred, mivel 1->4->3->2->1 körön bármelyik állapotból eljuthatunk bármelyikbe. Az 1 állapot aperiodikus, mivel poz. valószínűséggel helybenmarad. Mivel a lánc irred, egyetlen állapot aperiodikusságából az összes állapot aperiodikussága következik. => a lánc stabil.

-- SzaMa - 2005.04.11.

Határeloszlás 2x2-es Π esetén

http://info.sch.bme.hu/document.php?cmd=download_proc&tmp_page=&doc_id=8275 4. példa

A feladat szövege alapján Π

1-β	β
1-α	α

A p^(∞) határeloszlás a p^(∞)=p^(∞) Π egyenlet egyértelmű megoldása.

Órai példa volt, hog

1-p	p
q	1-q

Esetén p^(∞) = (q/(p+q), p/(p+q)).

Tessék behelyettesíteni, és ellenőrizni!

-- SzaMa - 2005.04.11.

Bináris Markov lánc, Π értelmezése

http://info.sch.bme.hu/document.php?cmd=download_proc&tmp_page=&doc_id=8275 1. példa

Π alapján a 0-ban maradás esélye minden lépésben 0,9; a 0->1 lépés esélye 0,1.
Így tehát 0-ból indítva a 0 sorozat hossza a G(0,1) geometriai eloszlás.
P(k)=0,9^k-10,1; várható érték: 1/0,1 = 10.

Ugyanígy a csupa 1 sorozat hosszának várható értéke 1/0,01 = 100.

(Ezt a részt szerda este javítottam ki, köszi Zoz, hogy szóltál. Pedig Laci is mondta, hogy a józan ész szerint ellenőrizzük az eredményt: ha a sor nagy eséllyel marad az 1 állapotban, akkor logikus, hogy hosszú csupa 1 sorozatok várhatóak.)

-- SzaMa - 2005.04.11.

http://info.sch.bme.hu/document.php?cmd=download_proc&tmp_page=&doc_id=8274 2. példa

Az 1 állapotban tartózkodás ideje Geo eloszlás.

0-ból indítva 0-ba visszatérés valósíznűsége:
P(1) = 0,1 azaz helybenmarad. P(k) = 0,9*0,7^k-2*0,3 azaz 1-be megy, k-2 idejig ott tartozkodik, majd 0-ba tér vissza.

• E* = Σ_k=0..∞ k*P(k) =
  

0,1 + Σ_k=2..∞ k*0,9*0,7^k-2*0,3 =
0,1 + 0,9*0,7^-2*Σ_k=2..∞ k*0,7^k*0,3 =
0,1 - 0,9*0,7^-2*(0,7*0,3) + 0,9*0,7^-2*Σ_k=0..∞ k*0,7^k*0,3 =
0,1 - 0,9*0,7^-1*0,3 + 0,9*0,7^-2*0,3^-1

-- SzaMa - 2005.04.11.

Foster kritérium

http://info.sch.bme.hu/document.php?cmd=download_proc&tmp_page=&doc_id=8274 3. példa

A Foster kritériumhoz kell hogy a lánc irreducibilis és aperiodikus legyen. Az irreducibilitás teljesül, hiszen ha gráfot rajzolunk az átmenetmátrixból, akkor minden állapotból mutat nyíl mind az elöző állapotba mind a következőbe. Aperiodikus is hiszen pl. a kettes állapot önmagába pozitív p valószínűséggel tér vissza, és mivel irreducibilis és van egy aperiodikus állapota ezért az egész lánc aperiodikus. Így használhatjuk a Foster kritériumot.

I=0-ra:

E(X_n+1|X_n=0)=(1-2p)*0+2p*1 =< C k>I-re:

E(X_n+1|X_n=k) =

(1-3p)(k-1)+pk+2p(k+1) =

k-3pk-1+3p+pk+2pk+2p =

k+5p-1 = k-(1-5p) < k-d ebből d=1-5p és d>0 ezért p<1/5. Azaz akkor stabil, ha 0<p<1/5.

Ha hibát találtok benne kérlek javítsátok. -- Brez - 2005.04.13. http://info.sch.bme.hu/document.php?cmd=download_proc&tmp_page=&doc_id=8279# feladat Rajzoljuk fel a gráfot. irreducibilis (kapásból látszik) ha q>0, p>0 aperiodikus mert van 1 aper. állapot (pl 0.) + még irreduc --> öröklődik az aper --> aperiódikus a lánc. Az állapotátmeneti mátrix: (fix szélességű betűmérettel nézd)

 
 1-q			 q				  0				0			  0	  0 ...
p(1-q)  qp+(1-q)(1-p)	  q(1-p)			 0			  0	  0 ...
  0		  p(1-q)	  qp+(1-q)(1-p)	  q(1-p)		  0	  0 ...
  0			  0			  p(1-q)	  qp+(1-q)(1-p)  q(1-p)  0 ...

Ekkor felírjuk a Foster kritériumot: k=0 lesz

0< I <= 0 -> I=0 ra:

E(Xn+1 | Xn = 0) = (1-q)*0 + q*1 + 0 + 0 +... = q <= C

I > 0 -ra

E(Xn+1 | Xn = k) = p*(1-q)*(k-1) + (qp+(1-q)*(1-p))*k + q*(1-p)*(k+1) = ...

= k-p+q <= k-d ---> 0 < d <= p-q ---> 0 < p-q ---> q

stabil. -- Zoz - 2005.04.14.

Határeloszlás végtelen Π esetén

http://info.sch.bme.hu/document.php?cmd=download_proc&tmp_page=&doc_id=8279 4. példa

A megoldást továbbra is a P=PΠ egyenlet fogja adni, csak mivel végtelen a Π mátrix ezért a következőt csináljuk: kiszámítjuk a határeloszlás első néhány elemét, ebből megsejtjük a megoldást, és teljes indukcióval bebizonyítjuk.

első oszlop:

p₀=(1-2p)p₀+(1-3p)p₁ --> p₁=2p/(1-3p)p₀ második oszlop:

p₁=2pp₀+pp₁+(1-3p)p₂ --> p₂=(2p/(1-3p))²p₀ sejtés: p_i=(2p/(1-3p))ⁱp₀ bizonyítás teljes indukcióval: i=<2-re teljesül -> pipa tegyük fel hogy p_k-ra teljesül nézzük meg hogy teljesül-e p_k+1-re

1. p_k=2pp_k-1+pp_k+(1-3p)p_k+1

2. p_k(1-p)-2pp_k-1=(1-3p)p_k+1

3. (2p/(1-3p))^kp₀(1-p)-2p(2p/(1-3p))^k-1p₀=(1-3p)p_k+1

4. p₀(((2p)^k-(2p)^kp)/(1-3p)^k-((2p)^k)/(1-3p)^k-1)=(1-3p)p_k+1

5. p₀(2p(2p)^k/(1-3p)^k+1)=p_k+1

6. p_k+1=(2p/(1-3p))^k+1p₀

p_k+1-re teljesült tehát helyes volt a feltevésünk.

-- Brez - 2005.04.13.

Duplán sztochasztikus Π

Müller Viktor elbeszélése alapján :)

http://info.sch.bme.hu/document.php?cmd=download_proc&tmp_page=&doc_id=8279 1. példa

lim_n->∞P(2004 | X_n)

Itt annak a valószínűségét vizsgáljuk, hogy a dobások összege osztható 2004-gyel (gáz, hogy a feltétles valószínűséget is így jelöljük). Mondhatjuk úgy is, hogy X_n = 0 (mod 2004).

A dobokockánál 1/6 - 1/6 eséllyel nő 1..6-tal X_n.

Tehát ha felírjuk az X_n (mod 2004) állapotaival az átmeneti-valószínűség-mátrixot, akkor az első sor 0-val kezdődik, majd 6 darab 1/6, a többi 0. A második sor ugyanez, eggyel jobbra shiftelve. Ebből láthatjuk, hogy a mátrix duplán sztochasztikus, azaz minden sor, és minden oszlop összege 1. Órán tanultuk, hogy d. szt. mátrix esetén a határeloszlás egyenletes. Mivel 2004 állapot van, a keresett valószínűség 1/2004.

Ja igen, nem árt belátni, hogy egyáltalán stabil, hogy lehessen határeloszlásról beszélni:

• véges állapotú (mod 2004)
• irreducibilis: csupa 1-es dobással 2004 lépésben végigjárható pozitív valószínűséggel.
• aperiodikus: két olyan kört kell előállítani, amik hossza relatív prím, és ezekből egy határérték felett bármilyen hosszúságú kör előállítható (átgondolandó...). Csupa 6-ossal 334 dobással körbeérünk, csupa 1-essel 2004 alatt. 334..2004 hosszú körök minden további nélkül előállíthatóak, ezek között kell pl. két prímszámot találni.

-- SzaMa - 2005.04.14.