III.1.2. A beágyazott Markov-láncok
Most már lehetőségünk van a beágyazott Markov-láncok
módszerének az
sorra való alkalmazásához. A módszer alapgondolata
az, hogy az
kétdimenziós
állapotleírást leegyszerűsítsük az
egydimenziós leírássá. Ha ki akarjuk
számolni az állapotváltozás jövőbeli értékeit,
akkor a rendszerbeli igényeknek ezzel az egydimenziós leírásával
együtt meg kell adnunk impliciten azt az időt is, amelyet az igény
már a kiszolgálócsatornában töltött. Ennek az
egyszerűsítésnek az az ára, hogy nem minden időpontot tudunk
figyelni, csak bizonyos kiválasztott időpontokat. Ezeknek olyanoknak kell
lenniük, hogy ha meghatározzuk az egyik ilyen időpontban a rendszerbeli
igények számát, és figyelembe vesszük az elkövetkezendő
beérkezéseket, akkor a legközelebbi alkalmas időpontban újra
ki kell tudnunk számolni a rendszerbeli igények számának
eloszlását, azaz valahogy le kell írnunk a kiszolgálócsatornában
tartózkodó igény már eltelt kiszolgálási idejét.
Sok ilyen ponthalmaz van, de legcélszerűbb a kiszolgálócsatornából
való távozási pillanatokból állókat tekintenünk.
Ha megadjuk egy igény távozásakor a rendszerben maradt igények
számát, akkor bármely jövőbeli pontban ismét ki tudjuk
számolni ezt, hiszen a további beérkezések adottak. Ezekben
a pillanatokban nulla a kiszolgálócsatornában tartózkodó
igényre vonatkozó, már eltelt kiszolgálási idő, hiszen
ez az igény (ha van ilyen) éppen az adott pillanatban lépett
be a csatornába. Leírásunk nem más, mint egy szemi-Markov
folyamat *A szemi-Markov folyamat esetében az egy
helyben maradás ideje tetszőleges eloszlású lehet, míg Markov
folyamatnál exponenciális eloszlást követelünk meg.
Lásd Karlin - Taylor: Sztochasztikus folyamatok, 210. oldal.,
melyben az állapotváltozások az igények távozási
pillanataiban következnek be. Ezekben a pillanatokban egy beágyazott
Markov-láncot definiálunk, ami a rendszerben tartózkodó
igények száma közvetlenül a távozás után.
Állapotváltozások csak a beágyazott pontokban jöhetnek
létre, és diszkrét állapotteret alkotnak. Két állapotátmenet
közötti idő eloszlása a kiszolgálási idő
eloszlásával egyezik meg, ha a távozás
legalább egy igényt hagy még a rendszerben, és az exponenciális
eloszlású beérkezési időközöknek és
-nek a konvolúciójával egyenlő, ha a távozás
üres rendszert hagy maga mögött, hiszen ekkor meg kell várnia
a következő beérkezést is, annak eloszlása pedig emlékezetnélküli.
Ezekben a beágyazott pontokban a lánc viselkedését Markov-folyamatként
lehet leírni. Tehát a kiszolgálócsatornából való
távozások időpontjait figyeljük, és állapotváltozónak
a távozó igények által hátrahagyott igények
számát vesszük. Mint majd látni fogjuk, ezen beágyazott
Markov-pontokra adódó megoldás az összes időpontra szolgáltatja
a megoldást! Ez a szerencsés körülmény annak köszönhető,
hogy a beérkezési folyamat Poisson-típusú, és ezáltal
a beérkező igények mintegy véletlen pillantást vetnek a
rendszerre. A rendszer állapotát a rendszerben tartózkodó
igények számaként -
- értelmezve megfigyelhetjük a rendszer állapotváltozásait
az idő függvényében. Ezek a változások közvetlen
szomszéd típusúak, azaz ha
igény van éppen a rendszerben, akkor a következő állapotában
vagy
lesz. A
típusú átlépések száma legfeljebb
eggyel különbözhet a
típusú átlépések számától,
ezért ha a rendszer elég sokáig működik, akkor a felfelé
irányuló átlépések relatív gyakoriságának
meg kell egyeznie a lefelé irányuló átmenetek relatív
gyakoriságával. Így arra következtethetünk, hogy a
beérkezések időpontjában észlelt rendszerállapot eloszlása
meg kell, hogy egyezzen a távozások időpontjában
észlelt rendszerállapot határeloszlásával
. Igazak a következő megállapítások:
ely
Poisson-folyamatú beérkezések esetén
Ha egy általános rendszerben
az értékeit mindig csak eggyel változtatja
és létezik a következő határeloszlások egyike, akkor
a másik is létezik, és ezen határeloszlások egyenlőek:
Így az
rendszerre
azaz a beérkezések, a távozások és a véletlenszerű
megfigyelések egyensúlyi állapotban a rendszerbeli igények
számának ugyanazt az eloszlását figyelik meg. A teljesség
kedvéért mind a két állítást bebizonyítjuk.
Bizonyítsuk be először az
-et. Vezessük be a következő jelöléseket:
Legyen
az az esemény, hogy egy beérkezés történik
a
intervallumban. Ekkor
Felhasználva a feltételes valószínűség definícióját,
Az emlékezetnélküliség miatt az
esemény nem függ a
pillanatban a rendszerben tartózkodó igények számától,
ezért
így
azaz
Ez természetesen a stacionárius valószínűségekre is igaz,
azaz
A
-t is bebizonyítjuk, az
felhasználásával. Jelölje
a
állapotban lévő rendszerbe történő beérkezések
számát a
intervallumban, és
a
intervallumban azon távozások számát,
melyek után a rendszer az
állapotba kerül. Feltételünkből következik,
hogy
Továbbá, ha az összes távozások számát
, az összes beérkezésekét pedig
jelöli, akkor
A távozási pontokban észlelt határeloszlás felírható
a következőképpen
Ha a számlálóhoz hozzáadunk és le is vonunk belőle
-t, és a nevezőt felírjuk a fenti alakban,
akkor
Mivel
véges és
-nek is annak kell lennie a stacionaritás feltétele
miatt,
-ből és abból, hogy
, egy valószínűséggel következik
Innen, az
pontot is felhasználva kapjuk az állításunkat.