Esercizio - sistema M/M/infinito

Questa pagina non ha ancora la versione ripasso: qui sotto c'è il testo completo.

Testo (approfondimento, esercizio impegnativo). Si consideri un sistema M/M/$\infty$. Si dimostri che $x(t)$ ammette una distribuzione stazionaria, di Poisson con parametro $\rho=\frac\lambda\mu$. Suggerimento: si consideri l'intervallo $[0,T]$ con il sistema vuoto al tempo $0$ (è un'ipotesi restrittiva?). Sia $A(T)$ il numero di arrivi in $[0,T]$: qual è la distribuzione di $A(T)$, cioè $P[A(T)=N]$? E come sono distribuiti gli arrivi nell'intervallo? Scrivere la distribuzione di $x(T)$ tenendo conto che $x(T)=k$ se ci sono stati $A(T)=N$ arrivi in $[0,T]$ e, di questi $N$ clienti, $k$ non hanno finito il servizio al tempo $T$. Far tendere $T$ all'infinito. Ricorda: la somma di variabili binarie identicamente distribuite ha distribuzione binomiale; qui si conta il numero di "successi" (un cliente non ha finito il servizio al tempo $T$) per una "moneta" con probabilità $p=P[t_j+y_j>T]$, dove $t_j$ e $y_j$ sono l'istante di arrivo e il tempo di servizio del $j$-esimo cliente.

Teoria usata: Processi di arrivo e processo di PoissonUn sistema a coda ha clienti che arrivano, un'area di attesa e $m$ servitori. Il processo di arrivo è un processo di punto con tempi di interarrivo $\tau_n=t_n-t_{n-1}$ e tasso $\lambda=\frac1{E[\tau]}$. Nel processo di Poisson omogeneo gli arrivi in intervalli disgiunti sono indipendenti e di Poisson con media $\lambda T$, gli interarrivi sono esponenziali $\lambda e^{-\lambda a}$ e senza memoria; somma di processi di Poisson è Poisson (tassi che si sommano), il diradamento con probabilità $p$ dà Poisson di tasso $p\lambda$; in $[0,h]$ c'è un arrivo con probabilità $\lambda h+o(h)$. Servizio con tasso $\mu=\frac1{E[y]}$; notazione di Kendall $A/B/m/K/N-S$.Processi di arrivo e processo di Poisson →, Sistemi a coda M-M-1 e M-M-mIn un sistema M/M/m (arrivi di Poisson $\lambda$, servizi esponenziali $\mu$, $m$ servitori) il numero di clienti $x(t)$ è una catena di Markov di nascita e morte con tassi di nascita $\lambda$ e di morte $\min(k,m)\mu$. A regime il bilancio di flusso $\lambda\pi_{k-1}=\min(k,m)\mu,\pi_k$ dà per M/M/1 $\pi_k=(1-\rho)\rho^k$ ($\rho=\frac\lambda\mu<1$), $E[x]=\frac\rho{1-\rho}$, $E[s]=\frac1{\mu-\lambda}$ (esponenziale), e per M/M/m la probabilità di accodamento di Erlang C, $C=P[x\ge m]$, con $E[q]=\frac{C,G}{m-G}$, $E[w]=\frac C{m\mu-\lambda}$, $E[s]=E[w]+\frac1\mu$ ($G=\frac\lambda\mu$, $\rho=\frac Gm<1$).Sistemi a coda M-M-1 e M-M-m →, Prove ripetute e modello binomialen prove indipendenti, ciascuna con probabilità di successo p: una sequenza con k successi ha probabilità p^k (1−p)^(n−k), e la probabilità di esattamente k successi è (n su k) p^k (1−p)^(n−k) (modello binomiale); il primo successo alla prova k ha probabilità (1−p)^(k−1) p.Prove ripetute e modello binomiale →, Distribuzione di PoissonPoi(λ) conta eventi rari: P(X = k) = e^(−λ) λ^k / k! per k = 0, 1, 2, …, con media e varianza entrambe uguali a λ; approssima la binomiale Bin(n, p) quando n è grande e p piccolo, con λ = np.Distribuzione di Poisson →.

Il sistema

M/M/$\infty$: arrivi di Poisson di tasso $\lambda$, servizi i.i.d. esponenziali di tasso $\mu$, infiniti servitori: ogni cliente trova subito un servitore e non c'è mai coda ($w=0$, $x=z$). Ogni cliente resta nel sistema un tempo $y_j\sim\operatorname{Exp}(\mu)$, indipendentemente dagli altri.

Sistema vuoto all'inizio: non è restrittivo

Si assume $x(0)=0$. Non è restrittivo perché ci interessa il comportamento per $T\to\infty$ e un cliente presente all'istante $0$ è ancora nel sistema all'istante $T$ con probabilità $e^{-\mu T}$ (assenza di memoria: il suo servizio residuo è ancora $\operatorname{Exp}(\mu)$), che tende a $0$: lo stato iniziale viene "dimenticato".

Distribuzione di $x(T)$

Arrivi. $A(T)$ è di Poisson di parametro $\lambda T$: $P[A(T)=N]=\frac{(\lambda T)^N}{N!}e^{-\lambda T}$. Posizioni degli arrivi. Dato che in $[0,T]$ ci sono stati $N$ arrivi, i loro istanti $t_1,\dots,t_N$ sono indipendenti e uniformi in $[0,T]$ (proprietà del processo di Poisson: arrivi omogenei, nessun istante privilegiato).

