I.3. Születési-halálozási folyamatok


A Markov-folyamatok egy igen fontos speciális osztálya születési és halálozási folyamatok néven ismert. A definiáló feltétel: minden állapotból csak ,,szomszédos'' állapotba mehet végbe átmenet ($\pm 1$-el változhat). Állapottérnek ekkor a nem negatív egész számok halmazát választjuk (ami nem megy az általánosság rovására), és $X_k=i$ esetében $X_{k+1}$ vagy $i-1$, vagy $i$, vagy $i+1$ lehet. A születési-halálozási folyamatoknak nagy szerepük van a sorbanállási rendszerek vizsgálatában. Ahhoz, hogy egy $X(t)$ Markov lánc születési-halálozási folyamat legyen, ki kell elégítenie az alábbi feltételeket :


ahol $h$ egy tetszőlegesen kis intervallumot jelent, $o(h)$ pedig olyan mennyiséget jelöl, amely gyorsabban tart $0$-hoz, mint $h$, ha $h\to0$, vagyis ${o(h) \over h}\to0$, ha $h\to0$. Vegyük észre, hogy $\lambda_k$, $\mu_k$ pozitív mennyiségek függetlenek az időtől. A $\lambda_k$-kat születési intenzitásnak, a $\mu_k$-kat pedig halálozási intenzitásnak nevezzük. Jelöljük $P_k(t)$-vel annak valószínűségét, hogy a folyamat a $t$ időpillanatban a $k$ állapotban van, vagyis

\begin{displaymath} P_k(t)=P(X(t)=k). \end{displaymath}

Ezt szokás abszolút valószínűségnek is nevezni. Ezen valószínűségek kiszámításához figyelembe kell venni a következőket. A $t+h$ időpillanatban a $X(t)$ $k$ állapotban van akkor és csak akkor, ha az alábbi feltételek teljesülnek:

1. $t$ időpillanatban a folyamat a $k$ állapotban van és a $(t,t+h)$ időintervallumban változás nem következik be; 2. $t$ időpillanatban a folyamat a $k-1$ állapotban volt és a $k$-ba történt átmenet; 3. $t$ időpillanatban a folyamat a $k+1$ állapotban volt és a $k$-ba történt átmenet; 4. $(t,t+h)$ alatt 2 vagy több átmenet történt. Látható, hogy az 1-3 feltételek kölcsönösen kizárják egymást, és a 4. eset valószínűsége $o(h)$. Világos, hogy $t$ minden értékére teljes eseményrendszerről van szó, így:

\begin{displaymath} \sum_{k=0}^\infty P_k(t)=1. \leqno(28) \end{displaymath}

Az előbbi feltételek teljesülése után már felírhatjuk a $P_k(t+h)$ valószínűséget:

\begin{displaymath} \eqalign{ P_k(t+h)=&P_k(t)\{1-\lambda_kh-\mu_kh+o(h)\}\cr ... ...\cr &+P_{k+1}\{\mu_{k+1}h+o(h)\}+o(h),\quad k\geq 1.\cr } \end{displaymath}

Ha mindkét oldalból kivonjuk $P_k(t)$-t és osztjuk $h$-val, akkor $h\to0$ esetén a következő differenciálegyenleteket kapjuk:

\begin{displaymath}{P_0(t) \over dt} =-\lambda_0P_0(t)+\mu_1P_1(t),\leqno(29)\end{displaymath}



Annak belátása, hogy a fenti egyenleteknek létezik egyértelműen meghatározott megoldása nem könnyű feladat. Az egyenletrendszer megoldható, ha bizonyos megkötéseket teszünk a születési-halálozási folyamatra vonatkozóan. Meg kell adni a $P_k(0)$, $k=0,1,2,...$ értékeket, ezenkívül a (28) egyenlőségnek is teljesülnie kell.


