„Tömegkiszolgálás - Összefoglaló” változatai közötti eltérés
Új oldal, tartalma: „{{GlobalTemplate|Infoalap|ToKiZh}} %TOC{ depth="3" }% ==Elmélet== ===Mikor nevezünk egy Markov láncot aperiodikusnak?=== Egy Markov lánc i. állapota aperiodik…” |
a Szikszayl átnevezte a(z) ToKi zh tudástár lapot a következő névre: Tömegkiszolgálás összefoglaló |
(Nincs különbség)
| |
A lap 2014. január 18., 14:48-kori változata
Ez az oldal a korábbi SCH wikiről lett áthozva.
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 ni úgy, hogy minden n >= ni esetén pi,i(n) > 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 ni,j idő, úgy, hogy pi,j(n) > 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>ni-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?
Y1, Y2, Y3 ... sorozat gyengén stac., ha
- *E* (Yn2) korlátos
- *E* (Yn) = m azonosan
- cov(Yi, Yj) = cov(Y0, Yj-i) = Rj-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?
X1, X2 ... Xn és
X1+τ, X2+τ ... Xn+τ
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
Xn+1 = Xn Π =>
X0 = (0, 1, 0)
X1 = (0, 1/2, 1/2)
X2 = (1/2, 1/4, 1/4)
X2 = (2/4, 3/8, 1/8)
* Ide nem X3 -at akartál írni? :) -- Olthyer - 2005.04.14.
Ez a megoldás teljesen jó (még ha egy kicsit IMHO pongyola megfogalmazású is: Xn nem egy vektor, annak az eloszlása az, vagyis, ha pontosak akarnánk lenni, az összes Xn-et P(n)-re kéne cserélni), de szerintem gyorsabb, ha az ember alkalmazza a P(3)=P(0)Π3 ö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,9k-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,7k-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,7k-2*0,3 =
0,1 + 0,9*0,7-2*Σk=2..∞ k*0,7k*0,3 =
0,1 - 0,9*0,7-2*(0,7*0,3) + 0,9*0,7-2*Σk=0..∞ k*0,7k*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(Xn+1|Xn=0)=(1-2p)*0+2p*1 =< C k>I-re:
E(Xn+1|Xn=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:
p0=(1-2p)p0+(1-3p)p1 --> p1=2p/(1-3p)p0 második oszlop:
p1=2pp0+pp1+(1-3p)p2 --> p2=(2p/(1-3p))2p0 sejtés: pi=(2p/(1-3p))ip0 bizonyítás teljes indukcióval: i=<2-re teljesül -> pipa tegyük fel hogy pk-ra teljesül nézzük meg hogy teljesül-e pk+1-re
1. pk=2ppk-1+ppk+(1-3p)pk+1
2. pk(1-p)-2ppk-1=(1-3p)pk+1
3. (2p/(1-3p))kp0(1-p)-2p(2p/(1-3p))k-1p0=(1-3p)pk+1
4. p0(((2p)k-(2p)kp)/(1-3p)k-((2p)k)/(1-3p)k-1)=(1-3p)pk+1
5. p0(2p(2p)k/(1-3p)k+1)=pk+1
6. pk+1=(2p/(1-3p))k+1p0
pk+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
limn->∞P(2004 | Xn)
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 Xn = 0 (mod 2004).
A dobokockánál 1/6 - 1/6 eséllyel nő 1..6-tal Xn.
Tehát ha felírjuk az Xn (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.