Probabilità che un cliente sia ancora presente. Il cliente $j$, arrivato in $t_j$, è nel sistema al tempo $T$ se $t_j+y_j>T$, cioè $y_j>T-t_j$. Con $t_j$ uniforme in $[0,T]$ e $y_j\sim\operatorname{Exp}(\mu)$ indipendente: $$p=P[t_j+y_j>T]=\frac1T\int_0^Te^{-\mu(T-t)}\,dt=\frac1T\int_0^Te^{-\mu u}du=\frac{1-e^{-\mu T}}{\mu T}$$ (si è sostituito $u=T-t$). I clienti sono indipendenti, quindi, dato $A(T)=N$, il numero $x(T)$ di clienti ancora presenti è binomiale $(N,p)$: $$P[x(T)=k\mid A(T)=N]=\binom Nkp^k(1-p)^{N-k},\qquad k\le N.$$

Distribuzione incondizionata. Per la probabilità totale: $$P[x(T)=k]=\sum_{N\ge k}\frac{(\lambda T)^N}{N!}e^{-\lambda T}\binom Nkp^k(1-p)^{N-k}=e^{-\lambda T}\frac{(\lambda pT)^k}{k!}\sum_{j\ge0}\frac{(\lambda(1-p)T)^j}{j!}=e^{-\lambda pT}\frac{(\lambda pT)^k}{k!},$$ dove si è posto $j=N-k$ e si è usato $\sum_j\frac{y^j}{j!}=e^y$ con $y=\lambda(1-p)T$ (e $e^{-\lambda T}e^{\lambda(1-p)T}=e^{-\lambda pT}$). Quindi $x(T)$ è di Poisson di parametro $$\lambda pT=\lambda\,\frac{1-e^{-\mu T}}\mu=\rho\left(1-e^{-\mu T}\right).$$ (Si ritrova che $x(T)$ è una "diradazione" di un processo di Poisson, Processi di arrivo e processo di PoissonUn sistema a coda ha clienti che arrivano, un'area di attesa e $m$ servitori. Il processo di arrivo è un processo di punto con tempi di interarrivo $\tau_n=t_n-t_{n-1}$ e tasso $\lambda=\frac1{E[\tau]}$. Nel processo di Poisson omogeneo gli arrivi in intervalli disgiunti sono indipendenti e di Poisson con media $\lambda T$, gli interarrivi sono esponenziali $\lambda e^{-\lambda a}$ e senza memoria; somma di processi di Poisson è Poisson (tassi che si sommano), il diradamento con probabilità $p$ dà Poisson di tasso $p\lambda$; in $[0,h]$ c'è un arrivo con probabilità $\lambda h+o(h)$. Servizio con tasso $\mu=\frac1{E[y]}$; notazione di Kendall $A/B/m/K/N-S$.Processi di arrivo e processo di Poisson →, §3.4.)

Limite per $T\to\infty$

$e^{-\mu T}\to0$ e il parametro tende a $\rho=\frac\lambda\mu$: $$\lim_{T\to\infty}P[x(T)=k]=\pi_k=\frac{\rho^k}{k!}e^{-\rho},\qquad E[x]=\rho.$$ La distribuzione stazionaria esiste per qualsiasi $\lambda$ e $\mu$ (il sistema M/M/$\infty$ è sempre stabile: ogni cliente trova un servitore) ed è Poisson di parametro $\rho$. Lo stesso risultato si ottiene dai bilanci di flusso, $\lambda\pi_{k-1}=k\mu\pi_k$ (Sistemi a coda M-M-1 e M-M-mIn un sistema M/M/m (arrivi di Poisson $\lambda$, servizi esponenziali $\mu$, $m$ servitori) il numero di clienti $x(t)$ è una catena di Markov di nascita e morte con tassi di nascita $\lambda$ e di morte $\min(k,m)\mu$. A regime il bilancio di flusso $\lambda\pi_{k-1}=\min(k,m)\mu,\pi_k$ dà per M/M/1 $\pi_k=(1-\rho)\rho^k$ ($\rho=\frac\lambda\mu<1$), $E[x]=\frac\rho{1-\rho}$, $E[s]=\frac1{\mu-\lambda}$ (esponenziale), e per M/M/m la probabilità di accodamento di Erlang C, $C=P[x\ge m]$, con $E[q]=\frac{C,G}{m-G}$, $E[w]=\frac C{m\mu-\lambda}$, $E[s]=E[w]+\frac1\mu$ ($G=\frac\lambda\mu$, $\rho=\frac Gm<1$).Sistemi a coda M-M-1 e M-M-m →, §6): $\pi_k=\frac{\rho^k}{k!}\pi_0$ con $\pi_0=e^{-\rho}$. La media $E[x]=\rho$ è anche Little: $E[x]=\lambda E[s]=\lambda\cdot\frac1\mu$.

Esempio numerico. $\lambda=3$ chiamate/min, durata media $\frac1\mu=0{,}5$ min: $\rho=1{,}5$ servitori occupati in media; $\pi_0=e^{-1{,}5}=0{,}223$, $\pi_1=0{,}335$, $\pi_2=0{,}251$, e $P[x\ge4]=0{,}066$. A $T=1$ min dal sistema vuoto: parametro $\rho(1-e^{-\mu T})=1{,}5(1-e^{-2})=1{,}30$.