Szikszayl, 2014. március 13., 12:54-n

2014-03-13T12:54:07Z

← Régebbi változat		A lap 2014. március 13., 14:54-kori változata
191. sor:		191. sor:


	[[~~Category~~:~~InfoMsc~~]]		[[Kategória:Mérnök informatikus MSc]]

Szikszayl: Szikszayl átnevezte a(z) Tömegkiszolgálás összefoglaló lapot a következő névre: Tömegkiszolgálás - Összefoglaló

2014-02-25T17:28:25Z

Szikszayl átnevezte a(z) Tömegkiszolgálás összefoglaló lapot a következő névre: Tömegkiszolgálás - Összefoglaló

← Régebbi változat	A lap 2014. február 25., 19:28-kori változata
(Nincs különbség)

Szikszayl, 2014. február 25., 17:21-n

2014-02-25T17:21:48Z

Változtatások megtekintése

Szikszayl: Szikszayl átnevezte a(z) ToKi zh tudástár lapot a következő névre: Tömegkiszolgálás összefoglaló

2014-01-18T13:48:18Z

Szikszayl átnevezte a(z) ToKi zh tudástár lapot a következő névre: Tömegkiszolgálás összefoglaló

← Régebbi változat	A lap 2014. január 18., 15:48-kori változata
(Nincs különbség)

Unknown user: Ú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…”

2012-10-21T20:24:46Z

Ú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…”

Új lap

{{GlobalTemplate|Infoalap|ToKiZh}}

%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|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|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|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|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|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? :) -- [[KissAnett|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. -- [[FoldesAdam|Földe]] - 2006.04.13.

-- [[SzaMa|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|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 Π

{| border="1"
| 1-β || β
|-
| 1-α || α
|}

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

Órai példa volt, hog

{| border="1"
| 1-p || p
|-
| q || 1-q
|}
Esetén p(∞) = (q/(p+q), p/(p+q)).

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

-- [[SzaMa|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|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|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.
-- [[BrezinaP|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)

<pre>

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 ...

</pre>

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

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.
-- [[ZozZ|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.

-- [[BrezinaP|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|SzaMa]] - 2005.04.14.

[[Category:Infoalap]]

Tömegkiszolgálás - Összefoglaló - Laptörténet

Szikszayl, 2014. március 13., 12:54-n

Szikszayl: Szikszayl átnevezte a(z) Tömegkiszolgálás összefoglaló lapot a következő névre: Tömegkiszolgálás - Összefoglaló

Szikszayl, 2014. február 25., 17:21-n

Szikszayl: Szikszayl átnevezte a(z) ToKi zh tudástár lapot a következő névre: Tömegkiszolgálás összefoglaló

Unknown user: Ú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…”