Most tegyünk egy kis kitérőt. Adjunk egy intuitív módszert arra, hogyan lehet az előbbi differenciálegyenlet-rendszert megkapni. Figyeljük a $k$ állapotot. Észrevehetjük, hogy oda csak a $k-1$ és a $k+1$ állapotokból lehet átlépni. Hasonlóképpen a $k$ állapototë csak úgy lehet elhagyni, hogy a $k-1$ vagy a $k+1$ állapotba jutunk. Mivel dinamikus szituációt vizsgálunk, ezért világos, hogy a két rátának a különbsége, amellyel a folyamat belép a $k$ állapotba, ill. elhagyja azt, egyenlő kell, hogy legyen az illető állapot abszolút valószínűségének a megváltozásával. Ennek segítségével leírhatjuk a $P_k(t)$ valószínűségekre vonatkozó mozgásegyenletet. A $t$ pillanatban az érkezés intenzitása ebbe az állapotba:

\begin{displaymath} Q \lambda_{k-1}P_{k-1}(t)+\mu_{k+1}P_{k+1}(t), \end{displaymath}

míg a távozás intenzitása:

\begin{displaymath} (\lambda_k+\mu_k)P_k(t). \end{displaymath}

E kettő különbsége az abszolút valószínűség $t$-beli változásával (deriváltjával) egyenlő, azaz

\begin{displaymath} {dP_k(t) \over dt}=\lambda_{k-1}P_{k-1}(t)+\mu_{k+1}P_{k+1}(t) -(\lambda_k+\mu_k)P_k(t)\ . \end{displaymath}

