Szeidl László: Tömegkiszolgálás (Összefoglaló, 2009/2010 tanév II. félév)
Óbudai Egyetem Neumann János Informatikai Kar
Téma 1
Tömegkiszolgálási rendszerek általános fogalmak Tömegkiszolgálási rendszerek matematikai leírása, sematikus ábrázolás, példák. Tömegkiszolgálási rendszerek Kendall-féle jelölésrendszere és osztályozása A tárgy kialakulásának kezdete visszanyúlik Erlang (1878-1929) munkáihoz, melyet a koppenhágai telefontársaságnál végzett. A kialakult terminus-technicus a mai napig sok tekintetben köt½odik a telekommunikációban megszokott fogalmakhoz (csatorna, hívás, sorhosszúság, foglaltság, hívás visszautasítása, stb.). A sorbanállási, vagy más szóval tömegkiszolgálási rendszerek (TKR-ek) elméletének gyors fejl½odése annak köszönhet½o, hogy igen széles körben lehet alkalmazni a gyakorlati élet rendkívül széles területein. Egy TKR akár több TKR-b½ol is állhat, m½uködésük leírására csak igen korlátozott mértékben állnak rendelkezésre analitikus eredmények. Sok esetben közelít½o eljárások, illetve szimulációs módszerek alkalmazása hozhat megfelel½o eredményt. Közös ezekben a rendszerekben: – igények megjelenése (beérkezési folyamat), – a rendszer struktúrája, amely szerint az igények vándorolhatnak a rendszerben, – kiszolgáló egységek, kiszolgálási elvek, kiszolgálási id½ok, – sorbanállási helyek, várakozás (sorok képz½odése), ill. elutasítás, – kiszolgálás (tágabb értelemben is), – igények távozása a rendszerb½ol (távozási folyamat). Megjegyzés 1 Általában elvonatkoztathatunk a vizsgált rendszerek konkrét jellegét½ol. Ez annak köszönhet½o, hogy a vizsgálatok gyakran bizonyos id½opontok halmazához (igények megjelenése a rendszerben, kiszolgálások kezdete, ill. befejezése, stb.) köt½odnek, ezért el lehet tekinteni az igények és kiszolgálások valós hátterét½ol.
1
Példák: telekommunikációs rendszerek, számítógép, számítógépes hálózatok, Internet, közlekedési rendszerek (közúti, vasúti), repül½otér (útlevél-, jegy-, csomagellen½orzés, boltok, ...), tengeri kiköt½ok, szervizek, szállítás, kereskedelem, bevásárló központok, bankok, jegyirodák, gyártórendszerek, készletgazdálkodás, kórházak, szakorvosi rendel½ok, stb. Sematikus ábrázolások (ld. 1–4. ábra). A legegyszer½ubb, egy sorból és egy kiszolgáló egységb½ol álló tömegkiszolgálási rendszer:
sorbanálló igények
távozó igények
beérkező igények
sorbanálló helyek
kiszolgáló egység
1. ábra
Több kiszolgáló egységb½ol álló párhuzamos kiszolgálóegységes rendszer.
2
1.
2.
•••
M.
2. ábra
Több (téglalappal jelölt ) tömegkiszolgálási egységb½ol álló zárt tömegkiszolgálási rendszer. Az egyes tömegkiszolgálási egységek állhatnak további egyszer½u, vagy összett TKR-ekb½ol
3. ábra
3
Több tömegkiszolgálási egységb½ol álló nyílt tömegkiszolgálási rendszer ábrázolása. Hasonlóan a 3. ábrához, az egyes tömegkiszolgálási egységek itt is tartalmazhatnak további egyszer½u, vagy összett TKR-ket a rendszerből távozó igények
külső forrásból érkező igények
a rendszerből távozó igények
külső forrásból érkező igények
4. ábra
Tömegkiszolgálási rendszerek matematikai leírása Azonosítanunk kell a beérkezési folyamatot, amely a beérkez½o igényeket írja le (absztrakt igények is lehetnek, továbbá igények képz½odhetnek a TKR-en belül is). A rendszerbe lép½o igények száma és eloszlása függhet a rendszer állapotától. A beérkezési folyamatot általában az egymás után érkez½o igények közötti id½ointervallumok valószín½uségeloszlásának segítségével írjuk le. A vizsgált rendszer struktúrája, amely szerint vándorolhatnak az igények a TKR kiszolgálóegységei között (pl. egy beteg különböz½o ellátása a korházi gyógykezelés során; fogorvosi rendel½o egy, vagy több fogorvos esetén; áruházi bevásárlás; kommunikáció az Interneten, stb.). Kiszolgálás szabályai (elvei): FCFS (a korábban érkez½o igény kiszolgásása korábban kezd½odik meg), prioritásos, stb. A TKR meghatározandó jellemz½oi, mutatói, melyek összefüggnek a vizsgálat céljaival. Megemlítünk néhány jellemz½o példát. Várakozási rendszereknél: átlagos várakozási id½o a kiszolgálás megkezdéséig, átlagos 4
sorhosszúság, sorhosszúság eloszlása. Elutasításos rendszereknél: elutasítás valószín½usége, elutasítások átlagos száma. Hatékonysági mértékek esetében: átlagos kihasználtság, kiszolgált igények átlagos száma, stb. (Ezeket a fogalmakat matematikailag korrekt módon a kés½obbiek során adjuk meg.)
Centrális zárt rendszer A számítógépek egyik legegyszer½ubb matematikai modelljének is tekinthet½o a következ½o, s az 5. ábrával szemléltetett rendszer.
F1(x)
p1 p0 F0(x)
pM FM(x)
5. ábra
A rendszer statisztikus viselkedése a következ½o paramérekkel írható le: – A rendszerben rögzített K számú igény van állandóan (emiatt nevezzük zártnak) és a megadott ábra szerint vándorolhatnaknak az igények. – Minden egyes kiszolgálóegység el½ott kell½o számú sorbanállóhely van, a felmerül½o (legfeljebb (K 1) igény számára. – A kiszolgálóegységeken a FCFS elv szerint történik a kiszolgálás; a kiszolgálási id½ok összességükben függetlenek, s az i-edik egységen azonos Fi (x); 0 i M eloszlásúak. – Ha egy kiszolgálás befejez½odik a 0-ik egységen, akkor onnan az igény pi ; 0 i M (pi 0; p0 + ::: + pM = 1) valószín½uséggel átmegy az i-edik egységre, a rendszer
5
állapotától és a kiszolgálási id½okt½ol függetlenül. Ha pedig egy igény kiszolgálása valamelyik i-edik, 1 i M egységen ér véget, akkor 1 valószín½uséggel a 0-ik kiszolgálóegységhez kerül. A 0-ik kiszolgálóegység ezen kitüntetett szerepe miatt ezt az egységet központi (centrális) kiszolgálóegységnek nevezzük. A vizsgált rendszer ezért kapta a centrális zárt TKR elnevezést. Megjegyzés 2 Számítógépek esetén szigorúnak tünhet az a megszorítás, hogy a rendszer zárt, vagyis állandóan n-számú igény tartózkodik a rendszerben. Ha a rendszer kihasználtságát vizsgáljuk, akkor nem mindegy az, hogy milyen küls½o terhelés mellett tesszük, a rendszer zártsága ebben az esetben azt jelenti, hogy ha egy program futása befejez½odik, akkor helyette egy másik program lép be a rendszerbe, amit a 0-ik egységr½ol a 0-ik egységre való visszatérés jelenthet az adott esetben.
Tömegkiszolgálási rendszerek Kendall-féle osztályozása A legkülönfélébb gyakorlati feladatok megoldása során sokszor el½ofordul ugyanaz a matematikai modell, amellyel modellezhet½o a probléma. Másrészr½ol, általában a bonyolult TKR-ek egyszer½ubb épít½okövekb½ol (egyszer½ubb TKR-ekb½ol) építhet½ok fel. Mindez már régóta szükségessé tette az alapvet½o és leggyakrabban el½oforduló tömegkiszolgálási rendszerek osztályozását. A tömegkiszolgálási rendszerek alapvet½o típusait a következ½o négyrészes szimbólum foglalja össze: AjBjmjn ahol A - az igények beérkezése közötti id½oközök eloszlása; B - kiszolgálási id½ok eloszlása; m - a kiszolgáló egységek száma (lehet véges, vagy végtelen); n - a várakozási helyek száma, ahol a beérkezett, de kiszolgálásra nem került igények várakozhatnak. Néha szerepel GI is, ami arra utal, hogy az egymásutáni beérkezési, vagy kiszolgálási id½ok általános eloszlásúak és függetlenek. Ha a négyrészes szimbólum utolsó része 1, akkor AjBjmj1 helyett gyakran használatos a következ½o jelölés
AjBjm: Ha a sorbanállóhelyek száma n = 0, akkor ezt a rendszert elutasításos rendszernek nevezzük.
6
El½ofordulhat az AjBjmjnje x jelölés is, ahol az A; B; m és n jelentése a korábbi, e jelenti az igényforrások számát, x pedig a kiszolgálás elvét. Az A és B változók általában a következ½o értékeket vehetik fel: M (exponenciális), Er (r-edrend½u Erlang), Hr (r-edrend½u hiperexponenciális), D (determinisztikus), G (általános). A meghatározásban szerepl½o Erlang- és hiperexponenciális eloszlások a kétparaméteres gamma eloszlás segítségével adhatók meg: Az ( ; ) paraméter½u gamma eloszlás ( > 0; > 0) s½ur½uségfüggvénye: f (x; ; ) =
( )
x
1
e
x
;
x > 0;
( )=
Z1
x
1
e
x
dx:
0
Ekkor = 1 esetén az exponenciális eloszlás; = n=2; = 1=2 esetén a 2n eloszlás; = n ; = n esetén pedig az Erlang-eloszlás adódik. (m; 1 ; :::; m ; 1 ; :::; m ) k ; k 0; 1 +:::+ m = 1 paraméter½u hiperexponenciális eloszlás exponenciális eloszlások keveréke, melynek s½ur½uségfüggvénye: f (x) =
m X
k ke
kx
; x > 0:
k=1
Feltételek: rendszerünkben, ha egy igény beérkezésekor van szabad kiszolgálóegység, akkor az igény azonnal kiszolgálásra kerül; ha nincs, sorba áll és várakozik mindaddig, amíg fel nem szabadul egy egység. Ha egy igény beérkezésekor az összes m sorbanállóhely foglalt, akkor az igény kiszolgálás nélkül távozik a rendszerb½ol (a rendszer elutasítja az igényt). A kiszolgálóegységek nem romlanak el és képesek arra, hogy egy igény kiszolgálása után azonnal megkezdjék a következ½o igény kiszolgálását. A sorbanállók között a kiszolgálás a rendszer meghatározott kiszolgálási elve szerint történik. A kiszolgálás módja és a várakozó igények közül való választás sokféle kiszolgálási algoritmus (kiszolgálási elv) szerint történhet
7
Téma 2
Kiszolgálási algoritmusok Leggyakrabban el½oforduló kiszolgálási elvek. Az egyszer½u GjGj1 (GjGj1j1) típusú tömegkiszolgálási rendszer matematikai leírása. Meghatározó sorozat, igények beérkezési- és távozási id½opontjai, sorhosszúság. Egy TKR vizsgálatát alapvet½oen az határozza meg, hogy a rendszer m½uködését milyen szempontból elemezzük. Általában olyan mutatók vizsgálata a cél, amelyek valamilyen értelemben jellemzik a rendszer m½uködésének hatékonyságát. Ezek a vizsgálatok nem csak egy m½uköd½o rendszer elemzésére és hatékonyságának növelésére irányulhatnak, hanem már a tervezés fázisában is fontos támpontokat jelenthetnek. Egy bonyolultabb, több kiszolgálóegységb½ol álló tömegkiszolgálási hálózat m½uködésének hatékonysága nem csak attól függ, hogy az egyes elemei milyen gyorsan és jól m½uködnek, hanem sok esetben alapvet½o szerepe van annak is, hogy a kiszolgálás milyen algoritmus szerint történik. De…níció 1 Kiszolgálási algoritmusok alatt olyan kiszolgálási eljárásokat (szabályokat) értünk, amelyek tetsz½oleges id½opontban megmondják, hogy a rendszerben lév½o igények közül melyiket kell éppen kiszolgálni, milyen sorrendben egymás után és milyen hosszú ideig tart a kiszolgálás. A kiszolgálási algoritmusokkal szemben támasztott igények különböz½oek lehetnek. Adatátvitel esetében lehet a kiszolgálás késleltetéssel szemben érzékeny (pl. telefon, videokonferencia), de más és más lehet egy esetleges adatvesztés következménye is (pl. egy számítógépes program esetén az átvitt anyag használhatatlanná válhat, ugyanakkor beszédátvitelnél esetleg csak kismérték½u min½oségromlással jár). Ennek megfelel½oen a kiszolgálási algoritmusoknak általában meghatározott kritériumoknak kell eleget tenni. Megjegyzés 3 A kiszolgálási kapacitás növelése a kapacitás kihasználtsága szempontjából sok esetben nem hatékony, viszont a megfelel½o kiszolgálási algoritmus kialakításával jelent½os eredményeket lehet elérni.
8
Leggyakrabban el½oforduló általánosabb kiszolgálási algoritmusok (kiszolgálási elvek) FIFO (First In First Out): Ha a kiszolgáló egység üres az igény beérkezésének id½opontjában, akkor a kiszolgálása haladéktalanul megkezd½odik és egészen addig tart, amíg a teljes kiszolgálás befejez½odik. Ha a beérkez½o igény a kiszolgáló egységet nem találja üresen, akkor az igények kiszolgálása a beérkezés sorrendjében történik. LIFO (Last In First Out): A kiszolgáló egységnél a sorbanálló igények kiszolgálása úgy történik, hogy egy igény kiszolgálása befejez½odik, akkor a rendszerbe utójára belépett igény kiszolgálása kezd½odik meg és tart a teljes kiszolgálásig. A FCFS (First Come First Served – el½oször érkezett, el½oször lesz kiszolgálva) és a LCFS (Last Come First Served – utoljára érkezett, el½oször lesz kiszolgálva) kiszolgálási elvek hasonlítanak a FIFO és LIFO elvekhez: a kiszolgáló egységnél a sorbanálló igények közül az az igény kerül el½oször kiszolgálásra, amelyik el½obb (vagy kés½obb) érkezett. Minthogy sok rendszerre az eredmény ugyanaz, ezért néha FIFO és FCFS (LIFO és LCFS) kiszolgási eljárásokat egymás szinonímájaként használják, de jó tudni a közöttük lev½o különbséget. Egyszer½u példaként említjük a 2. ábrán bemutatott párhuzamos kiszolgáló egységes rendszert, melyre könny½u látni, hogy a FCFS elv teljesülhet anélkül, hogy a FIFO elv fennállna. Véletlen sorrend: A sorbanállók közül a választás véletlenszer½uen, pl. egyenletes eloszlás szerinti sorsolással történik és a kiszolgálás a teljes igény kiszolgálásáig tart. Prioritásos rendszerek: Ezekben a rendszerekben az igényeket különböz½o véges M számú osztályba soroljuk. A rendszerbe lép½o minden egyes igény egy, a típusának (osztályának) megfelel½o indexet (számot), un. prioritási indexet kap. Az igény prioritása akkor nagyobb, amikor a prioritási indexe nagyobb. A sorbanálló igények közül mindig a magasabb prioritású igény kerül kiszolgálásra akkor, amikor a kiszolgáló egység felszabadul. Azonos típusú (prioritású) igények közül a választás a fenti elvek valamelyike szerint történhet. Az osztályba sorolás és a prioritások hozzárendelése az egyes osztályokhoz egyfajta eszközt jelent a rendszer hatékonyságának optimalizálására. Abszolut prioritásos rendszerek: Ha egy igény kiszolgálási ideje alatt egy magasabb prioritású igény érkezik a rendszerbe, akkor a kiszolgálás alatt lév½o alacsonyabb prioritású igény kiszolgálása azonnal befejez½odik (visszakerül a sorba) és a kiszolgáló egység a magasabb prioritású igény kiszolgálását kezdi meg. Relatív prioritásos rendszerek: A különbség az el½oz½o kiszolgálási elv és eközött abban van, hogy ha egy igény kiszolgálási ideje alatt egy magasabb prioritású igény érkezik a rendszerbe, akkor az új igény kiszolgálása csak azután kezd½odik meg, hogy a kiszolgálás megtörtént a kiszolgáló egységen. Id½oosztásos kiszolgálási algoritmus: széles körben elterjedt a nagy teljesítmény½u és nagy forgalmú kiszolgáló egységeken történ½o kiszolgálás szabályozására. Igazi jelent½oséget el½oször a nagy teljesítmény½u multiprogramozású számítógépeknél nyert, de alapvet½o szerepet játszik a modern telekommunikációs rendszerekben is. Ebben az esetben egy igény egyszerre 9
csak rész-kiszolgálást nyer és utána visszakerül a várakozási sorba, a kiszolgáló egység és a várakozási sor között egyfajta visszacsatolás van.
Az egyszer½u GjGj1 tömegkiszolgálási rendszer matematikai leírása a FCFS kiszolgálási elv mellett.
A rendszert a t0 = 0 id½opontban kezdjük vizsgálni és az egyszer½uség kedvéért feltesszük, hogy a rendszer üres a kezd½opontban, azaz L(0) = 0 és a sorhosszússzúságot leíró L(t).folyamat jóbbról folytonos. Az igények a rendszerbe az egymás utáni t1 = X1 ; t2 = X1 + X2 ; ::: id½opontokban érkeznek és a ti = X1 + ::: + Xi ; i = 1; 2; : : : id½opontban beérkez½o i. igény kiszolgálási idejét Yi jelöli. Világos, hogy Xi = ti
ti
1;
i = 1; 2; : : :
Ekkor, ha ismert a rendszer (Xi ; Yi ); i = 1; 2; : : : un. meghatározó sorozata, akkor ez a sorozat tetsz½oleges t 0 id½opontban meghatározza a rendszer állapotát és a feladat az, hogy kiindulva az (Xi ; Yi ); i = 1; 2; : : : sorozatból, eljárást adjunk a rendszer különböz½o jellemz½oinek meghatározására tetsz½oleges t id½opontban. Feltesszük a továbbiakban, hogy minden Xi és Yi pozitív mennyiség. Jelölje s1 ; s2 ; : : : az egymás után a rendszerbe érkez½o igények távozási id½opontjait, vagyis azokat az id½opontokat, amikor az igények kiszolgálása befejez½odött a rendszerben. Meg kell jegyezni, hogy a távozási id½opontokra, melyek a beérkezési id½opontokon kívül az egyes kiszolgálási id½okt½ol és a rendszer összes tulajdonságától függhetnek, általában nem adható a beérkezési id½opontokhoz hasonló egyszer½u formula. Ha adott a rendszer (Xi ; Yi ); i = 1; 2; : : : meghatározó sorozata, akkor tetsz½oleges t > 0 esetén a [0; t) id½ointervallumban beérkez½o igények, illetve onnan távozó igények száma megadható a K = maxfk : tk < tg; K 0 = maxfk : sk < tg; mennyiséggel. Ez azt jelenti, hogy az adott esetben a rendszer viselkedése leírható a meghatározó sorozat els½o K elemével, vagyis az (Xi ; Yi ); i = 1; 2; : : : ; K elemekkel. Minthogy a rendszerben állapotváltozás csak azokban az id½opontokban következik be (a rendszerben tartózkodó igények száma 1-gyel n½o, vagy csökken), amikor vagy beérkezik egy új igény a rendszerbe, vagy távozik egy már kiszolgált igény a rendszerb½ol, ezért viszonylag egyszer½u algoritmussal megadható nem csak az igények ti ; i = 1; 2; :::K beérkezési, hanem az si ; i = 1; 2; :::; K 0 távozási id½opontjai, melyek teljes mértékben meghatározzák a rendszer viselkedését a [0; t) id½ointervallumon, és így az L(t) sorhosszúságot is. Jelölje N (t), illetve M (t) a t (t 0) id½opontig a rendszerbe érkez½o K, illetve onnan eltávozott K 0 igények számát, ekkor ati ; i = 1; 2; :::K; illetve si ; i = 1; 2; :::; K 0 felhasználásával
10
kapjuk N (t) =
1 X
I(tk < t); M (t) =
k=1
és innen
1 X
I(sk < t)
k=1
L(t) = N (t)
M (t):
Összetettebb rendszer esetén (pl. többcsatornás, többféle igényt esetleg más kiszolgálási algoritmussal kiszolgáló rendszer) a rendszert csak több paraméter egyidej½u meghatározásával adhatjuk meg. Ennek megfelel½oen a rendszer jellemz½oinek leírása is lényegesen bonyolultabb eljáráshoz vezethet. Sokszor könnyebben levezethet½o eljáráshoz jutunk, ha a további vizsgálatok számára elegend½o speciális id½opontokban tekinteni a rendszert, mint pl. az igények beérkezési, vagy távozási id½opontjaiban. Tekintsük a GjGj1 rendszert. Jelölje sn továbbra is azt az id½opontot, amikor az n-ik igény kiszolgálása befejez½odik és legyen Ln = L(sn ); n 1. Jelölje Zn azon igények számát, amelyek az n-ik igény Yn kiszolgálási ideje alatt lépnek be a rendszerbe, azaz Zn = N (sn ) N (sn Yn ); n 1. Ekkor az Ln ; n = 1; 2; ::: sorozatra érvényes a következ½o rekurrens szabály (ez a sorozat redelkezik a kés½obbiekben bevezetend½o un. Markov-tulajdonsággal): Ln = I(Ln
1
> 0)(Ln
1
1) + Zn = (Ln
1
1)+ + Zn :
Megjegyzés 4 A kés½obbiek során (ld. 9. és 10. Téma) az MjMj1 és MjGj1 rendszerekre belátjuk, hogy a sorhosszúságnak létezik 1 valószín½uséggel határeloszlása, ha a n-nel tartunk a végtelenhez.
11
Téma 3
Tömegkiszolgálási rendszerek min½oségi mutatói Várakozási id½o, foglaltsági/szabad intervallum és sorhosszúság eloszlása. Littleformula. Minden TKR esetén meg kell határozni azokat a min½oségi mutatókat, amelyek alapján megítélhet½o a rendszer m½uködésének hatékonysága és amelyek alapján optimálisan megválaszthatók a rendszer paraméterei. Az alábbiakban megadunk néhány tipikus min½oségi mutatót. 1. Az igény elvesztésének a valószín½usége (veszteséges, vagy elutasításos rendszerekben). Jelölje az egymásutáni sorrendben beérkez½o igények beérkezési id½opontjait 0 t1 t2 ::: és mn jelentse azt a számot, amely megmutatja, hogy az els½o n darab beérkez½o igény közül a rendszer hányat utasít vissza. Ha fennáll az mn =n ! q; n ! 1 sztochasztikus konvergencia, akkor a q számot az igény elvesztése valószín½uségének nevezzük. Az elutasításos rendszerekben természetesen fontos kérdés annak vizsgálata, hogy egyáltalán létezik-e ilyen q szám. 2. Az igény várakozásának eloszlása. Legyen Wn ; n 1 az n-ik igény várakozási ideje. Jelölje n 1X Fn (x) = I(Wi < x); x > 0: n i=1
Fn (x) jelenti az x-nél kevesebb ideig várakozó igények átlagos számát az els½o n meg…gyelt igény alapján, vagyis az igények várakozási idejének empírikus eloszlásfüggvényét. Ha minden x > 0 és n ! 1 mellett Fn (x) sztochasztikusan konvergál az F (x) eloszlásfüggvényhez, akkor F (x)-t a várakozási id½o eloszlásának nevezzük. 3. Átlagos várakozási id½o. Ha 1 (W1 + ::: + Wn ) ! W (1) ; n
n!1
sztochasztikusan, akkor W (1) -t átlagos várakozási id½onek nevezzük. Hasonlóan (sztochasztikus konvergenciával) értelmezhet½ok az átlagos k-adrend½u momentumok: 1 (W1k + ::: + Wnk ); n!1 n
W (k) = lim
12
k
1:
Megjegyezzük, hogy elég általános feltételek mellett érvényes a W
(k)
=
Z1
xk dF (x);
k
1
0
összefüggés. 4. Foglaltsági intervallum (vagy periodus) eloszlása. Tekintsünk egy TKR-t, amelyben az igényeket kiszolgáló egységek közül válasszunk ki egyet (ha több is van). Jelölje [an ; bn ); n 1 azokat az egymásutáni id½ointervallumokat, amikor a kiszolgálóegység foglalt (éppen kiszolgálást végez) és [bn ; an+1 ) pedig azokat, amikor szabad (an < bn < an+1 ; n 1). Ekkor az [an ; bn ) intervallumot az n-ik foglaltsági intervallumnak nevezzük (a megadott kiszolgálóegységre nézve). Ha létezik sztochasztikusan a n
1X I(bi lim n!1 n
ai < x) = F (x);
x>0
i=1
konvergencia, akkor az F (x) függvényt a foglaltsági intervallum eloszlásának nevezzük. Analóg módon értelmezhet½o a [bn ; an+1 ); n 1 szabad intervallumokra vonatkozó eloszlás, továbbá a magasabbrend½u momentumok fogalma is. 5. A sorhosszúság eloszlása. Sorhosszúság alatt (adott kiszolgálóegységre, vagy azok egy csoportjára nézve) a rendszerben tartózkodó igények számát értjük. Ebben természetesen benne foglaltatnak az éppen kiszolgálás alatt lévõ igények is. Jelölje L(t); t 0 a sorhosszúságot a t id½opillanatban és tekintsük az 1 Lk (t) = t
Zt
I(L(s) = k)ds
0
mennyiséget. Jelentése: a [0; t] id½ointervallumnak az a hányada, ahol a sorhosszúság éppen k. Ha léteznek pk = lim Lk (t); k = 0; 1; ::: t!1
határértékek sztochasztikusan és
1 P
pk = 1, akkor ezt a sorhosszúság eloszlásának nevez-
k=0
zük. A korábbiakhoz hasonló módon de…niálható a sorhosszúság várható értéke és magasabbrend½u momentumai, további fontos mutatóval együtt. Megjegyzés. Ha a rendszer m½uködése leírható diszkrét X = fig állapotter½u (t); t 0 homogén ergodikus Markov-lánccal, f (i); i 2 X pedig tetsz½oleges korlátos függvény, akkor létezik az Zt 1 f ( (s))ds f = lim t!1 t 0
13
határérték és fennáll f=
X
f (i) i ;
i2X
ahol f i ; i 2 X g jelenti a f (t); t 0g Markov-lánc ergodikus eloszlását, amely az adott esetben egyértelm½uen meghatározható a Markov-lánc átmenetvalószín½uségi mátrixából és nem függ a Markov-lánc kezdeti eloszlásától.
Little-formula A Little-formula általános TKR-ek esetén a különböz½o min½oségi mutatók között határoz meg összefüggéseket. A formula felírásához vezessük be a következ½o jelöléseket az adott TKR egészére, vagy annak valamely részrendszerére vonatkozóan: N (t); t száma),
0 - beérkezési folyamat (a [0; t) id½ointervallumon a rendszerbe érkez½o igények
M (t); t
0 - távozási folyamat (a t id½opont el½ott a rendszerb½ol eltávozott igények száma),
L(t) = N (t) M (t); t 0 - sorhosszúság a t id½opontban, Rt L(t) = 1t L(s)ds; t > 0 - a [0; t) id½ointervallumon a rendszerben tartózkodó igények 0
átlagos száma, (t) =
N (t) t ;
t > 0 - átlagos beérkezési intenzitás a [0; t) id½ointervallumon,
t > 0 - az a [0; t) id½ointervallumba es½o id½omennyiség, melyet az n-ik igény eltöltött a rendszerben, P (t) = n (t); t > 0 - az összes id½omennyiség, melyet a t id½opontig beérkezett igények n (t);
n
eltöltenek a rendszerben a [0; t) id½ointervallumon,
T (t) = N(t) (t) ; t > 0 - egy igényre es½o átlagos rendszerben eltöltött id½o, a [0; t) id½ointervallumon beérkez½o összes igényre nézve.
Megjegyzés 5 Világos, hogy (t) =
Zt
[N (s)
M (s)]ds =
0
Zt
L(s)ds; t
0;
0
(t) L(t) = ; t > 0: t TKR-k vizsgálatánál gyakran az a cél, hogy meghatározzuk a fenti min½oségi mutatók id½ofügg½o, és (vagy) stacionárius eloszlását, illetve átlagos mennyiségek esetén azokat az értékeket, amelyekhez sztochasztikusan konvergálnak. A következ½o tétel az utóbbi számértékek között mond ki általános összefüggést.
14
Tétel 1 (Little) Tegyük fel, hogy fennállnak a következ½o sztochasztikus konvergenciák: N (t) = ; > 0; t!1 t!1 t Zt 1 lim L(t) = lim L(s)ds = L: t!1 t!1 t lim (t) = lim
0
Akkor létezik a limt!1 T (t) = T határérték sztochasztikusan és érvényes az L= T összefüggés. Bizonyítás. Egyszer½uen látható, hogy fennáll a következ½o sztochasztikus konvergencia: (t) (t)=t L(t) = lim = lim = T; t!1 N (t) t!1 N (t)=t t!1 (t)
lim T (t) = lim
t!1
ahonnan a feltevéseink alapján már közvetlenül adódik a tétel állítása. Megjegyzés 6 A tételben szerepl½o L = T összefüggést Little-formulának szokás nevezni. A Little-formula tapasztalati szabályként már régóta ismert volt, formálisan azonban Little (1961) igazolta el½oször Azt az összefüggést mondja ki, hogy a rendszerben tartózkodó igények átlagos száma = = beérkezési intezitás * egy igény által a rendszerben eltöltött átlagos id½o függetlenül attól, hogy hogyan de…niáltuk a rendszert, milyenek a beérkezési és kiszolgálá-si id½ok eloszlásai, s a kiszolgálási egységek számára sem kötünk meg semmit. Következményként megemlítjük az alábbi analógiákat: a) Ha csak a várakozóhelyek vizsgálatára szorítkozunk, akkor ebben az esetben azt kapjuk, hogy Lv = W; ahol Lv - várakozó igények átlagos száma, W - átlagos várakozási id½o. b) Ha csak a kiszolgálóegységeket vesszük szemügyre (több kiszolgálóegység esetén), akkor a következ½o azonossághoz jutunk Lk = Y ahol Lk - foglalt kiszolgálóegységek átlagos száma, Y - egy igény átlagos kiszolgálási ideje.
15
Téma 4
Sztochasztikus folyamatok általános fogalma. Poisson-folyamat. Poisson-folyamatok. Homogén Poisson-folyamat. Poisson-folyamatok konstrukciója. Homogén Poisson-folyamatok néhány fontos tulajdonsága: ritkasági feltétel. Számos m½uszaki, …zikai, közgazdasági,... stb. feladat esetén felmerül az a probléma, hogy a vizsgálat számára fontos és meghatározó valamilyen fXt ; t 2 T g (vagy más, gyakran alkalmazott jelölés mellett fX(t); t 2 T g) menynyiségek véletlen jelleget öltenek. Ezek a mennyiségek leggyakrabban adott objektumra vonatkozó adatok id½obeli, vagy térbeli (esetleg a kett½o együtt) változását írják le. Ezeknek a feladatoknak a matematikai modellezése során természetes módon merül fel az a gondolat, hogy a vizsgált fXt ; t 2 T g mennyiségeket, mint a T paraméterhez tartozó valószín½uségi változók együttesét értelmezzük, s amelyek valamilyen, egy és ugyanazon valószín½uségi mez½on vannak értelmezve. Ha a T paraméterhalmaz része a valós számegyenesnek, akkor a ft 2 T g halmaz felfogható id½oparaméterként is, és ebben az esetben az fXt ; t 2 T g valószín½uségi változók együttesét - a valószín½uségelméletben megszokott módon - sztochasztikus folyamatnak szokás nevezni. Ha a T paraméterhalmaz nem rendezhet½o nagyság szerinti sorrendbe, akkor a szokásos elnevezése véletlen függvény. Utóbbira egyszer½u példaként megemlíthetjük azt az esetet, amikor az adott objektumra vonatkozó véletlen mennyiségnek a térbeli helyzetét½ol való függését írjuk le egy adott térrészben, vagyis amikor a paraméterhalmaz pontjai a háromdimenziós valós euklideszi tér valamilyen részhalmaza. További elnevezések is ismertek. Aszerint, hogy a halmaz véges, vagy megszámlálhatóan végtelen, az sztochasztikus folyamatot diszkrét idej½u (paraméter½u), míg ha a halmaz a valós számegyenes véges, vagy végtelen részintervalluma, folytonos idej½u (paraméter½u) sztochasztikus folyamatnak nevezzük. A legfontosab példák a diszkrét, illetve folytonos idej½u esetekre: T = f1; 2; :::; N g, f1; 2; :::g, f:::; 1; 0; 1; :::g, fa t bg (a < b), f0 t < 1g és f 1 < t < 1g. Az elmondottak alapján tehát sztochasztikus folyamat alatt olyan véletlen jelleg½u, id½oben lejátszódó jelenségeket értünk, amelyeknek tetsz½oleges, a T paraméterhalmazhoz tartozó id½opontokban felvett értékei valószín½uségi változók. Attól függ½oen, hogy ezek a valószín½uségi változók milyen értékeket vehetnek fel, beszélhetünk valós érték½u, komplex érték½u, vagy 16
éppen többdimenziós sztochasztikus folyamatokról. Általában, ha kiegészít½o jelz½ot nem említünk, akkor valós érték½u sztochasztikus folyamatokról van szó. Egy tetsz½oleges fXt ; t 2 T g folyamat realizációi (trajektóriái) alatt az adott folyamat lehetséges megvalósulásait, kimeneteleit értjük, vagyis mindazon fXt ; t 2 T g függvényeket, melyeket egy kisérlet, vagy meg…gyelés során a folyamat eredményezhet. Megjegyezzük, hogy a diszkrét idej½u folyamatok esetén a realizációk a folyamat által meghatározott lehetséges (véges, vagy végtelen) számsorozatokat jelentik. Sztochasztikus folyamat végesdimenziós eloszlásai Tetsz½oleges fXt ; t 2 T g sztochasztikus folyamatot statisztikai értelemben a folyamat lehetséges végesdimenziós eloszlásai jellemzik, amely fogalom alatt azt értjük, hogy vesszük tetsz½oleges pozitív egész n és tetsz½oleges t1 ; :::; tn 2 T mellett az Xt1 ; :::; Xtn valószín½uségi változók Ft1 ;:::;tn (x1 ; :::; xn ) = P (Xt1 < x1 ; :::; Xtn < xn ): együttes eloszlásait. (a) A most bevezetett együttes eloszlásfüggvények F = fFt1 ;:::;tn ; t1 ; :::; tn 2 T ; n = 1; 2; :::g családja nyilvánvalóan rendelkezik az un. kompatibilitási feltételekkel: (b) Tetsz½oleges pozitív egész n és m szám, valamint t1 ; :::; tn+m 2 T esetén fennáll
Ft1 ;:::;tn ;tn+1 ;:::;tn+m (x1 ; :::; xn ; +1; :::; +1)) = Ft1 ;:::;tn (x1 ; :::; xn ); x1 ; :::; xn 2 R (c) Az 1,2,...,n számok tetsz½oleges i1 ; :::; in permutációjára az sj = tij ; j = 1; :::; n jelölés mellett fennáll
Fs1 ;:::;sn (xi1 ; :::; xin ) = Ft1 ;:::;tn (x1 ; :::; xn ); x1 ; :::; xn 2 R Gyakran el½ofordul, hogy vizsgálatainkhoz teljes mértékben elegend½o csupán megadni a folyamat végesdimenziós eloszlásait; ebben az esetben azt mondjuk, hogy a folyamat gyenge értelemben adott és ekkor természetesen teljesen mindegy, hogy milyen valószín½uségi mez½ot képzelünk mögé. Némely esetben fontos lehet a realizációk konkrét tulajdonsága is (pl. folytonosság), mely összefügghet azzal a valószín½uségi mez½ovel, amelyen értelmezve van a folyamat. Ha adva van az ( ; A; P ) valószín½uségi mez½o és rajta az fXt ; t 2 T g sztochasztikus folyamat, akkor azt mondjuk, hogy a sztochasztikus folyamat er½os értelemben adott. 17
Stacionárius folyamatok. Az id½oben véletlenszer½uen változó sztochasztikus folyamatok között a gyakorlat számára különös jelent½oséggel bírnak azok, melyeknek bizonyos jellemz½oi az id½o folyamán egyfajta állandóságot, stacionaritást mutatnak. Ezek közül a legfontosabbak a sz½ukebb, illetve tágabb értelemben stacionárius folyamatok. De…níció 2 Egy fXt ; t 2 T g sztochasztikus folyamatot sz½ukebb értelemben stacionáriusnak nevezünk, ha végesdimenziós eloszlásai az id½oeltolással szemben invariánsak, azaz tetsz½oleges pozitív egész n és minden olyan t; t1 ; :::; tn 2 T értékekre, melyekre teljesül ti + t 2 T ; i = 1; :::; n, az (Xt1 ; :::; Xtn ) és az (Xt1+t ; :::; Xtn +t ) valószín½uségi változók együttes eloszlása megegyezik. Világos, hogy ez a de…níció egyaránt érvényes mind az egy-, mind pedig a többdimenziós sztochasztikus folyamatok esetén. Legyen most az fXt ; t 2 T g sztochasztikus folyamat második momentuma véges minden t 2 T -re, azaz EXt2 < 1 és jelölje a várható érték- és kovarianciafüggvényét X (t)
= EXt ; t 2 T ; RX (s; t) = cov(Xs ; Xt ) = = E(Xt X (t))(Xs
X (s));
s; t 2 T
Az alapvet½o fogalmakat ezen a helyen csak egydimenziós valós érték½u folyamatokra adtuk meg, az egydimenziós folyamatokra bevezetett fogalmak minden nehézség nélkül átvihet½ok a többdimenziós esetre is. Megjegyezzük még, hogy létezik még egy általánosan használt stacionaritási fogalom, az un. gyenge értelemben vett stacionaritás. De…níció 3 Ha az sztochasztikus folyamat második momentuma véges minden t-re és a és a RX (s; t) kovarianciafüggvényére teljesül a
X (t)
várható érték-
X (t)
= X; t 2 T ; RX (s; t) = RX (t s); s; t 2 T ; összefüggés akkor azt mondjuk, hogy az X folyamat tágabb értelemben stacionárius, vagy stacionárius. Az RX függvényt az X sztochasztikus folyamat auto-kovariancia függvényének nevezzük. Stacionárius folyamatokra az RX (t) kovarianciafüggvényen kívül használatos még a folyamat szórásnégyzetével normált rX (t) =
1 1 RX (t) = 2 RX (t) RX (0) X
autokorrelációs függvény is.
Független növekmény½u folyamatok. Bizonyos …zikai folyamatok modellezésénél, de más gyakorlati feladatoknál is alapvet½o szerepet játszanak a független növekmény½u folyamatok. Ha az X = fXt ; t 2 T g folyamat olyan, hogy tetsz½oleges n 1; t0 ; :::; tn 2 T ; t0 < ::: < tn esetén az Xt1
Xt0 ; :::; Xtn 18
Xtn
1
valószín½uségi változók, mint az X folyamat növekményei függetlenek, akkor azt mondjuk, hogy X független növekmény½u folyamat. Poisson-folyamat. A független növekmény½u folyamatok fontos speciális esetét képezi a Poisson-folyamat. Ez a folyamat nem csak a tömegkiszolgálás elméletében játszik alapvet½o szerepet, hanem számos más alkalmazási területen (pl. kvantumoptikai, ökológiai, stb.) jut meghatározó szerephez. Meg kell jegyezni azt is, hogy a Poisson-folyamat több helyen merül fel a könyvben: a folytonos idej½u Markov-láncok között a tiszta születési folyamatként, a felújítás elméletben felújítási folyamatként is jellemezni fogjuk. De…níció 4 Az fN (t); t 0g nemnegatív egész értékeket felvev½o, balról folytonos sztochasztikus folyamatot ( > 0) paraméter½u (homogén) Poisson-folyamatnak nevezzük, ha 1. N (0) = 0; 2. N (t) független növekmény½u folyamat, 3. Tetsz½oleges 0 s t esetén N (t) N (s) eloszlása (t s) paraméter½u Poisson, azaz P (N (t)
N (s) = k) =
s)]k
[ (t k!
e
(t s)
; k = 0; 1; :::
A de…níció szerint az N (t); t 0; N (0) = 0 Poisson-folyamat olyan balról folytonos független növekmény½u lépcs½os-folyamat, melynek minden N (t) N (s); 0 s < t növekménye csak nemnegatív egész értékeket vehet fel és a növekmény eloszlása (t s) paraméter½u Poisson. Poisson-folyamatok általános fogalma. Legyen f (t); t
0g nemnegatív, monoton nemcsökken½o, balról folytonos függvény, melyre
(0) = 0.
De…níció 5 Az fN (t); t 0g nemnegatív egész értékeket felvev½o, balról folytonos sztochasztikus folyamatot (t) várható érték-függvény½u Poisson-folyamatnak nevezzük, ha 1. N (0) = 0; 2. N (t) független növekmény½u folyamat, 3. Tetsz½oleges 0 s t esetén N (t) N (s) eloszlása (t) (s) paraméter½u Poisson, azaz P (N (t)
N (s) = k) =
(s))k
( (t) k!
e
( (t)
(s))
; k = 0; 1; :::
Az N (t); t 0; N (0) = 0 folyamat tehát olyan balról folytonos lépcs½os-folyamat, melynek minden N (t) N (s); 0 s < t növekménye csak nemnegatív egész értékeket vehet fel és a növekmény eloszlása ( (t) (s)) paraméter½u Poisson. Azt is megjegyezzük, hogy a független növekmény½uség felhasználásával egyszer½uen nyerhet½o tetsz½oleges pozitív egész n és 0 < t1 < ::: < tn esetén az N (t1 ); :::; N (tn ) v.v.-k együttes eloszlása, ugyanis tetsz½oleges 0 k1 ::: kn egész számok mellett fennáll P (N (t1 ) = k1 ; :::; N (tn ) = kn ) = = P (N (t1 ) = k1 ; N (t2 ) N (t1 ) = k2 k1 ; :::; N (tn ) N (tn n Y ( (t1 ))k1 ( (ti ) (ti 1 ))k ( (ti ) (ti 1 )) e (t1 ) e = k1 ! (ki ki 1 )! i=2 19
1)
= kn
kn
1)
=
A (t) = EN (t) várható érték-függvény monoton növ½o, ezért a szakadási pontjainak f n g halmaza legfeljebb megszámlálható. Itt meg kell jegyezni, hogy a (t) függvény szakadási pontjainak f n g halmaza bár megszámlálható, azonban mivel több torlódási pontja is lehet, ezért nem feltétlenül adható meg monoton növ½o 1 < 2 < ::: sorozatként. Vezessük be a következ½o jelölést n
= (
n
+ 0)
(
n
0) = (
+ 0)
n
(
n ):
Ekkor könnyen megmutatható a független növekmény½uség felhasználásával (Khinchin-féle felbontás), hogy N (t) = Nr (t) + Ns (t); ahol Nr (t) és Ns (t) független Poisson-folyamatok X r (t) = (t) n;
illetve
s (t)
n
=
X
n
n
várható érték-függvénnyel. Az Nr (t) un. reguláris Poisson-folyamatnak nincs olyan ugrása, amely különbözne 1-t½ol, várható értékfüggvénye folytonos, így Nr (t) sztochasztikusan folytonos. Megjegyezzük, hogy az utóbbi tulajdonsággal is szokás a reguláris Poisson-folyamatot de…niálni. Az Ns (t) un. szinguláris Poisson-folyamatnak az ugrásai csak a rögzített f n g helyeken lehetnek, emellett De…níció 6 Ha az fN (t); t 0g Poisson-folyamat (t) várható érték-függvénye di¤ erenciálható függvény Rt (0-ban jobboldali di¤ erenciálhányadost véve) és (t) = 0 (s)ds, akkor a (t) függvényt az fN (t); t 0g Poisson-folyamat intenzitásfüggvényének nevezzük. Az N (t) Poisson-folyamat homogén, ha intenzitásfüggvénye (t) = ; t 0 konstans. Megjegyezzük, hogy ha (t) = t; t 0, akkor N (t) eloszlása t paraméter½u Poisson. Ebben az esetben EN (t) = t, vagyis az egységnyi id½ore jutó beérkezések átlagos száma és ez teszi indokolttá azt, hogy -t intenzitásnak, az N (t) folyamatot pedig intenzitású homogén Poisson-folyamatnak nevezzük.
Poisson-folyamatok konstrukciója Poisson-folyamatok konstruktív megadása fontos szerepet játszik mind az elmélet, mind pedig a gyakorlat (szimulációs módszerek alkalmazása) szemsz½ogéb½ol. A következ½o két konstrukciót adjuk meg bizonyítás nélkül: Tétel 2 (1. konstrukció) Legyen X1 ; X2 ; ::: független 1 paraméter½u exponenciális eloszlású valószín½uségi változók sorozata. Vezessük be N (t) =
1 X
I(X1 + ::: + Xm < t); t
0
m=1
sztochasztikus folyamatot. Ekkor N (t) homogén 1 intenzitású Poisson-folyamat. Tétel 3 (2. konstrukció) Legyen U1 ; U2 ; ::: független, a (0; T ) intervallumon egyenletes eloszlású v.v.-k sorozata és legyen N ezekt½ol független T paraméter½u Poisson-eloszlású v.v. Jelölje N (t) =
N X
I(Um < t); 0
t
T:
m=1
Ekkor N (t) homogén
intenzitású Poisson-folyamat a [0; T ] intervallumon.
20
Homogén Poisson-folyamatok néhány fontos tulajdonsága. A továbbiakban felsoroljuk a homogén Poisson-folyamatok néhány alapvet½o tulajdonságát. (a) Minden t
0 mellett az N (t) v.v. eloszlása t paraméter½u Poisson, azaz ( t)k P (N (t) = k) = e k!
t
; k = 0; 1; :::
(b) N (t) független, stacionárius növekmény½u folyamat. (c) Két független N1 (t; Poisson-folyamat.
1)
és N2 (t;
2)
Poisson-folyamat összege (
1
+
2)
paraméter½u
(d) Teljesülnek az alábbi aszimptotikus összefüggések h ! +0 mellett P (N (h) = 0) = 1
h + o(h);
P (N (h) = 1) = h + o(h) (s½ur½uségi feltétel), P (N (h)
2) = o(h); h ! +0 (ritkasági feltétel).
Lemma 1 Tetsz½oleges m pozitív egész szám mellett aszimptotikusan igaz ex
m xk P = o(xm ); x ! 0: k=0 k!
Bizonyítás. Az ex függvény Taylor-sorát használva kapjuk ex = így x ! 0 mellett
m xk 1 m xk 1 xk P P P xm+1 P (m + 1)! xk + = + ; (m + 1)! k=0 k! (m + 1 + k)! k=0 k! k=m+1 k! k=0 k!
m+1 1 P jxjk jxj 1 < (m + 1)! k=0 k! (m + 1 + 1):::(m + 1 + k)
m xk P k=0 k!
ex
m+1
<
jxj ejxj = o(xm ): (m + 1)!
Bizonyítás. A (d) összefüggéseinek a bizonyítása. Az el½oz½o Lemma felhasználásával kapjuk h
P (N (h) = 0) = e P (N (h) = 1) = P (N (h)
h 1! e
2) = 1
h
h
e
=1
(1
h + o(h);
h + o(h)) = h + o(h), i h)1 h + ( 1! e h = e h 1
h = o(h); h ! +0
(f) Utóhatásmentesség: Legyen fN (t); t 0g intenzitású Poisson-folyamat, továbbá tetsz½oleges 0 mellett legyen N (t) At -mérhet½o, ahol At A; t 0 monoton b½ovül½o -algebrák családja. Legyen olyan valószín½uségi változó, hogy minden t 0 mellett teljesül f tg 2 At Az ilyen valószín½uségi változókat nevezzük Markov-pontnak (Például, tetsz½oleges konstans id½opont mindig Markov-pont, de a = inf fs : N (s) kg ; k 0: un. els½o elérési pont is az.) Jelölje N (t) = N (t + ) N ( ); t 0 Ekkor N (t); t 0 szintén intenzitású Poisson-folyamat, amely független a Markov-ponttól és az fN (t); 0 t g értékekt½ol.
t
21
(g) Általános Poisson-folyamat el½oállítása 1 intenzitású homogén Poisson-folyamattal. Legyen f (t); t 0g nemnegatív, monoton nemcsökken½o, balról folytonos függvény, melyre (0) = 0; továbbá legyen N (t); t 0 pedig 1 intenzitású homogén Poisson-folyamat. Ekkor az N (t) = N ( (t)); t
0
egyenlettel de…niált folyamat Poisson-folyamat (t); t 0 várható érték függvénnyel. Bizonyítás. Világos, hogy N (0) = 0; N (t) független növekmény½u, továbbá tetsz½oleges 0 N (t) N (s) eloszlása (t) (s) paraméter½u Poisson, azaz P (N (t)
N (s) = k) = P (N ( (t)) =
k
( (t)
(s)) k!
22
e
N ( (s)) = ( (t)
(s))
; k = 0; 1; :::
s
t esetén
Téma 5
Felújítási- és regeneratív folyamatok Felújítási folyamat, késleltetett felújítási folyamat, felújítási függvény, elemi felújítási tétel. A felújítási folyamatokra vonatkozó nagy számok törvénye és centrális határeloszlás tétel. Regeneratív folyamatok, regenerációs pontok, ciklusok. Jelentsen fN (t); t 0g nemnegatív egész értékeket felvev½o sztochasztikus folyamatot, amely egy esemény egymás utáni bekövetkezéseit regisztrálja a [0; t) id½ointervallumon (pl. egy folytonosan ég½o lámpában az izzócserék száma - egyfajta izzót használunk és az izzót azonnal kicseréljük, ha kiégett). Jelölje 0 t1 t2 ::: a meg…gyelt események egymás utáni bekövetkezési id½opontjait és legyen t0 = 0. Feltesszük, hogy a bekövetkezési id½opontok között eltelt Ti = ti ti 1 , i = 1; 2; ::: id½otartamok, mint valószín½uségi változók függetlenek és azonos eloszlásúak, közös F (x) = P (Tk < x); k = 1; 2; ::: eloszlásfüggvénnyel. F (x)-r½ol feltesszük, hogy F (0) = 0 és F (0+) = P (Tk = 0) < 1 . Ekkor írhatjuk, hogy t0 = 0; tn = T1 + ::: + Tn ; N (0) = 0;
n = 1; 2; :::;
N (t) = supfn : tn < t; n
0g =
1 X
I(ti < t); t > 0:
i=1
(Emlékeztet½oül: I(ti < t) = 1, ha a ti < t feltétel teljesül, egyébként 1 az értéke.) De…níció 7 Az fN (t); t 0g és a ftn ; n 1g folyamatokat egyaránt szokás felújítási folyamatoknak nevezni (az elnevezés nem egyértelm½u). A tn ; n = 1; 2; ::: id½opontokat az n-ik felújítási id½opontnak, vagy az n-ik esemény bekövetkezéséhez szükséges várakozási id½onek nevezzük. Megjegyzés 7 Az fN (t); t 0g és ftn ; n 1g folyamatok kölcsönösen egyértelm½uen meghatározzák egymást, ugyanis tetsz½oleges t 0 és k 1 egész mellett fennáll N (t)
k
,
23
tk < t:
(5.1)
De…níció 8 El½ofordulhat, hogy csak a P (Tk < x) = F (x); k = 2; 3; ::: azonosság áll fenn és az F1 (x) = P (T1 < x) eloszlásfüggvényre F1 6= F . Ebben az esetben késleltetett felújítási folyamatról beszélünk. Megjegyzés 8 Mivel T1 ; T2 ; ::: független azonos eloszlású v.v.-k, ezért a tn összeg F (n) (x) = P (tn < x) eloszlásfüggvényét a konvolúciós formula segítségével írhatjuk fel: ha x 0 és n 1; akkor F (n) (x) = 0; ha x
0 és n
1;
ha n 2; és x 0; akkor folytonos f (x) s½ur½uségfüggvénnyel rendelkez½o F eloszlásfüggvény esetén F (n) (x) s½ur½uségfüggvényére fennáll f (n) (x) =
Z1
f (n
1)
(x
y)f (y)dy =
1
Zx
f (n
1)
(x
y)f (y)dy:
0
Általános esetben a következ½o konvolúciós formula érvényes F (n) (x) =
Z1
F (n
1)
(x
y)dF (y) =
1
Zx
F (n
1)
(x
y)dF (y):
0
Világos, hogy ez az összefüggés érvényes a késleltetett esetben is. De…níció 9 A H(t) = EN (t); t
0 függvényt felújítási függvénynek nevezzük.
A felújításelmélet alapvet½o feladata a H(t) felújítási függvény vizsgálata, aszimptotikus viselkedésének leírása. Ezzel a feladattal önállóan foglalkozunk a továbbiakban. Ezenkívül bebizonyítjuk, hogy az N (t) a felújítási folyamatra érvényes a nagy számok törvénye és a centrális határeloszlás tétel. A nyert eredmények könnyen átvihet½ok késleltetett felújítási folyamatokra, ezért ezzel a kérdéssel külön általában nem foglalkozunk. Az N (t) a felújítási folyamat momentumainak vizsgálatához szükségünk van a következ½o lemmára. Lemma 2 Tegyük fel, hogy fTn ; n = 1; 2; :::g független azonos eloszlású v.v.-k sorozata és P (T1 < 0) = 0; P (T1 = 0) < 1. Ekkor létezik olyan 0 > 0 szám, hogy minden t 0 mellett igaz Ee
0 N (t)
< 1:
Tétel 4 Tegyük fel, hogy fTn ; n = 1; 2; :::g független azonos eloszlású v.v.-k sorozata és P (T1 < 0) = 0; P (T1 = 0) < 1. Ekkor N (t) (t 0) tetsz½oleges k-adik momentuma véges, azaz E(N (t))k < 1; k = 1; 2; ::: Bizonyítás. A tétel bizonyításához elegend½o megjegyezni, hogy minden pozitív x-re ex =
1 P
i=1 k 0
k!
E(N (t))k < Ee
0 N (t)
< 1, ahonnan adódik E(N (t))k <
k 0
k!
Ee
0 N (t)
< 1:
Megjegyzés 9 A H(t) felújítási függvényre fennálló H(t) = EN (t) = E
1 X
I(ti < t) =
i=1
1 X i=1
24
P (T1 + ::: + Ti < t)
xk k!
>
xk k! ,
ezért
összefüggés közvetlenül kiadja a H(t) felújítási függvény el½oállítását az F eloszlásfüggvény konvolúcióhatványainak összegeként. 1 X H(t) = F (k) (t): k=1
A felújítási függvény vizsgálata. Minthogy a késleltetett esetben a H1 (t) felújítási függvény megadható az F1 eloszlásfüggvény és a H felújítási függvény segítségével, ezért a továbbiakban csak az utóbbit fogjuk vizsgálni (ekkor Fk = F; k 1). A vizsgálataink során mindig feltesszük az F eloszlásfüggvényrõl, hogy F (0) = 0 és hogy F (0+) < 1 . A felújítási függvényre vonatkozó két fontos tétel bizonyítás nélkül. Tétel 5 (Elemi felújítási tétel) Létezik a 1 H(t) = t!1 t ET1 lim
határérték (1=1 = 0). De…níció 10 Egy X v.v. G eloszlásfüggvényét rácsosnak (vagy aritmetikusnak) nevezzük, ha valamilyen d > 0 és r 2 R mellett az d1 (X r) v.v. csak egész értéket vesz fel, azaz P ( d1 (X r) 2 Z) = 1. A legnagyobb ilyen d számot az eloszlás lépésének nevezzük. Megjegyzés 10 Ha az X v.v. eloszlása rácsos d lépéssel, akkor
iuX
d = minfs : j (2 =s)j = 1g;
ahol a (u) = Ee ; u 2 R függvény az X v.v. karakterisztikus függvényét jelöli. Ekkor j (u)j < 1, ha 0 < juj < 2 =d. Abban az esetben, ha az X v.v. eloszlása nem rácsos, akkor j (u)j < 1; ha u 6= 0.
Tétel 6 (Blackwell-tétel.) Ha az F eloszlásfüggvény rácsos d lépéssel, akkor lim qn =
n!1
d ; ET1
ahol qn = H(nd) H((n 1)d). Ha az F eloszlás nem rácsos, akkor minden h > 0 mellett h lim (H(t + h) H(t)) = : t!1 ET1 Lemma 3 A H függvény monoton nemcsökken½o, balról folytonos. Bizonyítás. Minden F (k) (t); k
1 függvény monoton nemcsökken½o, balról folytonos, a 1 X
F (k) (t)
k=1
sor pedig minden véges intervallumon egyenletesen konvergens. Innen következik, hogy a H függvény monoton nemcsökken½o és balról folytonos.
25
A felújítási folyamatokra vonatkozó nagy számok törvénye és centrális határeloszlás tétel Tétel 7 Legyen 0 < ET1 =
< 1, ekkor fennáll a következ½o sztochasztikus konvergencia N (t) P 1 ! ; t
t ! 1:
Bizonyítás. Az (5.1) összefüggés következményeként az alábbi két esemény megegyezik egymással fN (t) kg = ftk < tg: Becsüljük meg tetszõleges " > 0 szám esetén a P (jN (t)=t n = n(t) = [t= + "t] , ekkor P
N (t) t
1
>"
= P
t
N (t) >
+ "t
1= j >") valószínûséget. Jelölje
P (N (t)
n) =
tn tn t t < P < n [t= + "t] n t= + "t tn 1 tn = P < < P ; n 1= + " 1=t n 1 + "=2 ha t 2=";
= P (tn < t) = P
1
=
ami a tn ; 1; 2; ::: sorozatra fennálló nagy számok Bernoulli törvénye értelmében 0-hoz tart, mid½on t ! 1. A P (N (t)=t 1= < ") valószín½uség becslése analóg módon történik. Megjegyzés 11 A nagy számok er½os törvényéb½ol következik, hogy tkk ! ; k ! 1 fennáll 1 valószín½uséggel. Ennek felhasználásával bizonyítható, hogy 1 valószín½uséggel igaz 1 N (t) ! ; t Tétel 8 Ha ET1 = ; D2 T1 = lim P
t!1
t ! 1:
2
< 1 , akkor t ! 1 mellett ! Zx N (t) t= 1 p < x = (x) = p e 2 t 2= 3
u2 =2
du:
1
Bizonyítás. Az fN (t)
kg = ftk < tg összefüggés következtében P (N (t)
k) = P
tk
p
k k
<
t
p
k k
:
Feltételeink szerint a tk ; k = 1; 2; ::: sorozatra érvényes a centrális határeloszlás tétel, ezért P
tk
p
k k
! (v); k ! 1: (*)
Rögzítsünk egy v értéket és válasszuk meg t ! 1 mellett a k 0 = k 0 (t) függvényt úgy, hogy teljesüljön rá a t
p
k0 =v k0 26
p egyenl½oség. Innen, mivel csak a pozitív gyök felel (mindig fennáll a kapjuk, hogy p p v + v2 2 + 4 t 0 k = 2 és p t v 2 2 + 4 t) v (v 0 k = + : 2 2 Választva a k = [k 0 ] =
v p
t
+4 t > j
j egyenl½otlenség)
1 p t
t 1+O
2
2 2
egész számot t függvényében, (*)-ból kapjuk, hogy P (N (t) A
1 v +O( p ) ! (v); t ! 1: t
N (t) t= p t= 3=2
k) = P
függvény folytonos, ezért P
és így (minden
N (t) t= p > t= 3=2
v
! (v) = 1
( v); t ! 1;
2 R mellett, mivel tetsz½olegesen választható volt) P
N (t) t= p
! (v); t ! 1:
A következ½o eredmény, amely az N (t) felújítási folyamat várható értékére és szórására vonatkozik (bizonyítás nélkül) a korábbiak élesítése, s az el½oz½oekben bizonyított eredményekkel együtt átvihet½o a késleltetett felújítási folyamatok esetére is. Tétel 9 Ha
2
= ET12 < 1 és T1 eloszlása nem rácsos, akkor t ! 1 mellett t
H(t)
!
3
2 2
1; 2
2
D2 N (t) = Ha még
2
t + o(t):
3
= ET13 < 1 , akkor D2 N (t) =
2
2 3
t+
5 4
2 2 4
2 3
3 3
2
2 2
+ o(1):
Regeneratív folyamatok Sok tömegkiszolgálási rendszer leírható regeneratív folyamatok segítségével. Ez a tulajdonság lehet½oséget nyújt határeloszlás tételek bizonyítására, szimulációs módszerek használatára. A fogalmat egyszer½ubb formában adjuk meg a könnyebb érthet½oség kedvéért. De…níció 11 T hosszúságú ciklusnak nevezzük a (T; Z(t)) párt, ahol T nemnegatív értékeket felvev½o v.v., Z(t); t 2 [0; T ) sztochasztikus folyamat. 27
De…níció 12 A Z(t); t 0 sztochasztikus folyamatot regeneratív folyamatnak nevezzük t0 = 0 < t1 < t2 < ::: regenerációs pontokkal, ha létezik független (Tk ; Zk (t)); k 1 ciklusoknak olyan sorozata, hogy (1) Tk = tk tk 1 ; k 1, (2) P (Tk > 0) = 1; P (Tk < 1) = 1, (3) az összes ciklus sztochasztikusan ekvivalens, (4) Z(t) = Zk (t tk 1 ); ha t 2 [tk 1 ; tk ); k 1. De…níció 13 Ha a (3) tulajdonság csak a második ciklussal kezd½od½oen áll fenn (akkor a felújítási folyamatokkal analóg módon) késleltetett regeneratív folyamatokról beszélünk. Megjegyzés 12 A tk ; k
1 folyamat felújítási folyamat.
Regeneratív folyamatok esetén megadható elég általános feltétel, amely biztosítja azt, hogy létezik határeloszlása a Z(t) folyamatnak, vagyis létezik a lim P (Z(t) 2 A)
t!1
határérték. Ezen túlmen½oen biztosítja a határeloszlás meghatározhatóságát, ahol A tetsz½oleges intervallum. Regeneratív módszer alapja Legyen fZ(t); t 0g regeneratív folyamat t0 = 0 < t1 < t2 < ::: regenerációs pontokkal, Tn = tn tn 1 ; n = 1; 2; :::. Feltesszük, hogy a Z(t) folyamat 1 valószín½uséggel jobbról folytonos és balról létezik határértéke. Megjegyzés 13 Ekkor a fTn ; fZ(tn 1 + u) : 0 u < Tn gg; n = 1; 2; ::: ciklusok függetlenek és sztochasztikusan ekvivalensek; ftn ; n 1g és a hozzátartozó fN (t); t 0g számláló folyamat felújítási folyamatot alkot. Ez az alapja annak, hogy a felújítási folyamatokhoz hasonlóan, a regeneratív folyamatokra is bizonyítható a nagy számok törvénye és a centrális határeloszlás tétel. A továbbiakban jelölje F a fTn ; n 1g v.v.-k közös eloszlását. Legyen h : R ! R olyan mérhet½o függvény, amelyre minden t 0 esetén fennáll Ejh(Z(t))j < 1. Mivel Z(t) regeneratív folyamat, ezért a második ciklussal kezd½od½o része független az els½o T1 hosszúságú ciklustól, így tetsz½oleges 0 < s < t mellett E(h(Z(t))jT1 = s) = Eh(Z(t
s)):
Legyen g(t) = Eh(Z(t))I(T1 > t): Elég általános feltételek mellett fennáll lim Eh(Z(t))
t!1
=
1
Z1
g(s) ds =
Z1
Eh(Z(s)I(T1 > s) ds =
0
=
1
0
=
1
E
ZT1 0
28
h(Z(s)) ds;
és tetsz½oleges A
R intervallum esetén fennáll lim P (Z(t) 2 A)
t!1
01 1 Z 1@ P (Z(s) 2 A; T1 > s) dsA
=
0
1
=
1 0T Z1 E @ I(Z(s) 2 A) dsA : 0
Példa 1 Tekintsük az fN (t); t
0g felújítási folyamatot. A felújítási id½opontok legyenek t0 = 0; tn = T1 + T2 + ::: + Tn ; n
legyen továbbá P (Tk < x) = F (x); k
1,
=
R1
1;
x dF (x). Jelölje tetsz½oleges t > 0 esetén
0
(t) = t tN (t) ; (t) = tN (t)+1 t: (Pl. a t id½opontban (t) jelentheti azt, hogy mennyi ideig nem jött taxi az állomásra, (t) pedig azt, hogy mennyi ideig kell még várakozni a következ½o taxi érkezéséig, feltéve azt, hogy a követési id½ok független azonos eloszlású v.v.-k közös F eloszlásfüggvénnyel.) Tétel 10 f (t); t
0g és f (t); t
0g regeneratív folyamatok, továbbá nem rácsos F esetén fennáll
lim P ( (t)< x) =
t!1
lim P ( (t) < x) =
t!1
1
Zx 0
lim P ( (t)< x) =
t!1
1
Zx
F (s)ds:
0
29
(1
F (u)du;
Téma 6
Markov-láncok Diszkrét idej½u, diszkrét állapotter½u Markov-láncok, m-edrend½u Markov-lánc. Kezdeti eloszlás, egylépéses- többlépéses átmenetvalószín½uség. Homogén-, inhomogén Markov-lánc. Egylépéses-, m-lépéses átmenetvalószín½uség-mátrix. Az mlépéses átmenetvalószín½uségek és tulajdonságaik, Chapman-Kolmogorov egyenlet. Példák Markov-láncokra. Sztochasztikus folyamatok egyik fontos osztálya jellemezhet½o azzal a tulajdonsággal, hogy ha tetsz½olegesen megadott t0 id½opillanatban ismerjük a folyamatot, akkor ez a legteljesebb információ, amit a folyamatnak a megadott t0 id½opont utáni viselkedése leírásánál …gyelembe kell venni a t0 id½opontig vett meg…gyelésekb½ol. Azt is lehet mondani, hogy a folyamat jöv½obeni viselkedésére a t0 id½opontig meg…gyelt értékei közül csak az az érték van hatással, amelyet a folyamat a t0 id½opontban felvesz. Ez a tulajdonság, amely egyfajta emlékezetnélküliséget fejez ki, heurisztikusan úgy is megfogalmazható, hogy "a folyamat jöv½obeni viselkedése a jelenen keresztül függ a múlttól". Minthogy …zikai rendszerek esetén a szóbanforgó folyamatok értékei általában a rendszer állapotát adják meg a fázistérben, amelyek általában eleget tesznek ennek az emlékezetnélküli tulajdonságnak, ezért a szokásos terminológia szerint, ha a folyamat valamilyen id½opontban egy x értéket vesz, akkor azt mondjuk, hogy a folyamat (rendszer) az adott id½opontban az x állapotban tartózkodik. Az összes ilyen felvehet½o értékek, vagy állapotok halmazát állapotérnek nevezzük. Természetesen, az id½oparaméter és a lehetséges állapotok tere egyaránt lehet diszkrét, avagy folytonos, és ett½ol függ½oen megkülönböztetünk diszkrét, illetve folytonos idej½u (paraméter½u) és azon belül diszkrét, illetve folytonos állapotter½u Markov-folyamatokat. Mi a gyakorlati alkalmazások számára igen nagy jelent½oséggel bíró és bonyolultabb, mértékelméletre er½osen támaszkodó matematikai apparátust nem igényl½o diszkrét, illetve folytonos idej½u, diszkrét állapotter½u Markov-folyamatokkal, vagy ebben az esetben szokásos szóhasználat szerint Markov-láncokkal fogunk részletesebben foglalkozni. Ezt a fogalmat egyébként Markov 1907-ben vezette be egy dolgozatában. Kolmogorov, Doeblin, Doob és mások tevékenysége nyomán napjainkra általános, s a gyakorlati modellezések során eredményesen alkalmazható jól kidolgozott elméletté fejl½odött.
30
Diszkrét idej½u, diszkrét állapotter½u Markov-láncok Tekintsünk egy diszkrét idej½u fXt ; t 2 T g; T = f0; 1; :::g sztochasztikus folyamatot, amelynek lehetséges értékei egy X véges, vagy megszámlálhatóan végtelen számosságú halmaz elemei. Ekkor azt mondjuk, hogy a folyamat állapottere az X halmaz és elemeit a folyamat állapotainak nevezzük. Feltesszük, hogy tetsz½oleges t = 0; 1; ::: esetén az fXt = kg; k 2 X események páronként egymást kizáróak. Ha a folyamat egy t 2 T id½opontban az x 2 X értéket veszi fel, akkor azt mondjuk, hogy a folyamat a t 2 T id½opontban az x állapotban tartózkodik. Véges, vagy megszámlálhatóan végtelen állapottér esetén az állapotteret szokás azonosítani a következ½o halmazokkal:
vagy
X = f0; 1; :::; N g (véges eset) X = f0; 1; :::g (megszámlálhatóan végtelen eset).
Természetesen ez az azonosítás az említett esetekben legfeljebb átbet½uzéssel mindig megvalósítható és általában ez nem vezet külön problémához, mivel az általunk vizsgált kérdéseknél az állapotok konkrét megjelölésének nics különösebb jelent½osége (pl. állapotokban való tartózkodás valószín½uségének, egyik állapotból a másik állapotba való átmenet valószín½uségének, stb.). Olyan vizsgálatoknál, mint pl. egy Markov-típusú tömegkiszolgálási rendszerben a sorhosszúság várható értéke, ahol a Markov-lánc által felvett értékek fontosak lehetnek, az állapottér megválasztása magától értet½od½o módon egybeesik a fentivel. Egyébként az állapottér konkrét megválasztása praktikus szempontok szerint történhet. A következ½o de…nícióban a feltételes valószín½uség de…niálatlan, ha a feltétel valószín½usége 0. A kés½obbiek során feltesszük eleve, hogy csak olyan állapotokra írunk fel egyenleteket, ahol a feltétel valószín½usége pozitív, illetve értelemszer½uen kiterjesztjük az egyenleteket ezekre az esetekre is. De…níció 14 Az X folyamatot X állapoter½u diszkrét idej½u Markov-láncnak nevezzük, ha minden lehetséges n = 0; 1; ::: érték és tetsz½olegesen választott i0 ; :::; in 2 X állapotok mellett fennáll P (Xn+1 = in+1 j X0 = i0 ; :::; Xn = in ) = P (Xn+1 = in+1 j Xn = in ) Ez az összefüggés fejezi ki azt a korábban említett heurisztikus tulajdonságot, hogy a folyamat múlttól való függése a jelenen keresztül történik. Megjegyzés 14 A Markov-lánc de…níciójában valójában az un. els½orend½u Markov-láncról van szó, mivel a de…nícióbeli egyenlet jobboldalán szerepl½o feltételes valószín½uségben csak az utólsó, egy lépéssel korábbi érték szerepel. Hasonló módon de…niálhatjuk a magasabbrend½u Markov-láncokat is. 31
De…níció 15 Azt mondjuk, hogy az X folyamat X állapoter½u m-edrend½u Markov-lánc (m 1), ha minden n = 1; 2; ::: és ik 2 X ; k = 0; 1; ::: mellett teljesül P (Xn+m = in+m j X0 = i0 ; :::; Xn+m
1
= P (Xn+m = in+m j Xn = in ; :::; Xn+m
= in+m 1
1)
= in+m
=
1)
=
Azt hihetnénk, hogy a Markov-láncok általánosabb osztályához jutunk m > 1 rend esetén, azonban egyszer½uen bevezethet½o olyan új, az X Markov-lánc értékeivel meghatározott m dimenziós folyamat, amely els½orend½u Markov-lánc. Vezessük be X 0 = f(k1 ; :::; km ) : k1 ; :::; km 2 X g az állapotter½u Yn = (Xn ; :::; Xn+m
1 );
n = 0; 1; :::
sztochasztikus folyamatot. Ekkor
P (Yn+1 = (in+1 ; :::; in+m )j Y0 = (i0 ; :::; im
1 ); :::; Yn
= (in ; :::; in+m
1 ))
=
= P (Xn+m = in+m ; :::; Xn+1 = in+1 j X0 = i0 ; :::; Xn+m
1
= in+m
1)
=
= P (Xn+m = in+m ; :::; Xn+1 = in+1 j Xn = in ; :::; Xn+m
1
= in+m
1)
=
= P (Yn+1 = (in+1 ; :::; in+m )j Yn = (in ; :::; in+m
1 ))
Ezzel igazoltuk, hogy a bevezetett Y = fY0 ; Y1 ; :::g folyamat els½orend½u Markov-lánc. Ez a tény indokolja azt, hogy a továbbiakban csak els½orend½u Markov-lánccal foglalkozunk és az els½orend½u szót elhagyjuk. Markov-láncok vizsgálatában alapvet½o jelent½oséggel bírnak a de…níció jobboldalán szerepl½o feltételes valószín½uségek, melyeknek külön elnevezése is van. De…níció 16 A pij (n; n + 1) = P (Xn+1 = jj Xn = i); i; j 2 X ; n = 0; 1; ::: mennyiségeket az X = fX0 ; X1 ; :::g Markov-lánc egylépéses átmenetvalószín½uségeinek nevezzük. Szükséges megjegyezni egyrészt azt, hogy a de…nicióban szerepl½o i és j állapotok megegyezhetnek egymással (a folyamat a következ½o idöpontban maradhat ugyanabban az állapotban), másrészt a most bevezetett átmenetvalószín½uségek nem csak az i; j állapotoktól függhetnek, hanem attól is, hogy mely id½opontban (n) nézzük. Egyébként a Markov-láncok egyik legfontosabb osztályát képezik azok a folyamatok, amelyekre ezek a mennyiségek nem függnek az n id½ot½ol. De…níció 17 Azt mondjuk, hogy az X Markov-lánc homogén, ha a egylépéses átmenetvalószín½uségei függetlenek az n id½ot½ol, ekkor pij (n; n + 1) = pij ; i; j 2 X ; n = 0; 1; ::: Ellenkez½o esetben a Markov-láncot inhomogénnak (nemhomogénnak) nevezzük.
32
Megjegyzés 15 Ha egy X homogén Markov-lánc valahányszor egy tetsz½olegesen rögzített i0 2 X állapotba kerül egy bizonyos t id½opillanatban, akkor a t id½opont után statisztikai értelemben mindig ugyanúgy fog viselkedni, függetlenül attól, hogy a t id½opont el½ott milyen értékeket vett fel. Ez egyben azt is jelenti, hogyha az id½otengelyt olyan egymásutáni véletlen hosszúságú szakaszokra bontjuk, amelyek végein a folyamat az i0 állapotban tartózkodik, azonkívül különbözik t½ole, akkor a folyamat viselkedése ezeken a szakaszokon statisztikai értelemben azonos és egymástól független. Valószín½uségelméleti szemléletben ez képezi az alapját a Markov-láncokra vonatkozó nagy számok törvényének és a centrális határeloszlás tételnek. Egyébként ez a tulajdonság analóg a felújítási folyamatokkal és általánosabb formában a regeneratív folyamatoknál jelenik meg. Markov-láncok végesdimenziós eloszlásait az átmenetvalószín½uségek nem határozzák meg egyértelm½uen, hiszen az függhet a kiinduló valószín½uségi változó eloszlásától. De…níció 18 A fPi = Pi (0) = P (X0 = i); i 2 X g eloszlást az X Markov-lánc kezdeti eloszlásának nevezzük. Tétel 11 Tetsz½oleges X Markov-lánc esetén a kezdeti eloszlás és az egylépéses átmenetvalószín½uségek egyértelm½uen meghatározzák a végesdimenziós eloszlásokat. Bizonyítás. Jelölje {Pi ; i 2 X g az X Markov-lánc kezdeti eloszlását, pij (n; n + 1); i; j 2 X ; n = 0; 1; ::: pedig az egylépéses átmenetvalószín½uségeit. Ekkor tetsz½oleges n (n = 1; 2; :::) és i0 ; :::; in 2 X esetén, melyre P (X0 = i0 ; :::; Xn = in ) > 0, a feltételes valószín½uség de…níciója szerint írhatjuk, hogy P (X0 = i0 ; :::; Xn = in ) = = P (Xn = in j X0 = i0 ; :::; Xn 1 = in 1 )P (X0 = i0 ; :::; Xn 1 = in 1 ) = = P (Xn = in j X0 = i0 ; :::; Xn 1 = in 1 ) P (Xn 1 = in 1 j X0 = i0 ; :::; Xn 2 = in 2 ) ::: P (X1 = i1 j X0 = i0 )P (X0 = i0 ): Felhasználva a Markov-tulajdonságot azt kapjuk, hogy a keresett valószín½uség kifejezhet½o az egylépéses átmenetvalószín½uségek és a kezdeti eloszlás segítségével: P (X0 = i0 ; :::; Xn = in ) = pin
1 in
(n
1; n)pin
2 in 1
(n
2; n
1) ::: pi0 i1 (0; 1)Pi0 :
Megjegyzés 16 Abban az esetben, amikor az X Markov-lánc homogén, akkor a P (X0 = i0 ; :::; Xn = in ) valószín½uségre nyert összefüggés átírható egyszer½ubb alakba: P (X0 = i0 ; :::; Xn = in ) = pin
1 in
pin
2 in 1
::: pi0 i1 pi0 :
Markov-láncok vizsgálatát sokszor leegyszer½usíti az átmenetvalószín½uség-mátrixok használata. De…níció 19 A véges N , vagy megszámlálhatóan végtelen X állapotter½u, homogén Markovlánc átmenetvalószín½uségeib½ol alkotott 2 3 2 3 p00 p01 ::: p0N p00 p01 p12 ::: 6 p10 p11 ::: p1N 7 6 p10 p11 p12 ::: 7 7; 6 7 =6 illetve = 4 : 4 p20 p21 p22 : 5 : ::: : 5 pN 0 pN 1 ::: pN N
:
33
:
:
:::
mátrixot a Markov-lánc (egylépéses) átmenetvalószín½uség-mátrixának nevezzük. Ha a Markov-lánc nem homogén, akkor az n = 0; 1; ::: id½ot½ol függ½o véges, vagy megszámlálhatóan végtelen sok sorból és oszlopból álló n = [pij (n; n + 1)]i;j2X mátrixokat nevezzük a Markovlánc (egylépéses) átmenetvalószín½uség-mátrixainak. Megemlítjük, hogy az átmenetvalószín½uség-mátrixok sztochasztikus mátrixok, azaz rendelkeznek a következ½o tulajdonságokkal: a) Elemei nemnegatívok: pij
0; i; j 2 X
(pij (n; n + 1)
0; i; j 2 X ; n = 0; 1; :::)
b) Elemeinek soronkénti összege 1: 0 1 X X @ pij = 1 pij (n; n + 1); j 2 X ; n = 0; 1; :::A : j2X
j2X
PÉLDÁK: Az els½o példa azt mutatja, hogy független azonos eloszlású, diszkrét értékeket felvev½o valószín½uségi változók sorozata homogén Markov-láncot alkot. A második példa szerint ilyenek összege is homogén Markov-lánc lesz. Ha a kiinduló valószín½uségi változók sorozatát független, de nem azonos eloszlásúnak de…niálnánk, akkor szintén Markov-lánchoz jutnánk, amely azonban már nem feltétlenül lenne homogén. A harmadik példa a véletlen bolyongást írja le a számegyenesen. Ebben az esetben az állapotteret praktikus szempontból az X = f0; 1; 2; :::g halmazzal adjuk meg. Ahhoz, hogy szemléletesen az id½o függvényében tudjuk bemutatni, a síkon ábrázoljuk (ld. 1. ábra). Legyen U0 ; U1 ; ::: független azonos eloszlású valószín½uségi változók sorozata közös P (Um = k) = pk ; pk 0; k = 0; 1; :::; m = 0; 1; ::: eloszlással. 1) De…niáljuk az X folyamatot az Xn = Un ; n = 0; 1; ::: sorozattal. Ekkor az X = fXn ; n = 0; 1; 2; :::g folyamat homogén Markov-lánc P (X0 = k) = pk ; k = 0; 1; ::: kezdeti eloszlással és 3 2 p0 p1 p2 ::: 6 p0 p1 p2 ::: 7 7 =6 4 p0 p1 p2 : 5 : : : ::: átmenetvalószín½uség-mátrixszal.
2) Tekintsük azt az X folyamatot, melynek kezdeti eloszlása P (X0 = 0) = 1, és tetsz½oleges n = 1; 2; ::: esetén pedig Xn = U1 + ::: + Un . Ekkor az X folyamat egylépéses átmenetvalószín½uségeire fennáll pij (n; n + 1) = P (Xn+1 = jj Xn = i) = P (U1 + ::: + Un+1 = jj U1 + ::: + Un = i) = = P (Un+1 = j
i) =
pj i ; ha j i 0; ha j < i
Eszerint az X folyamat homogén Markov-lánc 34
2
6 6 6 =6 6 4
p0 p1 p2 0 p0 p1 0 0 p0 0 0 0 : : :
p3 p2 p1 p0 :
p4 p3 p2 p1 :
::: ::: ::: ::: :::
3 7 7 7 7 7 5
átmenetvalószín½uség-mátrixszal. 3) Legyen most az U0 ; U1 ; ::: független azonos eloszlású valószín½uségi változók közös eloszlása P (Ui = +1) = p; P (Ui = 1) = 1 p (0 < p < 1); i = 0; 1; ::: és de…niáljuk az X folyamatot ugyanúgy, mint b)-ben, azaz legyen P (X0 = 0) = 1 a kezdeti eloszlása, és tetsz½oleges n = 1; 2; ::: esetén pedig Xn = U1 + ::: + Un . Fentebb megjegyeztük, hogy ez a folyamat éppen azt a véletlen bolyongást írja le a számegyenesen, amely az origóból kiindulva minden lépésben egy egységnyit lép a számegyenesen jobbra p, balra pedig 1 p valószín½uséggel. Itt a p = 21 eset felel meg a szimmetrikus bolyongásnak. Az így de…niált X folyamat homogén Markov-láncot alkot és egylépéses átmenetvalószín½uségeire teljesül pij (n; n + 1) = P (Xn+1 = jj Xn = i) = P (U1 + ::: + Un+1 = jjU1 + ::: + Un+1 = i) = 8 p; ha j = i + 1; < = P (Un+1 = j i) = 1 p; ha j = i 1; : 0; ha ji jj = 6 1:
Bár az átmenetvalószín½uség-mátrix az összes információt tartalmazza az egyes állapotok között lehetséges átmenetekr½ol, azonban bizonyos esetekben szemléletesen is ábrázolhatók ezek az átmenetek. Az 1. ábra a bolyongás átmeneteit mutatja be az id½o függvényében. Xt 4 3 2 1 0 -1 -2 -3 -4
• • •
• •
• •
• •
0
1 2 3
4 5
•
• •
6 7 1. ábra
A 2. ábra egy véges állapotter½u Markov-lánc átmeneteit érzékelteti. 35
t
•
n n-1
• •
• 4 3 2 1 0
•
•
•
• •
• • 0 1 2 3 4 5 6 7
t
2. ábra
Az m-lépéses átmenetvalószín½uségek és tulajdonságaik Legyen X Markov-lánc X állapottérrel. Jelölje tetsz½oleges i; j 2 X és 0 számok mellett pij (s; t) = P (Xt = jj Xs = i); i; j 2 X ;
s
t < 1 egész
és vezessük be a (s; t) = [pij ]i;j2X mátrixokat. Homogén Markov-láncok esetén pij (s; t) a csak a t
s különbségt½ol függ, így
pij (s; s + m) = pij (m); s; m = 0; 1; :::; i; j 2 X ; ahol a pij (m); m = 0; 1; :::; i; j 2 X mennyiségeket az X homogén Markov-lánc m-lépéses átmenetvalószín½uségeinek nevezzük. Gyakran szükségünk lesz az m-lépéses átmenetvalószín½uségekb½ol képzett (m) = (pij (m))i;j2X m-lépéses átmenetvalószín½uség-mátrixra is. A fenti de…níciókban esetén pij =
1; ha i = j, 0; ha i 6= j.
Ha az X Markov-lánc nem homogén, akkor hasonló módon vezethet½ok be ezek a fogalmak, azonban az n (id½o) értékét½ol való függ½oség lehet½oségét …gyelembe kell venni. Tétel 12 (Chapman-Kolmogorov egyenlet) Tetsz½oleges m 0; r + s = m (r; s az X homogén Markov-lánc m-lépéses átmenetvalószín½uségeire fennáll X pij (m) = pik (r)pkj (s): k2X
36
0) esetén
Bizonyítás. Minthogy az fXr = kg; k 2 X események páronként egymást kizáróak, P P (Xr = k) = 1, ezért az m-lépéses átmenetvalószín½uség és a feltételes valószín½uség de…ník2X
ciója szerint homogén Markov-láncokra teljesül (…gyelembevéve az olyan feltételes valószín½uségekre tett korábbi megjegyzésünket, amelyeknél a feltétel valószín½usége esetleg a 0 értéket veszi fel): pij (m) = P (Xm = jj X0 = i) = P (Xm = j; X0 = i) X P (Xm = j; X0 = i; Xr = k) = = = P (X0 = i) P (X0 = i) k2X X P (X0 = i; Xr = k) P (Xm = j; X0 = i; Xr = k) = = P (X0 = i) P (X0 = i; Xr = k) k2X X = P (Xr = kj X0 = i)P (Xm = jj Xr = k; X0 = i) = k2X
=
X
pik (0; r)pkj (r; m) =
k2X
X
pik (r)pkj (m):
k2X
Megjegyzés 17 Hasonló módon igazolható, hogy inhomogén Markov-láncokra a ChapmanKolmogorov egyenlet a következ½o formában érvényes: X pik (s; r)pkj (r; t) pij (s; t) = k2X
ahol 0
s
r
t tetsz½oleges egész számok.
A korábban bevezetett (s; t) = (pij )i;j2X jelölés mellett ez az egyenlet átírható tetsz½oleges 0 s r t egész számok esetén a (s; t) =
(s; r) (r; t)
mátrixalakba. Egymás után ismételten felhasználva ezt az összefüggést kapjuk, hogy (0; m) =
(0; 1) (1; 2) :::
(n
1; n):
Homogén esetben egyszer½u következményként adódik a Markov-lánc m-lépéses átmenetvalószín½uség-mátrixára, hogy (m) = m ; ahol
=
(0; 1) a homogén Markov-lánc egylépéses átmenetvalószín½uség-mátrixát jelöli.
37
Téma 7
Homogén Markov-láncok osztályozása Homogén Markov-láncok állapotainak osztályozása az átmenetvalószín½uségek aritmetikai tulajdonságai szerint: elérhet½o, kapcsolódó, elnyel½o állapotok. Irreducibilis osztályok, irreducibilis Markov-lánc. Aperiodikus és periodikus Markovlánc. Homogén Markov-láncok átmenetvalószín½uségeinek aszimptotikus tulajdonságai. Visszatér½o Markov-láncok. Állapotok els½o elérése, els½o visszatérés adott állapotba els½o elérési, illetve visszatérési valószín½uségek, visszatér½o-, átmeneti állapotok és az m-lépéses átmenetvalószín½uségek közötti összefüggés.
Markov-láncok viselkedése, aszimptotikus tulajdonsága alapvet½oen függ az egyes állapotok között fennálló kapcsolatoktól, melyek az átmenetvalószín½uségekben tükröz½odnek vissza. Ezekben a Markov-lánc különböz½o értékei nem játszanak szerepet, csak az egyes állapotok megkülönböztetésére szolgálnak. Jelölje Pi (t) = P (Xt = i); i 2 X az X Markov-lánc eloszlását a t id½opontban. A Markov-láncok elméletében az egyik fontos kérdés, hogy létezik-e az id½ot½ol függ½o P (t) = (pi (t); i 2 X ) eloszlásnak X lim P (t) = = ( i ; i 2 X ); i 0; i =1 t!1
i2X
határeloszlása tetsz½oleges X0 = k 2 X , kezdeti feltétel mellett. Az erre adható válaszban fontos szerep jut az átmenetvalószín½uségek aritmetikai tulajdonságainak. Tekintsük azt az esetet, amikor az X állapottér felbontható két olyan egymással diszjunkt (nem üres) X1 és X2 részhalmaz uniójára, melyekre pij = pji = 0, ha , i 2 X1 és j 2 X2 . Ekkor nyilvánvaló, hogy X0 = i0 2 X1 kezdeti érték esetén Xt 2 X1 minden t 0 esetén és fordítva, Xt 2 X2 ; t 0, ha az i0 kezdeti értékre i0 2 X2 : Ez az észrevétel már utal az átmenetvalószín½uségek aritmetikai tulajdonságainak fontos szerepére. Nem nehéz észrevenni, hogy ebben az esetben az X1 , illetve X2 részhalmazokhoz tartozó állapotok egymástól függetlenül vizsgálhatók. De…níció 20 Azt mondjuk, hogy a j 2 X állapot elérhet½o az i 2 X állapotból (jele: !), ha létezik olyan m 1 egész szám, hogy pij (m) > 0. Ha két i és j állapot olyan, hogy kölc38
sönösen elérhet½ok egymásból, akkor az ilyen állapotpárt kapcsolódóknak nevezzük (ennek a szimmetrikus relációnak a jele i !j). Világos, hogy ha az i és j állapotok nem kapcsolódóak, akkor vagy minden m 1-re pij (m) = 0, vagy pedig minden m 1-re pji (m) = 0. Biztosan nem lehet egyetlenegy állapottal sem kapcsolódó az olyan i állapot, amelyre pii = 1: Az ilyen állapotokat elnyel½o állapotoknak nevezzük. Vizsgálatainkban az állapotok osztályozása során nem játszanak fontos szerepet az olyan i 2 X állapotok, amelyekre van olyan j állapot, hogy i-b½ol j elérhet½o (i ! j), de fordítva nem (i 8 j). Az ilyen állapotokról elmondható, hogyha a Markov-lánc egyszer egy ilyen állapotba kerül, utána sohasem térhet vissza ugyanoda pozitív valószín½uséggel. Könny½u meggy½oz½odni arról, hogy az állapotok között bevezetett ! reláció re‡exív, szimmetrikus és tranzitív, vagyis ekvivalencia-reláció. Ezért X felbontható olyan további véges, vagy megszámlálhatóan sok nem üres, páronként diszjunkt X1 ; X2 ; ::: részhalmazok uniójára, hogy minden k 1-re Xk elemei mind kapcsolódók, ugyanakkor tetsz½oleges k 6= n és i 2 Xk ; j 2 Xn esetén az i és j állapotok nem kapcsolódók. De…níció 21 Azokat az osztályokat, melyeknek elemei mind kapcsolódó, irreducibilis osztályoknak nevezzük. Markov-láncok elméletében alapvet½o jelent½oséggel bírnak azok a Markov-láncok, amelyekre minden állapot egymással kapcsolódó. De…níció 22 Egy Markov-láncot irreducibilisnek nevezünk, ha bármely állapot elérhet½o tetsz½oleges más állapotból. Ez azt jelenti, hogy egy irreducibilis Markov-lánc egy irreducibilis osztályt képez, vagyis tetsz½oleges i; j 2 X állapot esetén létezik olyan (i-t½ol és j-t½ol függ½o) m 1 egész, hogy pij (m) > 0. A következ½o fontos fogalom a Markov-láncok peridicitása. De…níció 23 Jelölje tetsz½oleges i 2 X állapot esetén d(i) azoknak az m 1 egész számoknak a legnagyobb közös osztóját, amelyekre pij (m) > 0. Ha pij (m) = 0 minden m-re, akkor legyen d(i) = 0. A d(i) számot az i állapot periodusának nevezzük. Az olyan Markov-láncot, melyre minden állapot periodusa 1, aperiodikus Markov-láncnak nevezzük. PÉLDA periodikus Markov-láncra. Tekintsük a homogén Markov-láncokra korábban bemutatott egyszer½u bolyongás esetét a számegyenesen. Világos, hogy ebben az esetben minden i állapotra d(i) = 2, hiszen tetsz½oleges i állapotból kiindulva 2; 4; 6; ::: lépésben térhetünk vissza ugyanoda pozitív valószín½uséggel. Ekkor a pozitív valószín½uség½u lépésszámok (a páros természetes számok) legnagyobb közös osztója nyilvánvalóan 2. Megjegyezzük azt is, hogy a 0 id½opontban a 0 állapotból kindulva páros lépésben csak páros, páratlan lépésszám esetén pedig csak páratlan állapotba kerülhet a Markov-lánc. 39
Tétel 13 Legyen X tetsz½oleges homogén Markov-lánc X állapottérrel és legyen X 0 X egy tetsz½oleges (nem üres) irreducibilis osztály. Ekkor minden lehetséges i; j 2 X 0 mellett az i és j állapotok periodusai megegyeznek egymással, vagyis egy irreducibilis osztály állapotainak létezik közös d(X 0 ) peiódusa. Bizonyítás. Legyen i; j 2 X 0 két tetsz½oleges, egymástól különböz½o állapot. Az irreducibilitás miatt létezik olyan t; s > 0 egész, hogy fennáll pij (t) > 0 és pji (s) > 0 feltétel. Innen és a Chapman-Kolmogorov egyenlet alapján következik, hogy pii (t + s)
pij (t)pji (s) > 0 és
pjj (t + s)
pji (s)pij (t) > 0:
Így d(i) és d(j) nem nulla véges szám. Legyen pij (m) > 0 valamilyen m 1 egész szám mellett (ilyen biztosan van, hiszen az m = t+s választás megfelel ennek a tulajdonságnak). Ekkor a Chapman-Kolmogorov egyenlet ismételt alkalmazásával kapjuk, hogy pjj (t + s + m) Mivel k
pji (t)pii (m)pij (s) > 0:
1 tetsz½oleges egész szám mellett pjj (t + s + km)
k
pji (t) (pii (m)) pij (s) > 0
így a periodus de…níciója szerint d(j) osztója a (t + s + m) és a (t + s + 2m) számok mindegyikének, így ezzel együtt a (t + s + 2m) (t + s + m) = m különbségnek is. Ebb½ol következik, hogy osztója az összes olyan m-ek legnagyobb közös osztójának, melyekre pii (m) > 0, vagyis d(i)-nek is. Ezért fennáll a d(j) d(i) egyenl½otlenség. Innen, i és j szerepének felcserélésével nyerjük, hogy d(i) d(j), azaz d(j) = d(i).
Következményként tetsz½oleges homogén irreducibilis Markov-láncra kimondhatjuk az alábbi tételt. Tétel 14 Homogén irreducibilis Markov-lánc periodusa minden állapotra egy és ugyanaz a közös d = d(X ) szám, amely az adott esetben a Markov-láncra jellemz½o. Egy ilyen Markovlánc nyilvánvalóan vagy periodikus, vagy aperiodikus aszerint, hogy d = 1, vagy d > 1. Felmerül az a kérdés, hogy milyen jellegzetességet mutatnak azok a k számok, amelyekre a k lépéses átmenetvalószín½uségek pozitívak. Erre vonatkozik az alábbi állítás. Tétel 15 Legyen X homogén irreducibilis Markov-lánc X állapottérrel és legyen i 2 X tetsz½oleges állapot. Ekkor létezik olyan Mi egész szám, hogy tetsz½oleges m Mi esetén pii (md(i)) > 0. Bizonyítás. Az el½oz½o tétel szerint d(i) 1: Legyenek m1 ; :::; mL olyan egész számok, melyekre egyrészt pii (mk ) > 0, 1 k L, másrészt d(i) el½oáll úgy, mint az m1 ; :::; mL számok legnagyobb közös osztója. Ekkor a számelméletb½ol ismert tétel alapján van olyan Mi szám, hogy minden m Mi egész mellett létezik az md(i) = i1 m1 + ::: + iL mL egyenletnek megoldása nemnegatív egész i1 ; :::; iL számokkal. Ezt az összefüggést és a ChapmanKolmogorov egyenletet felhasználva nyerjük, hogy pii (md(i))
(pii (m1 ))i1 ::: (pii (mL ))iL > 0: 40
Vizsgáljuk meg most a azokat a homogén irreducibilis Markov-láncokat, amelyek d(X ) periodusa egynél nagyobb. Megmutatjuk, hogy az átmenetek között egyfajta ciklikus tulajdonság áll fenn, mint ami meg…gyelhet½o a korábban említett példánkban, a számegyenesen történ½o véletlen bolyongás esetén. Ebben a példában minden második lépésben csak páros, vagy páratlan állapotba kerülhetünk attól függ½oen, hogy páros, vagy páratlan állapotból indultunk ki. Rögzítsünk egy tetsz½olegesen választott i0 2 X állapotot és vezessük be k = 0; 1; :::; d 1 esetén az állapotok következ½o halmazait: Xk = fi 2 X : pi0 i (k + md) > 0; valamely m Tétel 16 Az X0 ; :::; Xd
1
1-reg
halmazok állapotai között a Markov-lánc csak az alábbi X0 ! X1 ! ::: ! Xd
1
! X0
ciklikus átmenetet engedi meg. Bizonyítás. Egyszer½uen igazolhatjuk, hogy az X1 ; :::; Xd 1 halmazok diszjunktak és uniójuk kiadja a teljes állapotteret. Ugyanis, ha ezek a halmazok nem lennének diszjunktak, akkor léteznek olyan k1 ; k2 ; m1 ; m2 egész számok, melyekre fennál 0 k1 < k2 d 1; m1 ; m2 1; valamint pi0 i (k1 + m1 d) > 0 és pi0 i (k2 + m2 d) > 0. Mivel a Markov-lánc irreducibilis, ezért biztosan létezik olyan K 1 egész, hogy pii0 (K) > 0. Felhasználva a Chapman-Kolmogorov egyenletet kapjuk, hogy pi0 i0 (k1 + m1 d + K) pi0 i0 (k2 + m2 d + K)
pi0 i (k1 + m1 d)pii0 (K) > 0; pi0 i (k2 + m2 d)pii0 (K) > 0;
ezért a d periodus a de…níció szerint osztója a (k1 + m1 d + K) és (k2 + m2 d + K) számok mindegyikének, így a (k2 k1 ) + (m2 m1 )d különbségüknek is. Innen következik, hogy d osztója a (k2 k1 ) számnak, ami nyilvánvalóan nem állhat fenn, mivel 0 < k2 k1 d 1. Az irreducibilitás miatt, mivel az i0 állapotból tetsz½oleges i 2 X állapotba pozitív valószín½uséggel el lehet jutni, ezért fennáll X = X0 [ ::: [ Xd 1 . Belátjuk most azt, hogy tetsz½oleges választott k = 0; 1; :::; d 1; i 2 Xk és olyan tetsz½oleges olyan j 2 X mellett, amelyre pij > 0, fennáll j 2 XK , ahol K k + 1 (mod d); azaz K + 1, ha 0 k < d 1 és K = 0; ha k = d 1. Válasszuk meg n-et úgy, hogy teljesüljön pi0 i (n) > 0. Világos, hogy Xk de…níciója szerint létezik olyan m egész, hogy pi0 i (k + md) > 0. K de…níciója szerint van olyan M egész, hogy k + md + 1 el½oállítható k + md + 1 = K + M d alakban. Minthogy teljesül a pij > 0 feltétel, így a Chapman-Kolmogorov egyenl½oség felhasználásával adódik, hogy pi0 j (K + M d) = pi0 j (k + md + 1)
pi0 i (k + md)pi0 j :
Innen, az Xk halmaz de…níciója szerint kapjuk, hogy j 2 Xk .
A most bizonyított tételb½ol adódik egy igen fontos következtetés. Következmény 1 Minthogy tetsz½oleges k = 0; 1; :::; d 1 esetén bármely Xk -beli állapotból kiindulva pontosan d lépés után kerülünk vissza egy Xk -beli állapotba, ezért ha bevezetjük a (k)
pij = P (Xd = ij X0 = j); i; j 2 Xk 41
mennyiségeket, akkor az el½obbiek szerint X (k) pij = 1; i 2 Xk : j2Xk
(k)
Így a pij
i;j2Xk
sztochasztikus mátrixot felfoghatjuk úgy is, mint egy Xk állapotter½u Markov-
lánc egylépéses átmenetvalószín½uség-mátrixát. Ez azt jelenti, hogy az Xk ; k = 0; 1; :::; d 1 halmazokhoz hozzárendelhetünk egy-egy homogén irreducibilis Markov-láncot és az eredeti d periodusú homogén irreducibilis Markov-lánc m-lépéses átmenetvalószín½uségek melletti aszimptotikus vizsgálatát visszavezethetjük d darab homogén aperiodikus irreducibilis Markovlánc vizsgálatára. Homogén Markov-láncok átmenetvalószín½uségeinek aszimptotikus tulajdonságai. Visszatér½o Markov-láncok.
Homogén Markov-láncok vizsgálata során alapvet½o jelent½oség½u kérdés az, hogy létezik-e a P Markov-láncnak határeloszlása, azaz létezik-e olyan = ( i ; i 2 X ) eloszlás ( i 0; i = i2X
1), hogy a (Pi ; i 2 X ) kezdeti eloszlástól függetlenül fennáll lim P (Xn = i) =
n!1
i;
i 2 X:
Ennek a kérdésnek a megválaszolásához szükség lesz olyan mennyiségek vizsgálatára is, mint pl. egy adott állapotba való visszatérés valószín½usége, a visszatérés lépésszámának várható értéke. Legyen i; j 2 X tetsz½oleges állapot és vezessük be a következ½o jelöléseket: fij (0) = 0; fij (1) = P (X1 = jj X0 = i); fij (n) = P (Xn = j; Xm 6= j; ha m = 1; 2; :::; n
1j X0 = i); n = 2; 3; :::
A most bevezetett fij (n) mennyiség annak a valószín½uségét adja meg, hogy a 0 id½opontban az i állapotból kiinduló Markov-lánc el½oször az n id½opontban kerül a j állapotba. Ha i 6= j, akkor az fij (n) mennyiség a j állapot n lépés alatt történ½o els½o elérésének a valószín½uségét, míg ha i = j, akkor az i állapotba n lépés alatt történ½o els½o visszatérés valószín½uségét jelenti. Az els½o elérési, illetve visszatérési valószín½uségek és az m-lépéses átmenetvalószín½uségek közötti összefüggést az alábbi tételben foglalt un. diszkrét felújítási egyenlet mutatja: Tétel 17 Tetsz½oleges i; j 2 X ; n = 1; 2; ::: esetén igaz n X pij (n) = fij (k)pjj (n
k):
k=1
Bizonyítás. Világos, hogy n = 1 esetén teljesül az pij (1) = fij (1)pjj (0) = fij (1) egyenlet. Legyen most n 2. Ekkor n X pij (n) = P (Xn = jj X0 = i) + P (Xn = j; Xk = j; Xm 6= j; 1 m k 1j X0 = i) = = fij (1)pjj (n
1) +
k=2 n X
fij (k)pjj (n
k); n = 1; 2; :::
k=2
42
Jelölje fij =
1 P
k=1
fij (k); i; j 2 X . Ez a mennyiség azt a valószín½uséget fejezi ki, hogy a 0
id½opillanatban az i állapotból kiinduló Markov-lánc valamikor a j állapotba jut. De…níció 24 Azt mondjuk, hogy az i 2 X állapot visszatér½o, ha fii = 1: Azokat az állapotokat, amelyek nem visszatér½oek, átmenetinek nevezzük. Egy Markov-láncot visszatér½onek, vagy átmenetinek nevezünk, ha az összes állapota visszatér½o, vagy átmeneti. Ez az osztályozás ebben a formában a pii (n) átmenetvalószín½uségekb½ol származtatott fii mennyiségekt½ol függ, azonban az eredeti pii (n) átmenetvalószín½uségekkel is megadható a következ½o tétel szerint. Tétel 18 (a)
Legyen i; j 2 X tetsz½oleges. Az i állapot akkor és csak akkor visszatér½o, ha 1 X
n=1
(b)
pii (n) = 1:
Ha i visszatér½o állapot, valamint i és j kapcsolódók, akkor j is visszatér½o.
Megjegyzés 18 Tetsz½oleges i 2 X állapot esetén egyszer½uen felírható az i állapotba való visszatérések számának várható értéke. Legyen a Markov-lánc kezdeti eloszlása P (X0 = i) = 1, azaz induljon ki a Markov-lánc az i állapotból 1 valószín½uséggel. Ekkor a visszatérések számának várható értéke ! 1 1 1 1 X X X X pii (k): P (Xk = ij X0 = i) = I(Xk = i) = E I(Xk = i) = E k=1
k=1
k=1
k=1
A tétel állítása szerint egy i 2 X állapot akkor és csak akkor visszatér½o, amikor a visszatérések számának várható értéke végtelen. A pij (n) n-lépéses átmenetvalószín½uségek n ! 1 melletti aszimptotikus tulajdonságával foglalkozik a következ½o tétel. Tétel 19 Ha a j 2 X állapot nem visszatér½o, akkor tetsz½oleges i 2 X állapotra igaz 1 X
n=1
pij (n) < 1
és
lim pij (n) = 0:
n!1
Bizonyítás. Az el½oz½o tétel bizonyításával analóg módon nyerjük, hogy 1 X
n=1
pij (n) =
1 X n X
fij (k)pjj (n
k) =
n=1 k=1
Minthogy a j állapot nem visszatér½o, ezért
1 X
fij (k)
k=1
1 P
n=1
n X
pjj (n
n=k
pjj (n) < 1, így fij
amely egyben a tétel második állítását is kiadja. A következ½o állítás igaz visszatér½o állapotokra. 43
k) = fij
1 X
pjj (n):
n=1
1 miatt
1 P
n=1
pij (n) < 1,
Tétel 20 Ha i 2 X állapot visszatér½o, akkor 1 valószín½uséggel végtelen sokszor visszatér az i állapotba. Ha az i; j 2 X állapotok kapcsolódók, és osztályuk visszatér½o, akkor igaz fij =
1 X
fij (k) = 1:
k=1
Példa visszatér½o Markov-láncra. Korábbi példánkban már szerepelt a véletlen bolyongás a számegyenesen. Kiindulva az origóból, egy részecske véletlenszer½uen mozog egy egységnyit jobbra, illetve balra, p, illetve 1 p valószín½uséggel (0 < p < 1). Ebben az esetben a részecske mozgását leíró folyamat homogén Markov-lánc, X = f0; 1; 2; :::g állapottérrel és 8 ha j =i+1 < p; 1 p; ha j=i 1 pij = : 0; ha j i jj = 6 1
egylépéses átmenetvalószín½uséggel. Világos, hogy a Markov-lánc irreducibilis és a periodusa pontosan 2. A kérdés az, hogy az állapotai vajon visszatér½oek-e. Ennek a kérdésnek az eldöntéséhez vizsgáljuk meg az nlépéses visszatérési valószín½uségek összegét. Könny½u észrevenni, hogy p00 (2k + 1) = 0; k = 0; 1; ::: Másrészr½ol az is világos, hogy a 0 állapotba a részecske 2k lépés alatt csak akkor tér vissza, amikor jobbra is, balra is (tetsz½oleges sorrendben) pontosan k lépést tesz. Ennek a valószín½usége p00 (2k) =
2k k p (1 k
p)k =
(2k)! [p(1 k!k!
p)]k :
A Stirling-formula szerint k!-ra k ! 1 mellett a következ½o aszimptotika adódik: k!
k e
k
k
p
p
2 k
felhasználásával a következ½o aszimptotikát kapjuk p00 (2k) =
2k e
2k
p
2 (2k)
k e
2 k
!
2
[p(1
p)]k =
[4p(1 p
p)]k : k
A számláló könnyen becsülhet½o a számtani és mértani közepek között fennálló egyenl½otlenség segítségével: p(1
p)
p + (1 2
p)
2
=
1 ; 4
ahol az egyenl½oség csak abban az esetben áll fenn, amikor p = 1 p, vagyis p = 1=2, és az összes többi esetben a szorzat kisebb 1=4-nél. Ez azt jelenti, hogy a p00 (2k) visszatérési valószín½uségek sora egyedül a p = 1=2 esetben (szimmetrikus bolyongás) divergens, az összes többi esetben mindig konvergens. A korábbi tételünk következményeként azt kapjuk, hogy csak a szimmetrikus esetben lesz a Markov-lánc 0 állapota és így az irreducibilitás miatt az összes többi állapota is - visszatér½o. Megjegyezzük, hogy hasonló eredményre jutunk abban az esetben, amikor a számegyenes helyett a sík egész érték½u pontjaiban nézz½uk a véletlen bolyongást. Belátható, hogy a szimmetrikus bolyongás esetén, amikor a részecske véletlenszer½uen mozog egy egységnyit jobbra, balra, felfelé, vagy lefelé egyaránt 1=4 1=4 valószín½uséggel, akkor a (0; 0) állapot visszatér½o. Nem szimmetrikus bolyongás esetén nincs visszatér½o állapot. Érdekes megjegyezni, hogy 2-nél magasabb dimenzióban a Markov-lánc már szimmetrikus esetben sem lesz visszatér½o.
44
Téma 8
Homogén Markov-láncok határeloszlása. Stacionárius, vagy egyensúlyi eloszlás, stacionárius eloszlás létezése. Iterációs eljárás a stacionárius eloszlás meghatározására. Ergodikus tétel Markov-láncokra. Tekintsük az X homogén Markov-láncot X = f0; 1; :::g állapottérrel, = (pij )i;j2X (egylépéses) átmenetvalószín½uség-mátrixszal és P = P(0) = (Pi = P (X0 = i); i 2 X ) kezdeti eloszlással. Jelölje (n) = ( i (n) = P (Xn = i); i 2 X ); n = 0; 1; ::: a Markov-lánc id½ot½ol függ½o eloszlását ( i (0) = pi ; i 2 X ). A legfontosabb kérdés, amit vizsgálni fogunk most az, hogy (a) mikor létezik a pij (m) m-lépéses átmenetvalószín½uségeknek m ! 1 mellett, valamint (b) a Markov-lánc id½ot½ol függ½o (n) eloszlásának n ! 1 esetén határértéke, és hogyan határozhatók meg? Ezek a kérdések szorosan összefüggnek a Markov-lánc visszatér½o állapotaival, vagyis az olyan i 2 X állapotokkal, amelyekre fii =
1 X
fii (k) = 1:
k=1
Itt megjegyezzük, hogy ez a visszatér½o tulajdonság nem függ a Markov-lánc kezdeti eloszlásától.
45
A visszatér½o állapotokra az n-lépéses átmenetvalószín½uségek aszimptotikus tulajdonsága, a nem nulla határérték létezése attól függ, hogy a visszatérési id½onek létezik-e véges i
=
1 X k=1
kfii (k) < 1
várható értéke. E feltétel teljesülése szerint tovább osztályozzuk az állapotokat. De…níció 25 Egy i 2 X állapotot visszatér½o pozitív, vagy nemnullaállapotnak nevezünk, ha i véges és visszatér½o nullaállapotnak, ha i = 1. Tétel 21 Legyen az X homogén Markov-lánc irreducibilis, visszatér½o és aperiodikus. Ekkor az öszes i; j 2 X állapotra teljesül 1
lim pij (n) =
n!1
:
j
Megjegyezzük, hogy a tétel nem csak a határértékeket adja meg, hanem egyben megvilágítja a bevezetett nemnullaállapot és nullaállapot fogalmát is. Eszerint egy visszatér½o j állapot nemnullaállapot, ha 1= j > 0 és nullaállapot, ha 1= j = 0 (itt és a továbbiakban az 1=1 = 0 konvencióval fogunk élni). A tételbeli aszimptotikus viselkedés szoros összefüggésben van a Markov-láncokra bizonyított diszkrét felújítási egyenlettel, melyre elég általános feltételek mellett bizonyíthatók konvergenciatételek. Ennek lényegét a következ½o eredmény mutatja (Erd½os, Feller, Pollard) , melyet bizonyítás nélkül közlünk. Lemma 4 Legyen fqi ; i
0g
tetsz½oleges valószín½uségeloszlás a nemnegatív egész számokon (qi
0;
1 P
i=0
qi = 1) és tegyük fel, hogy a fqi g
eloszlás nem rácsos szerkezet½u, azaz a qi > 0 feltételnek eleget tev½o indexek legnagyobb közös osztója 1. Ha a fvn ; n 0g számsorozat kielégíti a v0 = 1; vn =
n X
qk vn
k;
n
1
k=1
diszkrét felújítási egyenletet, akkor lim vn =
1
n!1
ahol =
1 X
kqk
és
k=1
;
1= = 0; ha = 1:
A (4) Tétel bizonyításához szükség lesz még egy eredményre az analízisb½ol. Lemma 5 Legyen a fqi g számsorozat olyan, mint az el½oz½o lemmában. Ha a fwn ; n konvergens, lim wn = w, akkor n!1
lim
n!1
n X
qn
k=0
46
k wn
= w:
0g számsorozat
Bizonyítás. Világos, hogy fwn g egyenletesen korlátos és így valamely véges W szám mellett jwn j W; n 1 P 0. A lim wn = w és qi = 1, feltételekb½ol következik, hogy tetsz½oleges " > 0 mellett van olyan N (") és n!1
i=0
K(") egész szám, hogy
jwn
wj < "
és
1 X
qk < ":
k=K(")
Könny½u ellen½orizni, hogy n > n(") = max(N ("); K(")) mellett jwn
n X
wj
qk wn
n X
k
k=0 n(")
X
k=0
qk jwn
n X
k=n(")+1
qk " +
k=0
wj +
k
n(")
X
qk w
k=0
n X
k=n(")+1
qk jwn
qk (W + jwj) +
wj +
k
1 X
k=n+1
1 X
k=n+1
qk jwj
qk jwj
" + "(W + jwj) + "jwj = "(1 + W + 2jwj): Minthogy " akármilyen kicsinek választható, így innen közvetlenül adódik a wn ! w; n ! 1 konvergencia. Rátérünk a (21) Tétel bizonyítására. Bizonyítás. A bizonyítás két részben történik. a) El½oször i = j mellett igazoljuk az állítást. A diszkrét felújítási egyenlet szerint pii (0) = 1;
pii (n) =
n X
fii (k)pii (n
k); n = 1; 2; :::;
k=1
ahol az i állapot visszatér½o tulajdonsága következtében fii =
1 P
fii (k) = 1 (fii
0). Felhasználva az 21.
k=1
Lemma eredményét kapjuk, hogy lim pii (n) =
1
n!1
:
i
b) Legyenek most i; j 2 X egymástól különböz½o állapotok és alkalmazzuk a 5. Lemmát. Mivel a Markov-lánc 1 P irreducibilis és visszatér½o, ezért fij = fij (k) = 1 (fij 0). Ekkor n ! 1 mellett k=1
lim pij (n) = lim
n!1
n!1
n X
fij (k)pjj (n
k) =
k=1
1 X
k=1
fij (k)
1 j
=
1
:
j
A most bizonyított eredmények könnyen átvihet½ok periodikus Markov-láncokra is. Legyen X homogén, d periodusú (d > 1), irreducibilis visszatér½o Markov-lánc. Ebben az esetben az X állapottér felbontható páronként diszjunkt X0 ; :::; Xd
1
ciklikus osztályokra a következ½o tulajdonsággal: Tetsz½oleges 0 k; m d 1 esetén bármely i 2 Xk állapotból kiindulva pontosan d lépésszám múlva kerülhetünk vissza el½oször pozitív valószín½uséggel egy Xk -beli állapotba és 47
pontosan `=
m m
k; ha k < m k + d; ha m k
lépés múlva egy Xm -beli állapotba, egyébként pij (s) = 0, ha s
1 nem osztható d-vel.
Tétel 22 Legyen az X Markov-lánc homogén, irreducibilis, visszatér½o d > 0 periodussal, i 2 Xk ; j 2 Xm; pedig tetsz½oleges állapotok. Ekkor lim pij (` + nd) =
d
n!1
ahol j
=
1 X
;
j
kfjj (k) =
1 X
rdfjj (rd):
r=1
k=1
Bizonyítás. Legyen el½oször k = m, ekkor az i; j 2 Xk állapotok mellett vizsgáljuk a pij (nd) átmenetvalószín½uségeket. Ez pontosan ugyanazt jelenti (ld. következmény a periodikus Markov-láncok ciklikusságáról), mintha azt az X Markov-láncot vizsgálnánk, melynek állapottere Xk és egylépéses átmenetvalószín½uség-mátrixa = d; ahol az eredeti Markov-lánc egylépéses átmenetvalószín½uség-mátrixát jelöli. Világos, hogy ebben az esetben a származtatott X Markov-lánc már homogén, irreducibilis, visszatér½o és aperiodikus lesz. Figyelembevéve, hogy az X Markov-lánc egylépéses átmenetvalószín½uségeire teljesül pij = pij (d); ezért a Markov-láncokra bizonyított határeloszlás tételünk felhasználásával kapjuk, hogy lim pii (n) = lim pii (nd) =
n!1
n!1
1 1 P
=
kfii (kd)
k=1
d 1 P
kdfii (kd)
=
d
:
i
k=1
Tegyük fel most, hogy k 6= m. Ekkor, mivel fij (k) = 0 és pij (k) = 0; ha k 6= ` + nd; d 0; 1 P továbbá az X Markov-lánc visszatér½osége miatt fij = fij (` + rd) = 1, ezért n ! 1 k=1
mellett adódik, hogy
pij (` + nd) =
1 X
fij (k)pjj (` + nd
k) =
1 X r=1
k=1
Ezzel befejeztük a 22. tétel bizonyítását.
48
fij (` + rd)pjj (rd) !
d j
:
Következmény 2 Ha az X homogén Markov-lánc irreducibilis, és valamely i 2 X állapota pozitív visszatér½o, akkor minden egyes állapota pozitív visszatér½o. Bizonyítás. Legyen j 2 X tetsz½oleges. Mivel a Markov-lánc irreducibilis, ezért létezik olyan s; t > 0, hogy teljesül pij (s) > 0; pji (t) > 0. Jelölje a Markov-lánc periódusát d. Világos, hogy d > 0, mivel pii (s + t) pij (s)pji (t) > 0. Másrészr½ol pii (s + nd + `)
pij (s)pjj (nd)pji (t);
pjj (s + nd + `)
pji (t)pii (nd)pij (s):
Innen a 22. Tétel alapján határátmenettel következik, hogy 1
pij (s)
1
i
pji (t);
j
1
pij (s)
j
1
pji (t)
i
ezért 1
pij (s)pji (t)
i
1
[pij (s)pji (t)]2
j
1
:
i
Ez azt jelenti, hogy ha az i visszatér½o nemnullaállapot, akkor j is az. Az eddig bizonyított tételek összefoglalásaként a következ½o állítást fogalmazhatjuk meg. Tétel 23 Legyen X homogén irreducibilis Markov-lánc. Ekkor az összes állapot vagy mind aperiodikus, vagy pedig mind periodikus ugyanazzal a periódussal, vagy mind átmeneti, vagy mind visszatér½o és azon belül: - vagy mind nemnullaállapot, - vagy mind nullaállapot.
Stacionárius eloszlás létezése. A korábbi jelöléseinknek megfelel½oen tetsz½oleges n i (n)
0 id½opontban
= P (Xn = i); i 2 X
jelöli a Markov-lánc eloszlását. Ekkor (0) = ( i (0) = pi ; i 2 X ) a kezdeti eloszlás. De…níció 26 Egy = ( i ; i 2 X ) eloszlást stacionárius eloszlásnak nevezünk, ha kezdeti eloszlásnak választva, tetsz½oleges n 0 id½opontban fennáll a i (n) = i ; i 2 X azonosság. Ezt az eloszlást szokás egyensúlyi eloszlásnak is nevezni. 49
Markov-láncok vizsgálatánál az egyik legfontosabb feladat a stacionárius eloszlás létezésének bizonyítása és ezután az eloszlás meghatározása. Míg az 21. Tétel az átmenetvalószín½uségek konvergenciájával foglalkozott, itt a (n) id½ot½ol függ½o eloszlás n ! 1 melletti határértékének létezésével fogunk foglalkozni, amely ha létezik, egyben megadja a stacionárius eloszlást is. Igaz a következ½o tétel, melynek bizonyításától elzekintünk. Tétel 24 Legyen az X homogén Markov-lánc irreducibilis, visszatér½o és aperiodikus. (A) Ekkor tetsz½oleges állapot esetén létezik a i
= lim
n!1
i (n)
=
1 j
határérték, amely nem függ a kezdeti eloszlástól. (B) Ha minden állapot visszatér½o nullaállapot, akkor nem létezik stacionárius eloszlás és minden i 2 X -re fennáll i = 0. Ha minden állapot visszatér½o nemnullaállapot, akkor létezik a = ( i ; i 2 X ) stacionárius eloszlás és minden i 2 X -re i = 1= i > 0. Ekkor a stacionárius eloszlás egyértelm½uen meghatározható a következ½o lineáris egyenletrendszerb½ol X (8.1) i = 1; i2X
i
=
X
j pji ;
j2X
i 2 X:
(8.2)
Következmény 3 Mivel a Markov-lánc irreducibilis, ezért a (B) részben a pozitív visszatér½oséget elegend½o egy állapotra megkövetelni, innen automatikusan következik a többi állapotra is. A tétel (8.2) egyenlete átírható a könnyebben áttekinthet½o = mátrix alakba is, ahol = ( 0 ; 1 ; :::) és a homogén Markov-lánc egylépéses átmenetvalószín½uség-mátrixa. Az (8.1), illetve (8.2) egyenletekben nem játszik semmiféle szerepet a kezdeti eloszlás, ezért világos, hogyha létezik a stacionárius eloszlás, akkor az független a kezdeti eloszlástól és csakis a átmenetvalószín½uség-mátrixtól függ.
Iterációs eljárás a stacionárius eloszlás meghatározására. Abban az esetben, amikor létezik stacionárius eloszlás, egyszer½uen bizonyítható, hogy kielégíti a (8.2) lineáris egyenletrendszert. Ugyanakkor ez a megközelítés egy iterációs eljárást is kínál (ld. az (8.3) egyenletet alább). Ez az eljárás különösen véges állapottér esetén jól alkalmazható.
50
A homogén Markov-lánc tetsz½oleges n = 0; 1; ::: id½opontbeli eloszlására fennáll a (n) = (n 1)
(n) = (
0 (n);
1 (n); :::)
egyenletet. Megismételve ezt az összefüggést adódik, hogy tetsz½oleges kiinduló (0) érték mellett (n) = (0) n ; n = 0; 1; ::: (8.3) Minthogy feltettük, hogy létezik a
stacionárius eloszlás, ezért írhatjuk, hogy = lim (n); n!1
így a lim (n) = lim (n
n!1
n!1
1)
egyenletb½ol következik . = De…níció 27 Egy állapotot a Markov-lánc ergodikus állapotának nevezzük, ha az i állapot aperiodikus és visszatér½o nemnullaállapot (d(i) = 1; fii = 1; i < 1). Azt mondjuk, hogy a Markov-lánc ergodikus, ha minden állapota ergodikus. A fentiek szerint a tételbeli tulajdonságokkal rendelkez½o, pozitív visszatér½o Markov-lánc mindig ergodikus. Mivel egy homogén, véges állapotter½u, irreducibilis Markov-lánc mindig pozitív visszatér½o, ezért igaz az alábbi állítás is. Tétel 25 Egy véges állapotter½u, homogén, irreducubilis Markov-lánc mindig ergodikus. Markov-láncok gyakorlati alkalmazásában az ergodikus eloszlások alapvet½o szerepet játszanak. Egy Markov-lánc esetén az átmenetvalószín½uségek aritmetikai tulajdonságai alapján általában egyszer½uen eldönthet½o az irreducibilitás és aperiodikusság tulajdonsága, míg azt a kérdést sokszor nehéz megválaszolni, hogy a Markov-lánc pozitív visszatér½o-e? Az alábbiakban megadunk bizonyítás nélkül három tételt, melyek elégséges feltételeket biztosítanak az ergodikus eloszlás létezésére homogén, irreducibilis, aperiodikus Markov-láncok esetén, ezenkívül az els½o tétel véges állapotú Markov-láncok esetén a (8.3) iterációs eljárás konvergenciasebességére is becslést ad. Legyen tehát az X = f0; 1; :::g állapotter½u X Markov-lánc homogén, irreducibilis és aperiodikus. Tétel 26 (Bernstein) Tegyük fel, hogy létezik olyan i0 2 X és teljesül a pii0 egyenl½otlenség. Ekkor lim pij (n) =
j;
i; j 2 X ;
= ( i ; i 2 X ) jelöli az ergodikus eloszlást, továbbá X jpij (n) 2(1 jj
)n ; n
n!1
ahol
> 0; hogy minden j 2 X állapot mellett
i2X
51
1:
Tétel 27 (Klimov) Ha az X = f0; 1; :::g állapotokhoz található olyan nemnegatív g(i); i 2 X függvény, valamint " > 0; i0 2 X állapot, hogy 1 valószín½uséggel teljesül E(g(Xn+1 )j Xn E(g(Xn+1 )j Xn
= i) g(i) "; i i0 ; n = i) < 1; i 0; n 0
0
akkor az X Markov-lánc ergodikus.
Tétel 28 (Foster) Legyen az X = f0; 1; :::g állapotter½u homogén Markov-lánc irreducibilis és aperiodikus. Feltesszük, hogy léteznek olyan a; b > 0 és ` 0 konstansok, melyekre teljesülnek az alábbi egyenl½otlenségek E(Xn+1 j Xn E(Xn+1 j Xn
= i) = i)
a; i `; i b; i > `:
Ekkor az X Markov-lánc ergodikus.
Ergodikus tétel Markov-láncra. Legyen az X homogén, irreducibilis, pozitív visszatér½o Markov-lánc X = f0; 1; :::g állapottérrel. Tekintsünk egy tetsz½olegesen rögzített i 2 X állapotot és nézzük meg annak relatív gyakoriságát, hogy egy megadott T hosszúságú id½ointervallumon a folyamat az id½o hányad részében tartózkodik az i állapotban. Jelölje Si (T ) =
T X
I(Xn = i);
n=0 T 1X 1 S i (T ) = I(Xn = i) = Si (T ): T T n=0
A legfontosabb kérdés ami itt felmerül az, hogy létezik-e valamilyen értelemben határértéke az S i (T ) valószín½uségi változóknak T ! 1 mellett? Ahhoz, hogy ennek a problémának a valószín½uségelméleti hátterét megvilágítsuk, vezessük be a következ½o jelöléseket: Jelölje azokat (i) (i) 0 T1 < T2 < ::: az egymást követ½o véletlen id½opontokat, amelyekben a Markov-lánc az i állapotba kerül, vagyis az i állapot els½o elérési, illetve visszatérési id½opontjainak sorozatát. Ez azt jelenti, hogy (i) (i) (i) X(Tn ) = i és X(k) 6= i, ha k 6= T1 ; T2 ; ::: Jelölje (i) (i) 1 ; 2
(i)
= T2
(i)
T1 ; :::
az els½o elérési, illetve az egymást követ½o visszatérési id½ohosszakat. A Markov-tulajdonság miatt - ahogyan ezt már korábban megjegyeztük - ezek a valószín½uségi változók függetlenek és (i) f n ; n 2g 52
azonos eloszlásúak is. A közös eloszlás nem más, mint az ffii (n); n
1g
n-lépéses visszatérési valószín½uségek. (i) Ha a folyamat a 0 id½opontban az i állapotból indul ki, akkor 1 eloszlása is megegyezik a többiével. Heurisztikusan világos, hogyha a visszatérési id½o várható értéke i , akkor T id½o alatt átlagosan T = i -szer tér vissza az i állapotba, vagyis átlagosan ennyiszer tartózkodik a folyamat az i állapotban és így az S i (T ) mennyiség 1= i körül ingadozik. Ez a körülmény természetesen matematikailag egzakttá tehet½o és általánosabban is megfogalmazható. Tétel 29 Ha X homogén, irreducibilis, pozitív visszatér½o Markov-lánc, akkor 1 valószín½uséggel igaz a következ½o konvergencia lim S i (T ) =
T !1
1 i
;i 2 X:
A Markov-tulajdonság következtében nemcsak a visszatérési id½ointervallumok, mint valószín½uségi változók függetlenek egymástól, hanem az egymást követ½o visszatérési id½ointervallumokon az egyes folyamatszakaszok is. Ez lehet½ové teszi az el½oz½o tételnél jóval általánosabb eredmények bizonyítását is.
53
Téma 9
Folytonos idej½u Markov-láncok Folytonos idej½u Markov-láncok. Poisson-folyamat. Születési-halálozási folyamatok. MjMj1 típusú tömegkiszolgálási rendszerek. Folytonos idej½u fXt ; t 0g Markov-láncot hasonló módon de…niáljuk, mint a diszkrét idej½ut, csak arra kell tekintettel lenni, hogy a Markov-tulajdonságot megfelel½o módon írjuk el½o a folytonos id½oparaméter esetén. Hasonlóan a diszkrét idej½u esethez itt is feltesszük, hogy az X állapottér a véges f0; 1; :::; N g; vagy f0; 1; :::g megszámlálhatóan végtelen sok nemnegatív egész értékekb½ol áll. De…níció 28 Azt mondjuk, hogy az fXt ; t 0g sztochasztikus folyamat X állapotter½u folytonos idej½u Markov-lánc, ha teljesíti a következ½o (un. Markov-) tulajdonságot: tetsz½oleges pozitív egész n érték, 0 t0 < t1 < ::: < tn és i0 ; :::; in 2 X esetén, melyekre teljesül P (Xtn 1 = in 1 ; :::; Xt0 = i0 ) > 0; fennáll P (Xtn = in j Xtn
1
= in
1 ; :::; Xt0
= i0 ) = P (Xtn = in j Xtn
1
= in
1 ):
(9.1)
Poisson-folyamat, mint folytonos idej½u Markov lánc. Tétel 30 Legyen Nt homogén folyamat Markov-láncot alkot.
intenzitású Poisson-folyamat, N0 = 0. Ekkor az Nt Poisson-
Bizonyítás. Legyen n > 0, 0 i1 ::: in+1 tetsz½oleges egész számok és t0 = 0 < t1 < ::: < tn+1 tetsz½olegesen választott értékek. Látható, hogy P (Ntn+1 = in+1 jNtn = in ; :::; Nt1 = i1 ) = P (Ntn+1 = in+1 ; Ntn = in ; :::; Nt1 = i1 ) = = P (Ntn = in ; :::; Nt1 = i1 ) P (Ntn+1 Ntn = in+1 in ; :::; Nt2 Nt1 = i2 = P (Ntn Ntn 1 = in in 1 ; :::; Nt2 Nt1 = i2 54
i1 ; Nt1 = i1 ) i1 ; Nt1 = i1 )
Mivel a Poisson-folyamat független növekmény½u folyamat, ezért az utolsó tört átírható a következ½o alakba P (Ntn+1 Ntn = in+1 in ) P (Ntn Ntn 1 = in in 1 ) P (Ntn+1 Ntn = in+1 in ) = P (Ntn Ntn 1 = in in 1 ) P (Ntn+1 Ntn = in+1 in ) = P (Ntn Ntn 1 = in in 1 ) = P (Ntn+1 Ntn = in+1 in ):
=
::: ::: ::: ::: ::: :::
P (Nt2 P (Nt2 P (Nt2 P (Nt2 P (Nt2 P (Nt2
Mivel Nt független növekmény½usége miatt az Ntn+1 Ntn ) események függetlenek, ezért P (Ntn+1
Ntn = in+1
in ) = P (Ntn+1
N t1 Nt1 N t1 Nt1 N t1 Nt1
= i2 = i2 = i2 = i2 = i2 = i2
i1 )P (Nt1 i1 )P (Nt1 i1 )P (Nt1 i1 )P (Nt1 i1 )P (Nt1 i1 )P (Nt1
= i1 ) = = i1 ) = i1 ) = = i1 ) = i1 ) = = i1 )
Ntn = in+1
in és Ntn = in (Nt
Ntn = in+1
in jNtn = in ) =
= P (Ntn+1 = in+1 jNtn = in );
N0 =
így összegezve kaptuk P (Ntn+1 = in+1 jNtn = in ; :::; Nt1 = i1 ) = P (Ntn+1 = in+1 jNtn = in );
Folytonos idej½u Markov-láncok jellemzése Vezessük be a pij (s; t) = P (Xt = jj Xs = i); 0 egyenlet átírható a következ½o alakba: P (Xtn = in j Xtn
1
= in
1 ; :::; Xt0
s < t; i; j 2 X jelölést, ekkor az (9.1) = i0 ) = pin
1; in
(tn
1 ; tn ):
De…níció 29 A pij (s; t) függvényt fXt ; t 0g Markov-lánc átmenetvalószín½uség függvényének, a pij (s; t) elemekb½ol alkotott (s; t) = [pij (s; t)]i;j2X mátrixot pedig a Markovlánc átmenetvalószín½uség mátrixának nevezzük.. De…níció 30 Az fXt ; t
0g Markov-láncot (id½oben) homogénnak nevezzük, ha pij (s; s + t) = pij (t); i; j 2 X ; s; t
Megjegyzés 19 Az el½oz½o de…níció átírható a tömörebb (s; s + t) = alakba. 55
(t); s; t
0
0;
Fontos jellemz½oje a Markov-láncnak a P (t) = (P0 (t); P1 (t); :::); t
0
id½ot½ol függ½o eloszlás, ahol Pi (t) = P (Xt = i); i 2 X . De…níció 31 A P (0) értékét kezdeti eloszlásnak nevezzük. A továbbiakban csak homogén Markov-láncokkal foglalkozunk, ezért az összefüggéseket csak erre az esetre adjuk meg. Hasonlóan a diszkrét idej½u esethez, folytonos idejú homogén Markov-láncokra is igaz és
P (s + t) = P (s) (t),
(s + t) =
(s) (t), s; t
0:
Az els½o egyenlet szerint tetsz½oleges t > 0 id½opontra P (t) = P (0) (t); ami azt jelenti, hogy a kezdeti eloszlás és az átmenetvalószín½uség egyértelm½uen meghatározza a Markov-lánc eloszlását. A második egyenlet a diszkrét idej½u Markov-láncéval analóg Chapman-Kolmogorov-egyenlet, amely kifejtve a következ½ot jelenti P pij (s + t) = pik (s)pkj (t); s; t 0: k2X
Vizsgálataink során azzal a feltevéssel élünk, hogy teljesül a lim pij (h) = pij (0) =
h!0+
ij ;
i; j 2 X
(9.2)
feltétel, ahol ij .a Kronecker-féle -függvény (értéke 1, ha i = j, és 0;ha i 6= j). A (9.2) feltételb½ol következik, hogy tetsz½olegesen rögzített t és h ! 0; t + h > 0 mellett fennáll lim
P (Xt+h = Xt ) = 1:
h!0; t+h>0
Ez az Xt folytonos idej½u Markov-lánc sztochasztikus folytonosságát jelenti, vagyis "nagyon rövid id½o alatt" az Xt folyamat "nagy valószín½uséggel" nem változtatja meg az állapotát. A (9.2) feltétel mellett bizonyítható, hogy: 1. pij (t); 0
t < 1 egyenletesen folytonos
2. Tetsz½oleges i 2 X esetén létezik a véges, vagy végtelen qi = lim
1
pii (h) = h
h!0+
p0ii (0)
határérték.A qi mennyiség elnevezése: az i állapotból való távozás intenzitása. Itt megjegyezzük, hogy a Markov-lánc fontos jellemz½oi a qii = qi ; i 2 X mennyiségek.
56
3. Tetsz½oleges i; j 2 X , i 6= j mellett létezik pij (h) h!0+ h
qij = lim
határérték. A qij mennyiséget az i állapotból a j állapotba való átmenet intenzitásának nevezzük. 4. Vezessük be a Q = [qij ]i;j2X = p0ij (0)
i;j2X
:=
0
(0)
jelölést. A Q mátrixot a folytonos idej½u Markov-lánc in…nitezimális-, vagy rátamátrixának nevezzük. A továbbiakban feltesszük, hogy a Markov-láncra teljesül a qi < 1; i 2 X
(9.3)
feltétel. Ekkor látható, hogy P (Xt+h 6= ij Xt = i) = qi h + o(h); h ! 0;
P (Xt+h = jj Xt = i) = qij h + o(h); h ! 0; j 6= i: 5. Ha a folytonos idej½u Markov-lánc teljesíti a (9.3) feltételt, akkor fennáll a következ½o di¤erenciálegyenlet 0 (t) = Q (t); (9.4) amely egyértelm½uen meghatározza az átmenetvalószín½uséget tetsz½oleges id½ointervallumon.
Folytonos idej½u Markov-lánc konstrukciója a (9.3) feltétel teljesülése esetén Ez a konstrukció a szimulációs módszerek alkalmazásánál egyben egy algoritmust is jelent ilyen folyamatok modellezésére.
K4
K0
K2 K1 K3
S0
S1 T1
S2
S3
T2
T3
1. ábra
57
S4 T4
Feladat: konstruálni olyan fXt ; t 0g folytonos idej½u Markov-láncot, amely 1 valószín½uséggel jobbról folytonos lépcs½os folyamat, lkezdeti eloszlása P (0) = (P0 (0); P1 (0); :::); átmenetvalószín½uség mátrixa (t) = [pij (t)] ; t 0 valamint teljesül az átmenetvalószín½uségek által meghatározott qi mennyiségekre a (9.3) feltétel. De…niáljuk az S0 ; S1 ; :::véletlen hosszúságú id½ointervallumokat, a Tm = S0 +:::+Sm 1 ; m = 1; 2; ::: véletlen id½opontokat és a nemnegatív egész értékeket felvev½o K1 ; K2 ; :::v.v.-kat a következ½o eljárással: (a) Válasszuk meg a K0 v.v.-t a P (0) eloszlás szerint, vagyis álljon fenn P (K0 = k) = Pk (0); k 2 X , továbbá legyen S0 exponenciális eloszlású v.v. a K0 -tól függ½o qK0 paraméterrel. (b) Vegyünk egy P (1) = P (T1 ) = (pK0 ;j (0); j 2 X ) eloszlású K1 v.v.-t és legyen a S1 v.v. eloszlása qK1 paraméter½u exponenciális. (c) Az m-edik lépésben (m = 2; 3; :::) hasonló módon választunk egy P (m) = P (Tm ) = (pK0 ;j (Sm ); j 2 X ) eloszlású Km és egy qKm paraméter½u exponenciális eloszlású Sm v.v.-t. (d) Utolsó lépésben de…niáljuk az fXt ; t Xt = K0 ;
0g sztochasztikus folyamatot a következ½o módon:
ha 0
t < S0 ;
Xt = Km ; ha Tm
t < Tm+1 ; m = 1; 2; :::
Tétel 31 A fenti módon meghatározott fXt ; t 0g sztochasztikus folyamat P (0) kezdeti eloszlással és (t); t 0 átmenetvalószín½uség mátrixszal rendelkez½o folytonos idej½u Markovlánc.
58
Téma 10
Születési-halálozási folyamatok
0
1
3
q1
k
q2
q3
qk
k+1
qk+1
qk+2
pk
pk+1
•••
q0
p0
p1
p2
pk-1
2. ábra
De…níció 32 Az fMt ; t folyamatnak nevezzük, ha
0g jobbról folytonos sztochasztikus folyamatot születési-halálozási
1. értékeinek (állapotainak) halmaza I = f0; 1; 2; :::g; 2. egy k 2 I állapotban eltöltött tartózkodási id½o eloszlása k
= ak + b k ;
ak
0; bk
0;
k
>0
paraméter½u exponenciális eloszlás, s a tartózkodási id½o nem függ az ebbe az állapotba kerülésig terjed½o trajektóriától; 3. tetsz½oleges k 2 I, k 1 állapotból pk = akk , ill. qk = 1 pk = bkk valószín½uséggel megy át a folyamat a (k + 1), ill. (k 1) állapotba. A 0 állapotból az 1 állapotba p0 valószín½uséggel lép, míg q0 = 1 p0 valószín½uséggel marad ott; 4. adott a Pk (0) = P (M0 = k) = 'k ; k 2 I kezdeti eloszlás. Ekkor az fMt ; t 0g folyamat megszámlálható állapotter½u, folytonos idej½u homogén Markov-folyamatot alkot. Az ak , ill. bk állandókat születési, ill. halálozási intenzitásoknak, a k értéket pedig populáció nagyságnak nevezzük. Speciális esetek: 59
ha ak 0, akkor tiszta halálozási-, ha bk beszélünk.
0 , akkor tiszta születési folyamatról
Az fMt ; t 0g folyamat fMm ; m 0g diszkrét idej½u beágyazott Markov-láncán az állapotoknak azt a sorozatát értjük, melyeket a folyamat az ugrások pillanataiban felvesz. Ennek átmenetvalószín½uségi mátrixa 2 3 q0 p 0 0 0 0 6q1 0 p1 0 0 7 6 7 60 q 7 2 0 p2 0 6 7 60 0 q 7 0 p 3 3 4 5 .. .. .. .. .. . . . . . . . . A születési-halálozási folyamatokra vonatkozó néhány eredmény Jelölje tetsz½oleges k
0 és Re s > 0 mellett
0, t
Pk (t) = P (Mt = k);
pk (s) =
Z1
e
st
Pk (t) dt;
Pk (0) = P (M0 = k) = 'k :
0
Tétel 32 Legyen p0 = 1; 0 < pk < 1; k
1. Ekkor a következ½o állítások igazak:
(a) A Pk (t) függvények kielégítik a következ½o di¤erenciálegyenlet rendszert P00 (t) =
a0 P0 (t) + b1 P1 (t);
Pk0 (t) = ak
1 Pk 1 (t)
(ak + bk )Pk (t) + bk+1 (t)Pk+1 (t);
k
1:
(b) Legyen adva a 'k ; k 0 kezdeti eloszlás. Akkor tetsz½oleges Re s > 0 esetén a pk (s) függvényekre fennáll a következ½o lineáris egyenletrendszer sp0 (s)
'0 =
spk (s)
' k = ak
(c) Tetsz½oleges k
a0 p0 (s) + b1 p1 (s); 1 pk 1 (s)
(ak + bk )pk (s) + bk+1 pk+1 (s);
k
1:
0 esetén léteznek a lim Pk (t) =
t!1
k
határértékek, amelyek nem függnek a Mt folyamat kezdeti eloszlásától. Emellett 0; k = 0; k 1 P a0 a1 ak 1 1. Ellenkez½o esetben ha a k sor divergens, ahol 0 = 1 és k = b1 b2 bk ; k k=0
k
> 0; k
0;
k
=
k 0;
1 X k=0
60
k
= 1:
(10.1)
Hasonló jelleg½u eredmények adódnak abban az esetben, amikor Mt véges f0; 1; 2; : : : ; ng állapotter½u születési-halálozási folyamat. Például a p0 = 1; 0 < pk < 1, ha 1 k n 1 és pn = 0 kezdeti feltétel mellett igaz a következ½o összefüggés: Tetsz½oleges 0 k n esetén léteznek a lim Pk (t) =
t!1
határértékek és emellett j
=
j 0;
ahol 0
= 1;
j
=
0
k
0
=@
a0 a1 b1 b2
>0
n X j=0
j
1
1
A
aj 1 ; 1 bj
;
j
n:
Megjegyzés 20 A konstans > 0 születési intenzitású tiszta születési folyamat nem más, mint a intenzitású Poisson-folyamat. Speciális eset: ai = ; i
j
0; bi = ; i 1; = = < 1. Ekkor 1 1 0 1 1 X 1 jA j @ = =1 = ; 0= 1
:
j=0
MjMj1 tömegkiszolgálási rendszer A Markov-típusú TKR-ek a legegyszer½ubb és legjobban vizsgált TKR-ek osztálya. Ilyen rendszerek vizsgálati módszere azon alapszik, hogy az alapvet½o sztochasztikus folyamatok, amelyekkel jellemzik az adott TKR-t, Markov-folyamatok lesznek, s ez a tény megengedi az erre vonatkozó fejlett elmélet alkalmazását. Ennek eredményeként különböz½o (analitikus) formulákat kaphatunk a vizsgált jellemz½ore - az id½o függvényében, vagy stacionárius üzemmódban.
Az MjMj1 tömegkiszolgálási rendszer leírása Legyen az egymás utáni beérkezések közötti id½ohosszak eloszlása a > 0 paraméter½u A(x) = 1 e ax , míg a kiszolgálási id½ok eloszlása b > 0 paraméter½u B(x) = 1 e bx exponenciális, a kiszolgálási elv legyen FCFS. A beérkezési- és kiszolgálási id½okr½ol feltesszük, hogy egymástól független valószín½uségi változók.
61
b paraméterű exponenciális eloszlású kiszolgálási idők igények beérkezése között eltelt időtartamok eloszlása: a paraméterű exponenciális
távozó igények
3. ábra
Jelölje L(t) a t 0 id½opontban a rendszerben tartozkodó igények számát. Az adott TKR esetén a következ½okkel fogunk foglalkozni. (A) Belátjuk, hogy fL(t); t
0g születési-halálozási folyamat, meghatározzuk paramétereit.
(B) Megadjuk L(t) eloszlását tetsz½oleges t (C) Megadjuk az L(t) sorhosszúság
k
0 id½opontban .
= lim P (L(t) = k); k t!1
0 határeloszlását.
(A) Legyen t olyan id½opont, amikor a rendszer éppen üressé válik. Ebben az id½opontban nyilvánvalóan fennáll L(t) = 0: Ezután a rendszer állapotváltozása pontosan akkor következik be, amikor egy igény beérkezik. Az állapotváltozásig eltelt id½o eloszlása (ami megegyezik a 0 állapotban való tartózkodás eloszlásával) a > 0 paraméter½u exponenciális - a feltételünk szerint, így a0 = a;
p0 = 1:
Megjegyezzük, hogy mivel az exponenciális eloszlás emlékezetnélküli, ezért ha tetsz½oleges t0 id½opontban a rendszer a 0 állapotban van, akkor az abban való tartózkodás eloszlása A(x), bármikor is került ebbe az állapotba a rendszer a t0 id½opontot megel½oz½oen. Ugyanez elmondható tetsz½oleges k 0 állapotról is. Tegyük fel most, hogy a rendszer a t id½opontban a k; k 1 állapotban van. A rendszerben állapotváltozás akkor következik be, amikor egy új igény belép, vagy egy bennlév½o igény távozik (annak a valószín½usége, hogy ez egy id½opontban történik, éppen 0-val egyenl½o az eloszlások folytonossága miatt). Jelölje t - a soronkövetkez½o igény beérkezéséig eltelt id½ot, t - a rendszerben éppen kiszolgálás alatt lev½o igény hátralév½o idejét. 62
Világos, hogy t és Jelölje t = min( t ; könnyen kiszámítható: P(
t
t
függetlenek, eloszlásuk A(x), ill. B(x). t ) az állapotváltozás bekövetkeztéig eltelt id½ot. Ekkor
< x) = 1
P(
t
x) = 1
P(
= 1
P(
t
x)P (
x) = 1
t
x;
t
eloszlása
x) =
t
e
t
(a+b)x
;
így a születési-halálozási folyamat fenti jelölései mellett k = a + b; k 1 (a k állapotban az exponenciális eloszlású tartózkodási id½o paramétere). A t id½o eltelte után a rendszer átmegy a (k + 1), vagy a (k 1) állapotba attól függ½oen, hogy t < t , vagy t > t (P ( t = t ) = 0; mivel t és t folytonos eloszlású v.v.-k). Világos, hogy P(
t
< x;
t
<
t)
= P ( t < x; t < t ) = Zx = P ( t < x; t < t j t = u)f t (u)du = 0
=
Zx
P(
> u)ae
t
au
du =
0
Zx
e
bu
ae
au
du =
0
a (1 = a+b
e
(a+b)x
)
és hasonlóan adódik b (1 e (a+b)x ): a+b Innen látható, hogy függetlenül k értékét½ol, a k állapotban való tartózkodás eloszlása 1) állapotba való átmenet k = (a + b) paraméter½u exponenciális, a (k + 1), ill. (k valószín½usége a b pk = ; ill: qk = (k 1): a+b a+b A fenti összefüggésekb½ol tehát az következik, hogy L(t) születési-halálozási folyamat, melynek paraméterei (a korábban alkalmazott jelölésekkel) P(
t
< x;
t
t)
= P(
ak = a; k k
t
< x)
R(
t
< x;
t
<
t)
=
0; bk = b; k
1; a b = a + b; p0 = 1; pk = ; qk = ; k a+b a+b
1:
(10.2)
(B) Az L(t); t 0 sorhosszúság id½ofügg½o eloszlásának meghatározása. Feltesszük, hogy a rendszer üres a 0 id½opontban, azaz L(0) = 0 1 valószín½uséggel ('0 = 1, 'k = 0; k 1) és vizsgáljuk a Pk (t) = P (L(t) = k);
pk (s) =
Z1 0
63
e
st
Pk (t)dt; Re s > 0
függvényeket. Ebben az esetben a pk (s) függvények a 32. tétel b) pontja segítségével írhatók le: sp0 (s) spk (s) = apk
1= 1 (s)
ap0 (s) + bp1 (s);
(10.3)
(a + b)pk (s) + bpk+1 (s); k
Vezessük be a p(z; s) =
1 X
1:
(10.4)
pk (s) z k
k=0
generátorfüggvényt. Szorozzuk be (10.4) mindkét oldalát z k -nal (0 < jzj szerint, ekkor a következ½o egyenlethez jutunk: sp(z; s)
sp0 (s) = azp(z; s)
(a + b)[p(z; s)
1; k
1 p0 (s)] + b[p(z; s) z
1) és összegezzük k
p0 (s)
zp1 (s)]:
Hozzáadva az (10.3) egyenletet, majd átrendezve kapjuk P (z; s) s
az + (a + b)
ahonnan p(z; s) = Tetsz½oleges Re s > 0 esetén a p(z; s); jzj Bessel-függvényt, azaz legyen Jm (z) =
z sz
b = 1 + bp0 (s) z
b p0 (s); z
b(1 z)p0 (s) : (1 z)(b az)
1 függvény korlátos . Jelölje Jm (z) az els½orend½u módosított 1 X
k=0
1 k! (m + k + 1)
z 2
m+2k
:
Analitikus módszereket használva, hosszas számolás után formula nyerhet½o a Pk (t) függvények pk (s) Laplace-transzformáltjaira, ahonnan a pk (s) a Pk (t) függvények között fennálló kölcsönösen egyértelm½u megfeleltetés következtében nyerhet½o a Pk (t) =
1 a
a b
k+1
e
(a+b)t
1 X
mt
1
m=k+1
b a
m=2
p Jm (2 abt):
összefüggés. Megjegyzés 21 Az utóbbi eredményb½ol érzékelhet½o, hogy még az igen egyszer½u MjMj1 típusú tömegkiszolgálási rendszer esetén is milyen nehézségekbe ütközik a sorhosszúság eloszlásának id½ofügg½o megoldása. A legt½obb esetben analitikus formula egyáltalán nincs az id½ofügg½o eloszlásra és csak közelit½o modellel, vagy szimulációs módszerrel vizsgálható.
(C) Az (10.1) és (10.2) összefüggésekb½ol közvetlenül kapjuk a határeloszlásra 0
=
1 P
k=0
a b
k
1
=1
a ; b
k
=
0
a b
k
; k
0:
Megjegyzés 22 Az M jM j1 rendszerrel teljesen analóg módon vizsgálható az M jM j1 rendszer és ugyanolyan módon látható be, hogy ebben az esetben is az L(t) folyamat születésihalálozási folyamat lesz, melynek paraméterei p0 = 1; ak = a; k k
0; bk = kb; k 1; a kb = a + kb; pk = ; qk = ; k a + kb a + kb 64
1:
Az M jM j1 rendszerre igaz 1 a k a=b e ; k 0; k! b n a o 1 a Pk (t) = exp (1 e bt ) (1 b k! b k
=
e
bt
k
)
;
k
0:
Megjegyzés 23 Egy és ugyanaz az L(t) folyamat jelenhet meg egyszerre az M jM j1 és M jM j1 rendszerben, ha az M jM j1 rendszerben a kiszolgálás intenzitása bn = nb (azaz függ a rendszerben lev½o igények számától). A többi rendszerjellemz½or½ol ez nem mondható el. Megjegyzés 24 Születési-halálozási folyamat lesz L(t) az M jM jnj1, M jM jnjm, 0 m < 1 rendszerek esetén is. Az M jM jnj0 rendszerre az L(t) folyamat 0; 1; :::; n állapotter½u születési-halálozási folyamat, melynek paraméterei p0 = 1;
0
= a;
j
= a + jb; pj =
n
= nb; pn = 0:
jb a ; qj = ; 1 a + jb a + jb
j
n
1;
Ekkor létezik stacionárius eloszlás (0 < a < 1; 0 < b < 1 tetsz½oleges) és 0 1 1 n a k 1 @X 1 a j A ; 0 k n: k = b k! j! b j=0
65
Téma 11
Az MjGj1 típusú tömegkiszolgálási rendszer Sorhosszúság, foglaltsági/szabad periodusok vizsgálata az MjGj1 rendszerben
A rendszer leírása Feltételek: 1. A rendszer a vizsgálat kezdetét jelent½o t0 id½opillanatban üresen kezd dolgozni. Az egyszer½uség kedvéért feltesszük, hogy t0 = 0. 2. Az fN (t); t t0 g beérkezési folyamat, amely a rendszerbe egymás után érkez½o igények beérkezési id½opontjait írja le, > 0 intenzitású Poisson-folyamat. 3. Egy kiszolgáló egység van, amely nem romlik el és képes arra, hogy egy igény kiszolgálása után egy másik igény kiszolgálását azonnal megkezdje. Ha egy igény olyan id½opontban érkezik a rendszerbe, amikor a kiszolgáló egység foglalt, az igény sorbanáll. A várakozási helyek száma nem korlátozott. 4. A kiszolgálási elv: FCFS (ebben az esetben megegyezik a FIFO kiszolgálási elvvel). 5. A kiszolgálási id½ok függetlenek egymástól, és a beérkezési folyamattól, azonos eloszlásúak közös P (Y < x) = B(x) eloszlásfüggvénnyel, melyre EY = < 1. A rendszer m½uködését sematikusan az 1. ábra mutatja be: A rendszer vizsgált jellemz½oje az fL(t); t 0g sorhosszúság, azaz a t id½opontban a rendszerben tartózkodó igények száma. Legyen L(t) jobbról folytonos, azaz L(t) = L(t + 0); t 0. Sok tömegkiszolgálási rendszer esetén alapvet½o feladat azoknak a kérdéseknek megválaszolása, hogy milyen a sorhosszúság eloszlása, létezik-e annak határeloszlása és az hogyan határozható meg, mennyi a rendszerben tartózkodó igények átlagos száma, stb. Ennek a résznek a tárgya az L(t) sorhosszúság t ! 1 melletti aszimptotikus eloszlásának vizsgálata.
Vezessük be a következ½o jelöléseket (a 2. ábra szemlélteti a tömegkiszolgálási rendszer m½uködését). Feltesszük, hogy a rendszer üres a 0 id½opontban, azaz L(0) = 0.
66
B(x) eloszlású kiszolgálás
igények beérkezése: λ intenzitású Poissonfolyamat
távozó igények
1. ábra
– X1 - az els½o igény beérkezési id½opontja, Xn pedig az (n beérkezése között eltelt id½o; – tn = X1 + ::: + Xn (n
1)-ik és n-ik sorszámú igény
1) - az n-ik igény beérkezési id½opontja;
– Yn - az n-ik igény kiszolgálási ideje; – rn ; n
1 - az n-ik igény kiszolgálásának kezd½opontja;
– sn ; n 1 - az n-ik igény rendszerb½ol való távozásának id½opontja (ebben az id½opontban fejez½odik be az n-ik igény kiszolgálása a rendszerben). A rendszer m½uködésének az ábrázolása
67
s1 L
r1
s2
r2 Y1
r3 Y2
s3
s4
r4
r5
Y3
Y4
4 3 2 1 t 0
t 1 t2
t3
t4
t5
t6
2. ábra
A feltételeink szerint f(Xn ; Yn ); n 1g független, azonos eloszlású v.v.-k sorozata, ahol a vektorok komponensei is függetlenek, továbbá az Xn ; n 1 beérkezési id½oközök eloszlása paraméter½u exponenciális, míg az Yn ; n 1 kiszolgálási id½ok eloszlásfüggvénye B(x). Az is világos, hogy a ftn ; n 1g sorozat nem más, mint az N (t) Poisson-folyamat ugrási helyeinek sorozata.
Az MjMj1 és MjGj1 rendszerek közötti f½obb eltérések Az MjMj1típusú rendszereknél mind a beérkezési id½oközök, mind pedig a kiszolgálási id½ok független, exponenciális eloszlású v.v.-k. Ugyanakkor ezek az eloszlások rendelkeznek az emlékezetnélküliség tulajdonságával, ahonnan levezethet½o az, hogy az fL(t); t 0g sorhosszúság folyamat Markov (születési-halálozási folyamat). Ez a tény jelent½osen megkönnyíti és leegyszer½usíti az adott TKR vizsgálatát. Az MjGj1 TKR-ben vizsgált folyamatok (sorhossz, várakozási id½o, stb.) nem feltétlenül alkotnak Markov-folyamatot, mivel a kiszolgálási id½o eloszlása már nem feltétlenül emlékezetnélküli. Így a vizsgálatuk a korábbiaktól eltér½o módszerek használatát igényli. A fenti feltételek tehát már nem feltétlenül biztosítják, hogy L(t) Markov-folyamat, azonban egy segédváltozó bevezetésével Markov-folyamattá egészíthetjük ki. Ha Y0 (t) jelöli azt, hogy a kiszolgálóegységen lév½o igény kiszolgálása már mennyi id½ot vett igénybe a t id½opillanatig (Y0 (t) legyen jobbról folytonos), akkor az f(L(t); Y0 (t)); t 0g vektorfolyamat már Markov és így tekinthet½o a TKR állapotvektoraként.
68
Általában a rendszer m½uködését adott szempontból leíró W (t) (t 0 ) vektort a rendszer egy állapotvektorának nevezzük, ha tetsz½oleges t > t mellett W (t) értékéb½ol és a (t; t] intervallumon meg…gyelt beérkezésekb½ol meghatározható a W (t) vektor. Az MjMj1 rendszerhez képest a különbség nem csak abban van, hogy itt a rendszer állapotát egy vektorfolyamattal tudjuk megadni, hanem - és ez lényeges különbséghez vezet - az állapottér már nem lesz diszkrét, mivel Y0 (t) értékkészlete nem diszkrét, hanem az R+ = [0; 1) halmaz (vagy annak részintervalluma) lehet.
Beágyazott Markov láncok módszere A módszer általánosan a következ½o lépések végrehajtását jelenti: (A) Olyan véletlen 0 < s1 < s2 < : : : id½opontok kiválasztása, melyekben a rendszer fejl½odését leíró folyamat Markov. (B) Az Ln = L(sn ); n
1 Markov lánc ergodikusságának igazolása.
(C) A Markov lánc k
= lim P (Ln = k); n!1
k
0
ergodikus eloszlásának meghatározása. (D) A lim P (L(t) = k) = t!1
k,
k
0 határértékek egybeesésének bizonyítása.
A korábbiak szerint sn (n = 1; 2; : : :) jelöli azt az id½opontot, amikor az n-ik igény kiszolgálása befejez½odik. Legyen Ln = L(sn ), n 1 (L0 = 0). Ekkor, mivel Ysn = 0, n 0, ezért a sn id½opontokban az fL(t); Yt ); t 0g állapotvektor folyamatot az fLn ; n 1g sorozat írja le. A beágyazott Markov láncok módszerének esetünkben éppen az az alapgondolata, hogy ha az f(L(t); Yt ); t 0g folyamatot a sn , n = 1; 2; : : : id½opontokban vizsgáljuk, akkor ezzel a módszerrel az fLn ; n 1g X = f0; 1; 2; : : :g megszámlálható állapotter½u Markov lánc vizsgálatához jutunk és az így nyert eredmények alapján vonunk le általános következtetéseket (ld. a módszer (D) pontját). Megjegyezzük, hogy a fentiekb½ol következik az az igen fontos tulajdonság is, hogy az L(t) folyamat regeneratív és ez a tény használható fel a (D) feladatrész bizonyításánál (utóbbitól eltekintünk). (A), (B) Bebizonyítjuk a következ½o tételt, amely választ ad az (A) és (B) pontokban megfogalmazott feladatokra. Tétel 33 Az fLn ; n 1g sztochasztikus folyamat X = f0; 1; 2; : : :g állapotter½u Markov lánc, amely homogén, irreducibilis és aperiodikus. Ha még teljesül a = B < 1 feltétel is, akkor az fLn ; n 1g Markov lánc ergodikus. Bizonyítás. El½oször igazoljuk, hogy az fLn ; n 1g sztochasztikus folyamat Markov lánc. Jelölje n , n = 1; 2; : : : azon igények számát, amelyek az n-ik igény Yn kiszolgálási ideje alatt lépnek be a rendszerbe, azaz n
= N (sn )
N (sn
Yn ) = N (rn + Yn )
69
N (rn );
n
1:
Megjegyezzük, hogy az n-ik igény kiszolgálása csak akkor kezd½odhet a rn = sn Yn > sn 1 id½opontban, ha a rendszer üres az sn 1 id½opontban, vagyis Ln 1 = 0, amikoris rn = tn és így ebben az esetben n = N (tn ) N (tn 1 ). Ekkor Ln
Ln =
1+
1
n;
n;
ha Ln ha Ln
1 1
> 0; = 0;
(11.1)
vagy másképpen írva Ln = I(Ln
> 0)(Ln
1
1
1) +
n
= (Ln
1
1)+ +
n:
Minthogy az fN (t); t 0g beérkezési folyamat Poisson folyamat, amely független az fYn ; n 1g kiszolgálási id½okt½ol, ezért az Yn kiszolgálási id½o alatt beérkez½o igények n száma független L1 ; : : : ; Ln 1 -t½ol, és így az Ln sorozat nyilvánvalóan Markov láncot alkot. Határozzuk meg most a n (n 1) v.v. eloszlását és várható értékét, melyre szükségünk lesz a továbbiakban. Felhasználva azt a tényt, hogy az N (t) folyamat utóhatásmentes, a n v.v.-k eloszlását felírhatjuk a teljes várható érték tételének segítségével fk = P (
n
= k) =
Z1
P(
1
= kjY1 = x)dB(x) =
0
Z1
( x)k e k!
x
dB(x); k
0:
(11.2)
0
Megjegyzés 25 A ( 11.2) összefüggésb½ol látható, hogy a P (Y = 0) = 1 elfajult esett½ol eltekintve mindig fennáll az fk > 0; k 0 egyenl½otlenség. A
n
v.v. várható értékére a következ½o formulát kapjuk E
n
=
1 X
1
kfk =
k=1 0
k=1
=
Z1 0
1 Z X
1 X ( x)k x e k!
( x)k e (k 1)!
x
x
Z1
dB(x) =
k=0
(11.3)
dB(x) =
xdB(x) =
B
= ;
0
ahol a mennyiséget - amely alapvet½o szerepet játszik vizsgálatunk során - a rendszer terhelésének nevezzük. (Az el½obbi egyenletben az összegzés és az integrálás sorrendjének felcserélhet½osége könnyen igazolható elemi úton.)
A homogenitás bizonyítása. Jelölje az egylépéses átmenetvalószín½uségeket pij (n) = P (Ln+1 = jjLn = i);
i; j
0; n
Ekkor a (11.1) egyenlet felhasználásával kapjuk pij = P (I(i > 0)(i 70
1) +
n+1
= j);
0:
ezért
8 ha i = 0; 1; j = 0; 1; 2; : : : ; < fj ; pij (n) = pij = 0; ha i 2; j i 2; : fj+1 i ; ha i 2; j i 1;
vagyis az fLn ; n 0g sorozat homogém Markov láncot alkot. átmenetvalószín½uség mátrix felírható a következ½o alakban 0 f0 f1 f2 f3 Bf0 f1 f2 f3 B B0 f f f 0 1 2 P = (pij )1 = B i;j=1 B0 0 f f 0 1 @ .. .. .. .. . . . . Az fLn ; n
Ennek megfelel½oen az egylépéses 1 ::: : : :C C : : :C C : : :C A .. .
0g Markov lánc irreducibilitásának és aperodikusságának bizonyítása
Mindkét igazolandó tulajdonság kiolvasható a most felírt egylépéses átmenetvalószín½uség mátrixból, de a következ½o egyszer½u gondolatmenettel is nyerhet½o. Mivel az egymás utáni igények között eltelt id½o paraméter½u exponenciális eloszlású, ezért világos, hogy tetsz½oleges i állapotból i kiszolgálás (lépés) alatt pozitív valószín½uséggel kerülhetünk a 0 állapotba - ehhez elegend½o az, hogy az i lépés alatt ne érkezzen új igény a rendszerbe; a 0 állapotból pozitív valószín½uséggel juthatunk el 1 lépés alatt bármely j 2 X állapotba. Innen az i ill. 1 lépéses átmenetvalószín½uségekre kapjuk (tetsz½oleges i; j 2 X esetén), (i) (1) (i+1) hogy pi0 > 0, p0j > 0 és így pij > 0, ahonnan következik az, hogy fLn ; n 0g Markov (n)
lánc irreducibilis (minden i; j 2 X létezik olyan n, hogy pij > 0). (1)
Könny½u látni, hogy tetsz½oleges i 2 X mellett pii > 0, mivel pozitív annak a valószín½usége, hogy egy igény kiszolgálása alatt pontosan egy újabb igény érkezik a rendszerbe. Így az fLn ; n 0g Markov lánc nyilvánvalóan aperiodikus (ha d(i) jelenti az i állapot periodusát, (n) vagyis d(i) = fl:n:k:o: ja azon n-eknek, melyekre pii > 0g, akkor d(i) = 1). (C) Az fLn ; n
0g Markov lánc ergodikusságának bizonyítása
Az ergodikusság igazolásához az egyik kínálkozó út annak közvetlen belátása, hogy a Markov lánc minden i 2 X állapota visszatér½o nemnulla, azaz 1 valószín½uséggel visszatér minden állapotba és az átlagos visszatérési id½o véges, vagyis 1 1 X X Fii = fii (n) = 1; mi = nfii (n) < 1; n=1
n=0
ahol fij (n) jelenti annak a valószín½uségét, hogy az i állapotból a j állapotba az n-ik lépésben kerülünk el½oször. Ez meglehet½osen számolásigényes út, ezért a bizonyítást a Markov láncok ergodicitására vonatkozó Klimov-féle elégséges feltétel segítségével végezzük el.
71
Tétel 34 (Klimov, 1964) Legyen a fZn ; n 0g folyamat f0; 1; 2; : : :g állapotter½u homogén, irreducibilis és aperiodikus Markov lánc. Létezzen olyan g(i); i 0 nemnegatív függvény, valamint " > 0 és i0 konstans, hogy teljesülnek a következ½o tulajdonságok: 1. E(g(Zn+1 jZn = i)) g(i) "; i i0 ; n 0; 2. E(g(Zn+1 )jZn = i) < 1; i 0. Akkor az fZn ; n 0g Markov lánc ergodikus. Visszatérve az fLn ; n 0g Markov lánc ergodikusságának bizonyításához, alkalmazzuk a Klimov-tételt a < 1 feltétel esetén az " = 1 (> 0) és a g(i) = i; i 0 függvény választása mellett. Azt kell belátnunk, hogy az adott körülmények között teljesülnek a Klimov-tétel 1. és 2. feltételei. Az (11.1) összefüggésb½ol következik, hogy fennáll E(g(Ln+1 )jLn = i) = E(i
1+
n+1 )
=i
1+
B
=1
";
=i
";
i
1
és E(g(Ln+1 )jLn = 0) = E
n+1
=
B
i = 0;
vagyis a Klimov-tétel feltételei maradéktalanul teljesülnek. Ezzel igazoltuk, hogy az fLn ; n lánc ergodikus.
0g Markov
Pollaczek-Hincsin várható érték formula Az (11.1) formula lehet½oséget biztosít arra, hogy az ergodikus eloszláshoz tartozó momentumokat meghatározzuk. Ezt a várható érték meghatározásával mutatjuk be, a többi momentum hasonlóan számolható. Maga a levezetés kevésbé számolásigényes, mint a kés½obb bizonyításra kerül½o Pollaczek-Hincsin transzformáltegyenlet felhasználásával adódó eljárás, azonban az utóbbinál automatikusan adódnak a levezetéshez szükséges feltételek ( < 1, létezik a kiszolgálási id½onek véges második momentuma). Tétel 35 Tegyük fel, hogy léteznek a véges lim ELn = m1
n!1
lim EL2n = m2
és
n!1
határértékek (a létezés feltételeivel itt nem foglalkozunk). Ekkor fennáll a Pollaczek-Hincsin várható érték formula: 2 EY12 : m1 = + 2(1 ) Bizonyítás. Mindenekel½ott megjegyezzük, hogy tétel feltételei alapján nem nehéz igazolni a (11.1) és (11.2) formulák felhasználásával , hogy E 2n < 1, valamint azt is, hogy létezik a kiszolgálási id½oknek is véges második momentuma. Képezve (11.1) mindkét oldalán a várható értéket, az n ! 1 határátmenettel kapjuk m1 = lim ELn = lim [EI(Ln n!1
=
n!1
lim [ELn
n!1
1
EI(Ln
1
1
> 0)(Ln
1
1) + E
> 0) + ] = m1
n]
=
lim EI(Ln
n!1
1
> 0) + ;
ahonnan lim P (Ln > 0) = lim EI(Ln
n!1
n!1
1
> 0) =
és 0
= lim P (Ln = 0) = 1 n!1
lim EI(Ln
n!1
1
> 0) = 1
:
(11.4)
Megjegyezzük, hogy ezek az összefüggések szemléletessé teszik a paraméter elnevezését (a rendszer terhelése). Bár a fenti eljárás hozott fontos eredményt, azonban a keresett várható érték kiesett az egyenletb½ol. Ha
72
az eljárást a második momentumokra megismételjük, akkor elérjük a kívánt célt. Felhasználva Ln függetlenségét, kapjuk
1
és
n
m2 = lim EL2n = n!1
lim E[(L2n
=
n!1
2Ln
1
1
+ 1)I(Ln
+2(Ln 1 1)I(Ln 2m1 + + 2 m1
= m2 ahonnan
2 2+E 2(1 )
m1 =
2 1
1
=
1
> 0) + 2 n]
> 0) n + 2 2 + E 21 ;
+
E 21 2(1
)
=
:
Az alábbiakban a generátorfüggvények módszerével igazoljuk az E 21 = 2 EY12 + összefüggést, melynek felhasználásával az utolsó egyenletünkb½ol adódik Pollaczek-Hincsin várható érték formula. Az E
2 1
=
2
EY12 +
Jelölje B (s) =
R1
összefüggés igazolása az
R1 0
e
sx
dB(x); s
x2 dB(x) < 1 feltétel mellett
0 a B(x) eloszlásfüggvény Laplace-Stieltjes transzformáltját. Az E
1
0
várható érték levezetéséhez hasonló meggondolásokkal kapjuk f 0 (1) = E
n
=
1 X
kfk =
=
Z1
x
1 X
k=0
0
( x)k e k!
eloszlásának generátorfüggvényére, hogy
Z1 1 X ( x)k e k k!
k=1
k=1
1
x
x
dB(x) =
(11.5)
0
dB(x) =
Z1
xdB(x) = :
0
Minthogy létezik a kiszolgálási id½oknek második momentuma, ezért a B Laplace-Stieltjes transzformált kétszer folytonosan deriválható jobbról a 0 pontban és a jobboldali deriváltakra fennáll 0
B (0)
B 00 (0)
Z1
=
=
xdB(x) =
EY1 =
B;
0 Z1
x2 dB(x) = EY12 :
0
Innen és a (11.5) formula felhasználásával kapjuk (a generátorfüggvény baloldali deriváltjait véve az 1 pontban), hogy E E
1 2 1
= f 0 (1) = B 0 (0) = B = ; = (zf 0 (z))0z=1 = B 0 (0) + 2 B 00 (0) = = + 2 EY12 :
B
+
2
EY12 =
(C) A sorhosszúság ergodikus eloszlásának meghatározása a laczek-Hincsin transzformáltegyenlet Az fLn ; n
0g Markov-lánc ergodicitásából következik, hogy létezik a k
= lim P (Ln = k); k = 0; 1; 2; ::: n!1
73
< 1 esetben. Pol-
ergodikus eloszlás, amely a k
=
1 X
j pjk ;
k = 0; 1; 2; :::;
j=0
1 X
=1
k
k=0
egyenletrendszerb½ol határozható meg. A P mátrix speciális alakjából következik (11.2) alapján, hogy ez átírható k
=
0 fk k X
=
+
1 fk
+
2 fk 1
+ ::: +
k+1 f0
k i+1 fi
+
0 fk ;
k = 0; 1; 2; :::
=
(11.6)
i=0
alakba. Ennek az egyenletrendszernek a megoldását a generátorfüggvények módszerével nyerhetjük. Vezessük be a következ½o generátorfüggvényt. (z) =
1 X
k
zk ;
f (z) =
k=0
1 X
k=0
fk z k ; jzj
1:
Mindenekel½ott megjegyezzük, hogy (1) = f (1) = 1 és a korábbi számítások szerint f 0 (1) = lim f 0 (z) = 1 P
z!1 0
kfk (= E
n)
k
= . Szorozzuk meg (11.6) mindkét oldalát z -nal és összegezzük k szerint k
0-ra, ekkor
k=1
kapjuk (z)
= =
1 X
k X
zk
k=0 1 X
fm
k m+1
+
0 f (z)
zk
m
k m+1
+
0 f (z);
=
m=0
fm z m
m=0
1 X
+
0 f (z)
=
k=m
(z) z
= f (z)
0
ahonnan (z)[1
f (z)=z] =
0 f (z)(1=z
1);
és így (z) = (z) meghatározásához szükséges megadni
0
0
(1 z)f (z) ; f (z) z
jzj < 1:
értékét, ami a (1) =
(11.7)
1 P
k
= 1 feltételb½ol határozható meg.
k=0
A Pollaczek-Hincsin várható érték formula levezetése során speciális feltételek mellett már megkaptuk R1 értékét, itt (11.7)-ból az x2 dB(x) < 1 feltétel mellett adódik.
0
0
Mivel (z) balról folytonos az 1 pontban, ezért a z = 1 pontban (11.7) számlálójának és nevez½ojének egyaránt el kell t½unnie. Így a L’Hospital szabály szerint (1) = lim
z!1 0
(z) = lim
z!1 0
f 0 (z) 0
f (z) zf 0 (z) = lim z!1 0 f 0 (z) 1
ahonnan kapjuk a 0 = 1 formulát. Korábban igazoltuk a (11.7) összefüggést, vagyis azt, hogy f (z) = B ( (1
74
z)); jzj
1:
0
f (z) = 1 f 0 (1)
1 0
1
= 1;
Innen és a (11.7) összefüggés …gyelembevételével kapjuk a Pollaczek-Hincsin transzformáltegyenletet (pontosabban annak egyik alakját): (1 )(1 z)B ( (1 z)) (z) = : B ( (1 z)) z Emlékeztet½oül, ez a formula adja meg az fLn ; n generátorfüggvényét.
0g beágyazott Markov-lánc ergodikus eloszlásának a
Következmény 4 Az M jM j1 rendszer invertálása: Esetünkben legyen a beérkezési intenzitás továbbra is > 0, míg a kiszolgálás intenzitása > 0 (a beérkezési id½oközök, ill. a kiszolgálási id½ok ekkor független , ill. paraméter½u exponenciális eloszlású valószín½uségi változók). Ekkor B (s) = ; Re s > ; s+ (z) = Mivel
=
(1 [ =(
z+
)(1 z) z + )]
z
:
= = , ezért (z) =
1 1
z
;
így innen a stacionárius eloszlásra következik k
= (1
)
k
; k
0:
A korábbiak megjegyzésünk szerint a (D) összefüggés bizonyításától eltekintünk.
Foglaltsági/szabad intervallumok vizsgálata az MjGj1 típusú TKRben Ha meg…gyeljük egy TKR m½uködését, akkor általában kijelölhetünk olyan egymást követ½o id½oszakaszokat, amelyeken a rendszer üres ill. foglalt. Azt az id½ointervallumot, amikor a rendszer foglalt, foglaltsági intervallumnak (v. periodusnak) nevezzük. Akkor kezd½odik, amikor az üres redszerbe beérkezik egy igény és akkor fejez½odik be, amikor a rendszer kiürül. Vizsgáljuk a rendszert a korábban tett feltételek mellett. Ha ( i ; i ); i = 1; 2; : : : jelenti az egymás után következ½o szabad ill. foglalt periodusok hosszát (ld. 1. ábra), akkor ( i ; i ) független, azonos eloszlású valószín½uségi vektorváltozók. sorozata, melyekben a i és i komponensek is függetlenek egymástól. A ( i + i ); i = 1; 2; : : : sorozat felújítási folyamatot alkot, ahol i eloszlása paraméter½u exponenciális. Az i foglaltsági intervallumok eloszlásának a meghatározása bonyolultabb, mellyel az alábbiakban foglalkozunk. A szabad/foglalt intervallumokat a következ½o ábra szemlélteti: Jelölje (x) = P ( i < x). Tegyük fel, hogy a t = 0 id½opillanatban érkezik igény a rendszerbe és ezzel egy foglaltsági periodus kezd½odik. Jelölje ennek kiszolgálási idejét Y . Két eset lehetséges: – ezen id½o alatt nem érkezik újabb igény a rendszerbe és akkor a foglaltsági intervallumnak vége szakad, vagyis a hossza ebben az esetben Y (ekkor = Y ). – Y id½o alatt n
1 számú igény érkezik a rendszerbe és a foglaltsági intervallum folytatódik.
Jelölje az utóbbi esetben az egymás utáni n darab kiszolgálási id½ot Y1 ; Y2 ; : : : ; Yn . Tegyük fel, hogy a belép½o igények kiszolgálása a belépés fordított sorrendjében történik, azaz LCFS kiszolgálási elv szerint (Takács, 1955), ekkor a feltevéseink következtében a beérkezési és kiszolgálási id½ok függetlenek, paraméter½u exponenciális ill. B(x) eloszlásúak, ezért az Y id½o alatt belép½o minden egyes igényhez tartozó "saját" foglaltsági intervallum eloszlása ugyanaz ( ) lesz. A teljes foglaltsági intervallum tehát felbontható ekkor olyan Y; n ; n 1 ; : : : ; 1 hosszúságú intervallumokra (ha n = 0, akkor = Y ), ahol n ; n 1 ; : : : ; 1 az egyes igényekhez tartozó “saját" foglaltsági intervallumokat jelentik, és amelyek: 75
ηi
ξi
ξi + 1
ηi + 1
t 1. ábra
η
Yn
Yn - 1
ζn
Y
Y1
ζ1
ζn - 1 2. ábra
– függetlenek – azonos eloszlásúak és eloszlásuk megegyezik az A teljes valószín½uség tétele szerint (
n
+
+
1
eloszlásával. = 0, ha n = 0)
(x) = P ( < x) = = P (Y + n + + 1 < x) = 1 X = P (Y + n + + 1 < x; n = j) = j=0
=
Z1 X 1 0
=
Z1 X 1 0
=
+
+
+
+
j
< x; n = j j Y = y) dB(y) =
1
P (y +
j
1
< x)
j=0
Z1 X 1 0
P (Y +
j=0
j=0
j (x
y)
( y)j e j!
76
y
( y)j e j!
dB(y)
y
dB(y) =
(az összegzés és az integárlás sorrendje felcserélhet½o volt), ahol j (x)
= P(
1
+
+
j
< x):
A nyert függvényegyenlet egyszer½usíthet½o, ha Laplace–Stieltjes-transzformáltakat használunk. Jelölje B (s) =
Z1
e
sx
dB(x);
(s) =
0
Ekkor, mivel
j -k
=
j=0
1 X (
=
d (x):
Z1
yj e
( +s)y
dB(y) =
0
( 1)j
(s))j dj (B ( + s)); j! dsj
(
j=0
ami megegyezik a B ( + s
sx
eloszlásúak, ezért írhatjuk 9 1 = j Z y) e sx dx j (x y) e y dB(y) = ; j! 0 9 = y)j e sy ( (s))j e y dB(y) = ; j!
(s))j j!
j=0
1 X
e
0
függetlenek és azonos 8 Z1 <X 1 ( (s) = : j=0 0 8 Z1 <X 1 ( = : 0
Z1
(s)) függvény
(s) pont körüli Taylor-sorával, így
(s) = B ( + s
(s)):
(11.8)
Az (11.8) függvényegyenlet megoldásával foglalkozik a következ½o Tétel 36 Ha = 1 , akkor létezik és egyértelm½u a megoldása az (11.8) függvényegyenletnek Re s > 0 esetén, amelyre j (s)j 1 és (s) valós minden s > 0 mellett, továbbá a (s) Laplace-Stieltjes transzformálthoz tartozó (x) függvény (inverz Laplace-Stieltjes transzformált) eloszlásfüggvény. Következmény 5 Tegyük fel, hogy E = (0) várható értékre:
< 1. Di¤ erenciálva (11.8)-t, az s = 0 helyen, egy egyenlet adódik az 0
(0) = B 0 (0)(1
0
(0)):
Innen a foglaltsági intervallum várható értékére kapjuk 0
E =
(0) =
1
Hasonlóan számítható a többi momentum is, pl. E
2
=
EY 2 : (1 )3
77
:
Téma 12
Az MjGj1 típusú tömegkiszolgálási rendszer vizsgálata szimulációval A tömegkiszolgálási rendszerek jellemz½oinek vizsgálatánál gyakran, még egyszer½unek látszó modellek esetén sem tudunk egzakt formulákat adni. Ilyen esetekben hasznos és hatékony vizsgálati módszer a szimulációs módszer. Ez a megközelítés azon alapszik, hogy a rendszer m½uködésére nagyszámú kísérletet végzünk, mintegy a „rendszer m½uködését szimuláljuk” és a nyert eredmények alapján vonunk le következtetéseket. A szimulációs módszert a GjGj1 rendszeren keresztül mutatjuk be a korábban megszabott feltételek teljesülése mellett (függetlenség, azonos eloszlások), azonban a módszer hasonló módon alkalmazható más TKR-ek esetében is. Megjegyezzük, hogy számos szimulációs vizsgálatok céljára felhasználható szoftver létezik, lehet½oséget nyújtva a különböz½o gyakorlati problémák megoldásában. Jelölje (Xn ; Yn ); n = 1; 2; : : : a rendszer beérkezési folyamatát, jelölje A(x) a beérkezési id½oközök eloszlását, B(x) pedig a kiszolgálási id½okét. Vizsgáljuk a rendszer egyik jellemz½ojét, mondjuk az átlagos sorhosszúságot a [0; T ] intervallumon. A vizsgálat a következ½o lépésekb½ol áll: 1. El½oször modellezzük a rendszert jellemz½o eloszlással bíró v.v.-kat. Ez alatt azt értjük, hogy pl. a könnyen generálható, (0; 1)-en egyenletes eloszlású v.v.-k segítségével el½oállítjuk, vagy jól közelítjük. Ezután pszeudovéletlenszám-generátor felhasználásával létrehozzuk a rendszert jellemz½o eloszlásokkal a véletlen (xn ; yn ); 1 n K sorozatot, ahol K jelenti azoknak azon igényeknek a szimulált sorozattól függ½o számát, melyek a [0; T ] intervallum alatt érkeznek a rendszerbe, azaz K = maxfk : tk < T g; ahol tk jelenti a k-adik igény beérkezési id½opontját: tk = x1 + ::: + xk ; k = 1; 2; ::: Az egyszer½uség kedvéért feltesszük, hogy a rendszert jellemz½o A(x) és B(x) eloszlásfüggvényekre A(0+) = B(0+) = 0 és ennek megfelel½oen a generált sorozat minden tagja pozitív. 78
2. Meghatározzuk az egymás utáni foglaltsági intervallumokat és az igények egymás utáni távozási id½opontjait. (a) A foglaltsági intervallumok meghatározása Jelölje az igények egymás utáni távozási id½opontjait s1 ; s2 ; :::és legyenek j = [tnj ; snj+1 1 ); j = 1; 2; ::: az egymást követ½o foglaltsági intervallumok. Ekkor teljesül, hogy a foglaltsági intervallumokhoz tartozó t id½opontokban L(t) > 0, azon kívül pedig L(t) = 0. A de…níció szerint tnj jelenti a j-edik foglaltsági periodus kezd½opontját (n1 = 1), snj+1
1
= tnj + ynj + ynj +1 + :: + ynj+1
1
pedig a végpontját. Az nj index a következ½o rekurziós formulával határozható meg: nj+1 = minfnj + 1 + m : xnj + ::: + xnj +m > ynj + ::: + ynj +m g; j = 1; :::; M ahol M = maxfk : tnk < T ): (b) A foglaltsági intervallumhoz tartozó kezd½o indexek felhasználásával meghatározzuk egymás után a k-adik (1 k K) igény sk távozási id½opontját (ez elvileg történhet a T id½opont után is). Jelölje `(k) azt az egyértelm½uen meghatározott indexet, amelyre fennáll n`(k) k n`(k)+1 1; ekkor az sk távozási id½opontokra fennáll sk = tn`(k) + yn`(k) + ::: + yk : 3. Kiszámítjuk az _
1 L(T ) = T
ZT
L(t)dt
0
átlagos sorhosszúságot. Ebben az esetben, felhasználhatjuk az L(t) = N (t)
M (t); t
0, összefüggést, ahonnan _
1 L(T ) = T
ZT 0
(N (t)
K 1X M (t))dt = [min(sk ; T ) T
tk ]
k=1
Megjegyezzük, hogy az összegzésben a min(sk ; T ) tk éppen azt az id½otartamot jelenti a [0; T ] intervallumra nézve, amennyit a_k: igény eltölt a rendszerben. Hosszú T szimulációs id½ot véve az L(T ) -vel becsüljük a rendszer átlagos sorhosszúságát.
79
Regeneratív módszer alkalmazása szimulációs vizsgálatokban Az un. regeneratív szimulációs módszerrel (Crane, M.A., Lemoine, A.J., 1977 és Shedler, G.S., 1987) is vizsgálhatjuk az átlagos sorhosszúságot, amely további következtetésekre ad módot. Ez a megközelítés azon az észrevételen alapszik, hogy a rendszer a tki ; i = 1; 2; ::: id½opontokban, az üres periodus után az éppen a tki id½opontban beérkez½o igényt kezdi kiszolgálnia és a rendszer további állapotváltozása teljes mértékben független a 0 t tki id½ointervallumon felvett állapotától, vagyis a rendszer a tki ; i = 1; 2; ::: id½opontokban mintegy regenerálódik. Ez azt jelenti, hogy az egymást követ½o foglaltsági és üres periodusokból álló szakaszok függetlenek, és függetlenek lesznek azok a folyamatszakaszok is, amelyek leírják a rendszer állapotát. Innen következik, hogy a rendszernek az egyes regeneratív szakaszokon számított jellemz½oi független azonos eloszlásó valószín½uségi változókat képeznek, melyekre alkalmazható a nagy számok törvénye, centrális határeloszlás tétel és ennek alapján pl. kon…dencia-intervallum is szerkeszthet½o a rendszer mutatóira. E tulajdonság felhasználásával bizonyítható pl. az is, hogy a rendszerben tartózkodó igények számának létezik-e határeloszlása, vagy pl. létezik-e határértéke (1 valószín½uséggel) az LT átlagos sorhosszúságnak. Számos TKR rendelkezik a regeneratív tulajdonsággal és hatékonyan vizsgálhatók ezzel a módszererel. Visszatérve a GjGj1 rendszer vizsgálatához, meghatározzuk a fenti eljárással az [0; T ] intervallumot metsz½o M számú j ; 1 j M foglaltsági periodust a hozzá tartozó nj ; 1 j M kezd½o indexekkel együtt. Legyen Ij =
R
L(t)dt =
j
és IM =
R
nM
L(t)dt =
nj+1 P 1
[sk
tk ]; 1
j
M
k=nj
nMP +1 1
I(sk
T; tk < T )[min(sk ; T )
tk ]:
k=nM
Ekkor a rendszerben tartózkodó igények átlagos száma LT =
M 1 MP1 1 M 1 P 1 RT L(t)dt = Ij + JM = Ij T0 T j=1 T T M j=1
1 (IM T
JM )
Az egyenletben szerepl½o véletlen mennyiségekr½ol a következ½oket tudjuk mondani: (a) A felújításelmélet alapján (ld. 5. Téma, alapvet½o felújítási tétel) a regenerációs peT riodusok M számára fennáll M ! v, T ! 1; 1 valószín½uséggel, ahol jelenti egy regenerációs hossz várható értékét, amely minden regeneratív periodusra ugyanaz. (b) Minthogy IM eloszlása megegyezik I1 eloszlásával, ezért JM 1 (IM T
JM )
1 valószín½uséggel. 80
1 IM ! 0 T
IM miatt nyilvánvalóan
(c) Az Ij ; j 1 valószín½uségi változók függetlenek és azonos eloszlásúak, a 1 konvrgencia 1 valószín½uséggel teljesül, ezért a véletlen tagszámú
M T
! 1; T !
M 1 P Ij M j=1
összegre igaz a centrális határeloszlás tétel: legyen = EIk ; = DIk ; akkor tetsz½oleges valós x szám mellett ! M 1 P P p (Ikj ) < x ! (x); T ! 1; M j=1 ahol
1 (x) = p 2
jelöli a standard normális eloszlásfüggvényt.
Rx
e
y 2 =2
dy
1
Megjegyezzük, hogy a szimulációs eredmény alapján kon…dencia-intervallumot is szerkeszthetünk az átlagos sorhosszúságra.
81
Bibliography [1] Györ… L., Páli I.: Tömegkiszolgálás informatikai rendszerekben, M½uegyetemi Kiadó, 1996 [2] Lakatos L., Szeidl L., Telek M.: Tömegkiszolgálási algoritmusok, In: Informatikai algoritmusok, 2. kötet (szerkeszt½o: Iványi A.), ELTE Eötvös Kiadó, 2005 [3] S.Karlin, H.M.Taylor: Sztochasztikus folyamatok, Gondolat, Budapest, 1985 [4] Kingman, J.F.C., Poisson Processes, Clerendon Press, Oxford, 1993.Kingman, 1993. [5] L.Kleinrock: Sorbanállás–kiszolgálás. Bevezetés a tömegkiszolgálási rendszerek elméletébe, M½uszaki Kiadó, Budapest, 1979 [6] Snyder, D.L., Random Point Processes, Wiley, New York, 1975. [7] Sztrik J.:Bevezetés a sorbanállási elméletbe és alkalmazásaiba, Debrecen, 2004 (elektronikus változat: http://irh.inf.unideb.hu/user/jsztrik/) [8] A.S.Tanenbaum, M. van Steen: Számítógép-hálózatok, Panem, Budapest, 2004
82
