Esercizio - SMS dei gol e coda M/M/1

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

Testo. Uno studente si iscrive a un servizio che invia un SMS ogni volta che viene segnato un gol nel campionato di calcio. Si può mostrare, con buona approssimazione (Heuer et al., 2010), che il numero di gol in una partita è una variabile di Poisson di parametro $3$ [gol], e che i gol sono distribuiti uniformemente nella partita. La durata media di una partita è di $96$ minuti. Una domenica pomeriggio si giocano $8$ partite contemporaneamente. Il telefono dello studente ha una memoria molto grande per gli SMS e riceve messaggi solo da questo servizio. Lo studente li legge man mano che arrivano (in ordine) e poi li cancella. Il tempo per leggere e cancellare un messaggio è esponenziale con media $3$ minuti. Con la notazione di Kendall, che sistema a coda è? Si stimi la probabilità che, a metà delle partite, la memoria del telefono contenga due o più messaggi.

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 →.

Il modello

Arrivi. In una partita ci sono in media $3$ gol, distribuiti uniformemente nei $96$ minuti: il gol è un evento di un processo di Poisson con tasso (media del numero di eventi per unità di tempo) $$\lambda_0=\frac{3\ \text{gol}}{96\ \text{min}}=\frac1{32}\ \text{min}^{-1}.$$ Le $8$ partite sono indipendenti e simultanee: per la sovrapposizione di processi 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) i messaggi arrivano con un processo di Poisson di tasso $$\lambda=8\lambda_0=\frac8{32}=\frac14=0{,}25\ \text{min}^{-1}$$ (un messaggio ogni $4$ minuti in media).

Servizio. Lo studente è un solo servitore; i messaggi sono letti in ordine di arrivo (FCFS); il tempo di lettura è esponenziale di media $3$ minuti, quindi $\mu=\frac13\ \text{min}^{-1}$. La memoria è praticamente illimitata (coda infinita). Dunque il sistema è una M/M/1.

Carico. $\rho=\frac\lambda\mu=\frac{0{,}25}{1/3}=0{,}75<1$: il sistema è stabile.

Probabilità di due o più messaggi in memoria

Un messaggio resta in memoria finché non è stato letto e cancellato, quindi i messaggi in memoria sono i clienti nel sistema, $x$ (quello in lettura compreso). Con le probabilità stazionarie $\pi_k=(1-\rho)\rho^k$: $$\pi_0=1-\rho=0{,}25=\frac14,\qquad\pi_1=(1-\rho)\rho=0{,}25\cdot0{,}75=\frac3{16},$$ $$P[x\ge2]=1-\pi_0-\pi_1=1-\frac14-\frac3{16}=\frac9{16}=0{,}5625=\rho^2.$$ Il risultato è anche $P[x\ge k]=\rho^k$ per $k=2$. Dunque, in condizioni di regime, più di una volta su due ci sono almeno due messaggi non cancellati.

Una verifica: il regime è davvero raggiunto?

Il risultato usa la distribuzione stazionaria, ma alle $0$ del primo minuto la memoria è vuota e le partite durano solo $96$ minuti. Il sistema si avvicina al regime con costante di tempo dell'ordine di $\frac1{(\sqrt\mu-\sqrt\lambda)^2}=\frac1{(0{,}577-0{,}5)^2}\approx167$ minuti, più lunga della partita. Risolvendo numericamente le equazioni differenziali della catena di nascita e morte a partire dal sistema vuoto si ottiene, a metà partita ($t=48$ min), $P[x\ge2]=0{,}49$ (e $0{,}53$ a $96$ min). Il valore $\frac9{16}=0{,}56$ è quindi una stima per eccesso, come chiede il testo ("si stimi"): è il valore a regime, e a metà partita il sistema è ancora un po' sotto di esso.