De ez éppen a (30) összefüggés $k>0$ esetén. Könnyű belátni, hogy ez az érvelés a $k=0$ esetben is korrekt egyenletre vezet. Az általános, időfüggő megoldás nehezen adható meg, ezért mi megelégszünk az ún. {\dlt egyens\'ulyi} (vagy stacionárius) megoldással, mivel ez sok esetben jól használható. Definiáljuk a stacionárius megoldást, mint egy $P_k$ valószínűségi eloszlást, amelyre fennáll a következő: $P_k(t)=P_k$. Ha egy ilyen eloszlás létezik, akkor egyértelmű és minden $k$-ra teljesül:

\begin{displaymath} \lim_{t\to\infty }P_k(t)=P_k. \end{displaymath}

Mivel minket most csak a folyamat időtől független tulajdonságai érdekelnek, ezért először vegyük a (30) baloldalának határértékét $t\to\infty$ esetén, ez $0$-val lesz egyenlő, és egy kis átalakítással a következő lineáris differenciaegyenletet kapjuk:

\begin{displaymath} \lambda_kP_k-\mu_{k+1}P_{k+1}=\lambda_{k-1}P_{k-1}-\mu_kP_k, \qquad k=1,2,...\quad . \end{displaymath}

Ebből arra következtethetünk, hogy

\begin{displaymath} \lambda_{k-1}P_{k-1}-\mu_kP_k=\hbox{konstans}, \qquad k=1,2,...\quad . \end{displaymath}

A (29)-ből:

\begin{displaymath} \lambda_0P_0-\mu_1P_1=0. \end{displaymath}

Tehát a fenti konstansnak nullának kell lenni, ezzel az alábbi egyenlőségre jutottunk:

\begin{displaymath} \mu_kP_k=\lambda_{k-1}P_{k-1}, \qquad k=1,2,... \quad . \end{displaymath}

Ez a következőképpen értelmezhető: a baloldal a $k$ állapotból a $k-1$ állapotba való átmenet rátája, ami egyensúlyban van a $k-1$ állapotból a $k$ állapotba való átmenet rátájával, ami a jobboldalon található. Így az egyensúlyi állapot valószínűségei a következők:

\begin{displaymath} P_k={\lambda_{k-1} \over \mu_k}P_{k-1}={\Lambda(k) \over M(k)}P_0, \end{displaymath}

ahol

\begin{displaymath} \Lambda(k)=\prod_{i=1}^k\lambda_{i-1}, \end{displaymath}

és

\begin{displaymath} M(k)=\prod_{i=1}^k\mu_i. \end{displaymath}

A $P_0$ valószínűséget egyértelműen meghatározhatjuk, mivel a valószínűségek $\{P_k; k=0,1,2,...\}$ összegének $1$-nek kell lenni. Tehát, ha az

\begin{displaymath} 1+\sum_{k=1}^\infty {\Lambda(k) \over M(k)}=1+\sum_{k=1}^\infty \prod_{i=1}^k{\lambda_{i-1} \over \mu_i} \end{displaymath}

sor konvergens, és összege $\varphi$ akkor

\begin{displaymath} P_0=\varphi^{-1}, \end{displaymath}

és ez egyben a stacionáris eloszlás létezésének elégséges feltétele is.

A Poisson folyamat: A vizsgált rendszerek közül a legegyszerűbb a tiszta születési folyamat. Ekkor feltesszük, hogy $\mu_k=0$ minden $k$ esetén. Tovább egyszerűsítve a problémát tegyük fel, hogy $\lambda_k=\lambda$, $k=0,1,2,...$ . Ekkor a (29, 30) a következőre redukálódik:


Az egyszerűség kedvéért tegyük fel, hogy a rendszer a $0$ állapotból indul a $0$ időpillanatban, azaz

\begin{displaymath} P_k(0)=\cases{ 1&\hbox{, ha $k=0$} ,\cr 0&\hbox{, ha $k\ne 0$}.\cr} \end{displaymath}

Könnyű látn<i, hogy a $P_0(t)$ valószínűségre:

\begin{displaymath} P_0(t)=e^{-\lambda t}. \end{displaymath}

Így a $k=1$ esetre az alábbit kapjuk:

\begin{displaymath} {dP_1(t) \over dt}=-\lambda P_1(t)+\lambda e^{-\lambda t}. \end{displaymath}

Ennek a differenciálegyenletnek a megoldása:

\begin{displaymath} P_1(t)=\lambda te^{-\lambda t}. \end{displaymath}

Indukcióval folytatva a megoldást, könnyen meggyőződhetünk, hogy

\begin{displaymath} P_k(t)={(\lambda t)^k \over k!}e^{-\lambda t},\qquad k\geq 0, t\geq 0. \end{displaymath}

Ez a híres Poisson-eloszlás. A konstans $\lambda$ születési intenzitású tiszta születési folyamatban előforduló születések sorozatát nevezik Poisson folyamatnak. Mivel a kapott eredményeket később a sorbanállási rendszerek tanulmányozásakor szeretnénk felhasználni, így rögtön sorbanállási jelöléseket vezetünk be: a Poisson-folyamatot mint igények beérkezését tekintjük valamilyen kiszolgálási rendszerben, nem pedig mint egy populáció új tagjainak születését. Ezért $\lambda$ az igénybeérkezés átlagos intenzitása. A kezdeti feltételllel együtt a $P_k(t)$ mennyiség megadja annak valószínűségét, hogy $k$ igény érkezik be a $(0,t)$ intervallumban. Világos, hogy ha átlagosan $\lambda$ igény érkezik be időegységenként, ezért egy $t$ hosszúságú intervallum alatt átlagosan $\lambda t$ számú igénynek kell beérkeznie, azaz a $t$ idő alatt beérkezett igények számának várható értéke $\lambda t$. A Poisson-folyamatot, mint tiszta születési folyamatot vezettük be, és levezettük a $P_k(t)$ mennyiségekre - egy adott $t$ hosszúságú időintervallum alatt bekövetkező érkezések számának valószínűségeloszlására - egy formulát. Vizsgáljuk most meg a beérkezések időpillanatainak együttes eloszlását, ha előre ismert, hogy éppen $k$ igény érkezett ebben az intervallumban. Osszuk fel a $(0,t)$ intervallumot $2k+1$ diszjunkt részre a következőképpen. Az $\alpha_i$ hosszúságú intervallumok előzzék meg a $\beta_i$ hosszúságú intervallumokat $(i=1,\ldots,k)$, és az utolsó intervallum $\alpha_{k+1}$ hosszúságú legyen, továbbá

\begin{displaymath}\sum_{i=1}^{k+1}\alpha_i +\sum_{i=1}^k\beta_i =t .\end{displaymath}

Jelentse $A_k$ azt az eseményt, hogy éppen egy beérkezés fordul elő minden egyes $\beta_i$ intervallumban $(i=1,2,...,k)$, az $\alpha_i$ intervallumban pedig egy sem. $A_k$ valószínűségét akarjuk kiszámolni, feltéve, hogy éppen $k$ beérkezés történik a $(0,t)$ intervallumban. A feltételes valószínűség definíciójából

\begin{displaymath} \eqalign{ P(A_k\vert\hbox{pontosan }k\hbox{ be\'erkez\'es ... ...{pontosan }k\hbox{ be\'erkez\'es }(0,t)\hbox{ alatt})}\cr } \end{displaymath}

Amikor a Poisson-folyamat szerinti beérkezéseket vizsgáljuk diszjunkt időintervallumokban, akkor független eseményeket vizsgálunk, azaz ezek együttes valószínűségét az egyes valószínűségek szorzataként lehet kiszámolni. Könnyu látni, hogy

\begin{displaymath} P(\hbox{egyetlen be\'erkez\'es egy }\beta_i\hbox{ hossz\'us\'ag\'u intervallum alatt})= \lambda\beta_ie^{-\lambda\beta_i} \end{displaymath}

és

\begin{displaymath} P(\hbox{nincs be\'erkez\'es egy }\alpha_i\hbox{ hossz\'us\'ag\'u intervallum alatt})= e^{-\lambda\alpha_i}. \end{displaymath}

Kihasználva ezt, azonnal kapjuk a következőt:

\begin{displaymath} P(A_k\vert\hbox{ \'eppen }k\hbox{ be\'erkez\'es }(0,t)\hbox{ alatt})=\end{displaymath}


\begin{displaymath} ={(\lambda\beta_1\lambda\beta_2 ... \lambda\beta_ke^{-\lam... ...ha_k}) \over ((\lambda t)^k/k!)e^{-\lambda t}}= \leqno{(31)} \end{displaymath}


\begin{displaymath}={\beta_1\beta_2...\beta_k \over t^k}k!.\end{displaymath}

Másrészt tekintsünk egy olyan folyamatot, amelynél a $(0,t)$ intervallumban $k$ darab pont fordul elő egymástól függetlenül, mégpedig mindegyik az intervallumon egyenletes eloszlás szerint. Könnyen belátható, hogy

\begin{displaymath} P(A_k\vert\hbox{ \'eppen }k\hbox{ be\'erkez\'es }(0,t)\hbox... ... t}\right) ...\left({\beta_k \over t}\right)k!,\leqno{(32)} \end{displaymath}

ahol a $k!$ tényező amiatt jelenik meg, mert nem különböztetjük meg a $k$ darab pont permutációit. Észrevehetjük, hogy a (31) és a (32) összefüggésekben megadott két feltételes valószínűség megegyezik, és ennek alapján arra gondolhatunk, hogy ha a Poisson-folyamatban $t$ idő alatt $k$ beérkezés történik, akkor a beérkezések eloszlása ugyanaz, mint $k$ darab ugyanazon az intervallumon egyenletes eloszlású pont eloszlása. Ennek pontos igazolása a fenti gondolatmenet finomításával elvégezhető. A születési folyamat tulajdonságaiból könnyű levezetni, hogy a Poisson-folyamat homogén; vagyis ha $X(s,s+t)$ jelöli a $t$ hosszúságú $(s,s+t)$ intervallum alatti beérkezések számát, akkor

\begin{displaymath} P(X(s,s+t)=k)={(\lambda t)^ke^{-\lambda t} \over k!}, \end{displaymath}

függetlenül attól, hogy hol helyezkedik el az intervallum (vagyis függetlenül az intervallum $s$ kezdőpontjától).


Most a Poisson-folyamat és az exponenciális eloszlás közötti összefüggés vizsgálatára térünk át. Az exponenciális eloszlásnak szintén központi szerepe van a sorbanállás elméletében. Tekintsük a $\tilde t$ valószínűségi változót - a két egymás utáni ,,szomszédos'' beérkezések között eltelt idő -, amelynek eloszlás- és sűrűségfügvényét $F(t)$, ill. $f(t)$ jelöli. Ekkor $f(t)\Delta t+o(\Delta t)$ a valószínűsége annak, hogy a soron következő beérkezésig a legutolsó beérkezéstől eltelt idő legalább $t$, de legfeljebb $(t+\Delta t)$. Mivel $F(t)$ a valószínűsége annak, hogy a beérkezések közötti idő$\leq t$, ezért

\begin{displaymath} F(t)=1-P(\tilde t>t). \end{displaymath}

De $P(\tilde t>t)$ éppen annak valószínűsége, hogy egyetlen beérkezés sem következik be a $(0,t)$ intervallumon, azaz $P_0(t)$. Azt kapjuk tehát, hogy

\begin{displaymath} F(t)=1-P_0(t), \end{displaymath}

így az eloszlásfüggvény (a Poisson esetben)

\begin{displaymath} F(t)=1-e^{-\lambda t},\qquad t\geq 0. \leqno{(33)} \end{displaymath}

Ezt differenciálva, a sűrűségfüggvény:

\begin{displaymath} f(t)=\lambda e^{-\lambda t}, \qquad t\geq 0. \end{displaymath}

Ez a jól ismert exponenciális eloszlás, tehát a {\dlt Poisson-folyamat eset\'en a be\'erkez\'esi idők\uml oz\uml ok f\uml uggetlen exponenci\'alis eloszl\'as\'uak}. Az exponenciális eloszlás legfontosabb jellemzője az, hogy emlékezetnélküli, azaz a valószínűségi változó múltja nem játszik szerepet jövőjének meghatározásában. Ezen a következőt értjük. Képzeljük el, hogy a $0$ időpillanatban következett be egy beérkezés. Ha azt kérdezzük, hogy mi a legközelebbi beérkezésig eltelő $t$ idő eloszlása, a felelet nyilvánvaló, a (33) képlet adja meg az eloszlásfüggvényét. Teljék el bizonyos idő, mondjuk $t_0$ másodperc, ez alatt ne történjen beérkezés. Ekkor újra megkérdezhetjük: Mennyi a valószínűsége annak, hogy a legközelebbi beérkezésig mostantól számítva $t$ idő telik el. Ez a kérdés csak annyiban különbözik a $0$ időpillanatban feltett kérdéstől, hogy most tudjuk, a két beérkezés között eltelő idő legalább $t_0$ másodperc. Ahhoz, hogy feleljünk a második kérdésre, a következő számításokat végezzük:

\begin{displaymath} \eqalign{ P(\tilde t\leq t+t_0\vert\tilde t>t_0)=&{P(t_0<\... ...leq t+t_0)-P(\tilde t\leq t_0) \over P(\tilde t>t_0)}.\cr } \end{displaymath}

A (33) miatt


és így

\begin{displaymath} P(\tilde t\leq t+t_0\vert\tilde t>t_0)=1-e^{-\lambda t}=P(\tilde t\leq t). \end{displaymath}

Az eredmény azt mutatja, hogy ha az utolsó beérkezés óta $t_0$ idő telt el, akkor a következő beérkezésig hátralevő idő eloszlása ugyanaz, mint a beérkezési időköz feltétel nélküli eloszlása. És ez az egyetlen olyan folytonos eloszlás, amely ilyen tulajdonságú.


Nem nehéz belátni, hogy

\begin{displaymath}1-e^{-\lambda t}=\lambda t+o(t).\end{displaymath}

Ez nyilván egyenértékű a

\begin{displaymath}\lim_{t\to 0}{{1-e^{-\lambda t}}\over t}= \lambda \end{displaymath}

állítással, amelyet a L'Hospital-szabállyal egyszerűen bebizonyíthatunk. Hiszen

\begin{displaymath}\lim_{t\to 0} {( {1-e^{-\lambda t})}' \over t'}= \lambda . \end{displaymath}

Az $1-e^{-\lambda t}= \lambda t+o(t) $ egyenlőség a későbbiekben nagyon fontos lesz számunkra.

Nyitólap    Tartalomjegyzék    Fejezetek ( B I II III IV F )    Letöltések
FRAME-mel FRAME nélkül
<<   Előző Következő  >>