„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…” |
aNincs szerkesztési összefoglaló |
||
| (3 közbenső módosítás ugyanattól a felhasználótól nincs mutatva) | |||
| 1. sor: | 1. sor: | ||
{{ | {{Vissza|Tömegkiszolgálás}} | ||
==Elmélet== | ==Elmélet== | ||
===Mikor nevezünk egy Markov láncot aperiodikusnak?=== | ===Mikor nevezünk egy Markov láncot aperiodikusnak?=== | ||
Egy Markov lánc i. állapota aperiodikus, ha létezik n<sub>i</sub> úgy, hogy minden n >= n<sub>i</sub> esetén p<sub>i,i</sub><sup>(n)</sup> > 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 i. állapota aperiodikus, ha létezik n<sub>i</sub> úgy, hogy minden n >= n<sub>i</sub> esetén p<sub>i,i</sub><sup>(n)</sup> > 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.) | ||
| 13. sor: | 9. sor: | ||
Ha egy irreducibilis Markov láncnak van aperiodikus állapota, akkor minden állapota az. | Ha egy irreducibilis Markov láncnak van aperiodikus állapota, akkor minden állapota az. | ||
===Mikor nevezünk egy Markov láncot irreducibilisnek?=== | ===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<sub>i,j</sub> idő, úgy, hogy p<sub>i,j</sub><sup>(n)</sup> > 0. (Azaz minden állapotból átjuthat mindegyikbe adott idő alatt) | Egy Markov lánc irreducibilis, ha minden i,j eleme S állapotpár esetén létezik n<sub>i,j</sub> idő, úgy, hogy p<sub>i,j</sub><sup>(n)</sup> > 0. (Azaz minden állapotból átjuthat mindegyikbe adott idő alatt) | ||
===Aperiodikusság boncolgatása=== | ===Aperiodikusság boncolgatása=== | ||
| 30. sor: | 21. sor: | ||
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. | 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. | ||
===Mikor nevezünk egy diszkrét idejű sztochasztikus folyamatot gyengén stacionáriusnak?=== | ===Mikor nevezünk egy diszkrét idejű sztochasztikus folyamatot gyengén stacionáriusnak?=== | ||
Y<sub>1</sub>, Y<sub>2</sub>, Y<sub>3</sub> ... sorozat gyengén stac., ha | Y<sub>1</sub>, Y<sub>2</sub>, Y<sub>3</sub> ... sorozat gyengén stac., ha | ||
* *E* (Y<sub>n</sub><sup>2</sup>) korlátos <br/> | * *E* (Y<sub>n</sub><sup>2</sup>) korlátos <br/> | ||
* *E* (Y<sub>n</sub>) = m azonosan <br/> | * *E* (Y<sub>n</sub>) = m azonosan <br/> | ||
* cov(Y<sub>i</sub>, Y<sub>j</sub>) = cov(Y<sub>0</sub>, Y<sub>j-i</sub>) = R<sub>j-i</sub> <br/> (azaz a kovariancia csak az időkülönbségtől függ, az időponttól nem) | * cov(Y<sub>i</sub>, Y<sub>j</sub>) = cov(Y<sub>0</sub>, Y<sub>j-i</sub>) = R<sub>j-i</sub> <br/> (azaz a kovariancia csak az időkülönbségtől függ, az időponttól nem) | ||
===Mikor nevezünk egy diszkrét idejű sztochasztikus folyamatot erősen stacionáriusnak?=== | ===Mikor nevezünk egy diszkrét idejű sztochasztikus folyamatot erősen stacionáriusnak?=== | ||
X<sub>1</sub>, X<sub>2</sub> ... X<sub>n</sub> és <br/> | X<sub>1</sub>, X<sub>2</sub> ... X<sub>n</sub> és <br/> | ||
X<sub>1+τ</sub>, X<sub>2+τ</sub> ... X<sub>n+τ</sub> <br/> | X<sub>1+τ</sub>, X<sub>2+τ</sub> ... X<sub>n+τ</sub> <br/> | ||
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") | 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") | ||
===Mikor nevezünk egy Markov-láncot pozitív visszatérőnek?=== | ===Mikor nevezünk egy Markov-láncot pozitív visszatérőnek?=== | ||
| 55. sor: | 38. sor: | ||
==Gyakorlat== | ==Gyakorlat== | ||
===Átmeneti-valószínűség mátrixból eloszlás=== | ===Átmeneti-valószínűség mátrixból eloszlás=== | ||
X<sub>n+1</sub> = X<sub>n</sub> Π => <br/> | X<sub>n+1</sub> = X<sub>n</sub> Π => <br/> | ||
X<sub>0</sub> = (0, 1, 0) <br/> | X<sub>0</sub> = (0, 1, 0) <br/> | ||
| 64. sor: | 45. sor: | ||
Ez a megoldás teljesen jó (még ha egy kicsit IMHO pongyola megfogalmazású is: X<sub>n</sub> nem egy vektor, annak az ''eloszlása'' az, vagyis, ha pontosak akarnánk lenni, az összes X<sub>n</sub>-et P<sup>(n)</sup>-re kéne cserélni), de szerintem gyorsabb, ha az ember alkalmazza a P<sup>(3)</sup>=P<sup>(0)</sup>Π<sup>3</sup> összefüggést. Szerintem egyszerűbb, és kevesebb a rettentő idegesítő "láncelszámolás" esélye. -- [[FoldesAdam|Földe]] - 2006.04.13. | Ez a megoldás teljesen jó (még ha egy kicsit IMHO pongyola megfogalmazású is: X<sub>n</sub> nem egy vektor, annak az ''eloszlása'' az, vagyis, ha pontosak akarnánk lenni, az összes X<sub>n</sub>-et P<sup>(n)</sup>-re kéne cserélni), de szerintem gyorsabb, ha az ember alkalmazza a P<sup>(3)</sup>=P<sup>(0)</sup>Π<sup>3</sup> összefüggést. Szerintem egyszerűbb, és kevesebb a rettentő idegesítő "láncelszámolás" esélye. -- [[FoldesAdam|Földe]] - 2006.04.13. | ||
===Véges állapotú Markov lánc stabilitása Π alapján=== | ===Véges állapotú Markov lánc stabilitása Π alapján=== | ||
Gráfot rajzolva jobban áttekinthető. 1..4 az állapotok. Ha az i. sor j. eleme pozitív, akkor i->j él van. | 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 | Mivel a véges állapot 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 helyben marad. | ||
Mivel a lánc irred, egyetlen állapot aperiodikusságából az összes állapot aperiodikussága következik. => a lánc stabil. | Mivel a lánc irred, egyetlen állapot aperiodikusságából az összes állapot aperiodikussága következik. => a lánc stabil. | ||
===Határeloszlás 2x2-es Π esetén=== | ===Határeloszlás 2x2-es Π esetén=== | ||
A feladat szövege alapján Π | A feladat szövege alapján Π | ||
| 105. sor: | 78. sor: | ||
===Bináris Markov lánc, Π értelmezése=== | ===Bináris Markov lánc, Π értelmezése=== | ||
Π 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. <br/> | Π 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. <br/> | ||
Így tehát 0-ból indítva a 0 sorozat hossza a G(0,1) geometriai eloszlás. <br/> | Így tehát 0-ból indítva a 0 sorozat hossza a G(0,1) geometriai eloszlás. <br/> | ||
| 117. sor: | 88. sor: | ||
-- [[SzaMa|SzaMa]] - 2005.04.11. | -- [[SzaMa|SzaMa]] - 2005.04.11. | ||
Az 1 állapotban tartózkodás ideje Geo eloszlás. | Az 1 állapotban tartózkodás ideje Geo eloszlás. | ||
| 130. sor: | 100. sor: | ||
0,1 - 0,9*0,7<sup>-2</sup>*(0,7*0,3) + 0,9*0,7<sup>-2</sup>*Σ<sub>k=0..∞</sub> k*0,7<sup>k</sup>*0,3 = <br/> | 0,1 - 0,9*0,7<sup>-2</sup>*(0,7*0,3) + 0,9*0,7<sup>-2</sup>*Σ<sub>k=0..∞</sub> k*0,7<sup>k</sup>*0,3 = <br/> | ||
0,1 - 0,9*0,7<sup>-1</sup>*0,3 + 0,9*0,7<sup>-2</sup>*0,3<sup>-1</sup> | 0,1 - 0,9*0,7<sup>-1</sup>*0,3 + 0,9*0,7<sup>-2</sup>*0,3<sup>-1</sup> | ||
===Foster kritérium=== | ===Foster kritérium=== | ||
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. | 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. | ||
| 150. sor: | 115. sor: | ||
Ha hibát találtok benne kérlek javítsátok. | Ha hibát találtok benne kérlek javítsátok. | ||
-- [[BrezinaP|Brez]] - 2005.04.13. | -- [[BrezinaP|Brez]] - 2005.04.13. | ||
Rajzoljuk fel a gráfot. | Rajzoljuk fel a gráfot. | ||
| 159. sor: | 122. sor: | ||
Az állapotátmeneti mátrix: | Az állapotátmeneti mátrix: | ||
{| class="wikitable" border="1" style="text-align:center;" | |||
p(1-q) | |- | ||
| 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: | Ekkor felírjuk a Foster kritériumot: | ||
| 186. sor: | 151. sor: | ||
===Határeloszlás végtelen Π esetén=== | ===Határeloszlás végtelen Π esetén=== | ||
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. | 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. | ||
| 212. sor: | 174. sor: | ||
===Duplán sztochasztikus Π=== | ===Duplán sztochasztikus Π=== | ||
Müller Viktor elbeszélése alapján :) | Müller Viktor elbeszélése alapján :) | ||
lim<sub>n->∞</sub><b>P</b>(2004 | X<sub>n</sub>) | lim<sub>n->∞</sub><b>P</b>(2004 | X<sub>n</sub>) | ||
| 231. sor: | 191. sor: | ||
[[ | [[Kategória:Mérnök informatikus MSc]] | ||