III.1.2. A beágyazott Markov-láncok

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 $\left[N\left(t\right), X_0\left(t\right)\right]$ kétdimenziós állapotleírást leegyszerűsítsük az $N\left(t\right)$ 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ő $B\left(x\right)$ 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 $B\left(x\right)$ -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 $k\to k+1$ típusú átlépések száma legfeljebb eggyel különbözhet a $k+1\to k$ 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 $\left(R_k\right)$ meg kell, hogy egyezzen a távozások időpontjában észlelt rendszerállapot határeloszlásával $\left(D_k\right)$ . Igazak a következő megállapítások: ely Poisson-folyamatú beérkezések esetén

$\begin{displaymath} P\left(N\left(t\right)=k\right)=P\left(box{egy}\ t\ \hbox{p... ...z\'es}\ k\ \hbox{ig\'enyt tal\'al a rend\-szer\-ben}\right). \end{displaymath}$

Ha egy általános rendszerben $N\left(t\right)$ 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:

$\begin{displaymath} R_k:=\lim_{t\to\infty}P\left(t\ \hbox{pillanatbeli be\'erkez\'es}\ k\ \hbox{ig\'enyt tal\'al a rendszerben}\right) , \end{displaymath}$

$\begin{displaymath} D_k:=\lim_{t\to\infty}P\left(t\ \hbox{pillanatbeli t\'avoz\'as}\ k\ \hbox{ig\'enyt hagy maga m\uml og\uml ott}\right) , \end{displaymath}$

$\begin{displaymath} R_k=D_k. \end{displaymath}$

Így az

rendszerre

$\begin{displaymath} R_k=P_k=D_k , \end{displaymath}$

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:

$\begin{displaymath} P_k(t):=P\left(N\left(t\right)=k\right) , \end{displaymath}$

$\begin{displaymath} R_k(t):=P\left(\hbox{egy}\ t\ \hbox{pillanatbeli be\'erkez\'es}\ k\ \hbox{ig\'enyt tal\'al a rendszerben}\right). \end{displaymath}$

Legyen $A(t,t+\Delta t)$ az az esemény, hogy egy beérkezés történik a $(t,t+\Delta t)$ intervallumban. Ekkor

$\begin{displaymath} R_k(t)=\lim\limits_{\Delta t\to 0}P\left(N\left(t\right)=k\ \vert\ A(t,t+\Delta t)\right). \end{displaymath}$

Felhasználva a feltételes valószínűség definícióját,

$\begin{displaymath} R_k(t)=\lim\limits_{\Delta t\to 0}{P\left(N\left(t\right)=k, A(t,t+\Delta t)\right)\over P\left(A(t,t+\Delta t)\right)}= \end{displaymath}$

$\begin{displaymath} =\lim\limits_{\Delta t\to 0}{P\left(A(t,t+\Delta t)\ \vert\... ...ght)P\left(N(t)=k\right)\over P\left(A(t,t+\Delta t)\right)}. \end{displaymath}$

Az emlékezetnélküliség miatt az $A(t,t+\Delta t)$ esemény nem függ a

pillanatban a rendszerben tartózkodó igények számától, ezért

$\begin{displaymath} P\left(A(t,t+\Delta t)\ \vert\ N\left(t\right)=k\right)=P\left(A(t,t+\Delta t) \right) , \end{displaymath}$

így

$\begin{displaymath} R_k(t)=\lim\limits_{\Delta t\to 0}P\left(N(t)=k\right) , \end{displaymath}$

azaz

$\begin{displaymath} R_k(t)=P_k(t). \end{displaymath}$

Ez természetesen a stacionárius valószínűségekre is igaz, azaz

$\begin{displaymath} R_k=\lim\limits_{t\to\infty}R_k(t)=\lim\limits_{t\to\infty}P_k(t)=P_k. \end{displaymath}$

-t is bebizonyítjuk, az

felhasználásával. Jelölje $\hat{R}_k\left(t\right)$ a

állapotban lévő rendszerbe történő beérkezések számát a $\left(0,t\right)$ intervallumban, és $\hat{D}_k\left(t\right)$ a $\left(0,t\right)$ intervallumban azon távozások számát, melyek után a rendszer az

állapotba kerül. Feltételünkből következik, hogy

$\begin{displaymath} \vert \hat{R}_k\left(t\right)-\hat{D}_k\left(t\right)\vert\le 1.\leqno(2) \end{displaymath}$

Továbbá, ha az összes távozások számát $D\left(t\right)$ , az összes beérkezésekét pedig $R\left(t\right)$ jelöli, akkor

$\begin{displaymath} D\left(t\right)=R\left(t\right)+N\left(0\right)-N\left(t\right). \end{displaymath}$

A távozási pontokban észlelt határeloszlás felírható a következőképpen

$\begin{displaymath} D_k=\lim_{t\to\infty}{\hat{D}_k\left(t\right)\over D\left(t\right)}. \end{displaymath}$

Ha a számlálóhoz hozzáadunk és le is vonunk belőle $\hat{R}_k\left(t\right)$ -t, és a nevezőt felírjuk a fenti alakban, akkor

$\begin{displaymath} {\hat{D}_k\left(t\right)\over D\left(t\right)}={\hat{R}_k\l... ...ight)\over R\left(t\right)+N\left(0\right)-N\left(t\right)}. \end{displaymath}$

Mivel $N\left(0\right)$ véges és $N\left(t\right)$ -nek is annak kell lennie a stacionaritás feltétele miatt,

-ből és abból, hogy $\hat{R}\left(t\right)\to\infty$ , egy valószínűséggel következik

$\begin{displaymath} D_k=\lim_{t\to\infty}{\hat{D}_k\left(t\right)\over D\left(t... ...\to\infty}{\hat{R}_k\left(t\right)\over R\left(t\right)}=R_k. \end{displaymath}$

Innen, az pontot is felhasználva kapjuk az állításunkat.

Nyitólap Tartalomjegyzék Fejezetek ( B I II III IV F ) Letöltések

FRAME-mel

FRAME nélkül

<< Előző

Következő >>