Esercizio - Gara fra server con tempi di servizio esponenziali - minimo, massimo e richieste replicate

Teoria: Distribuzione esponenziale e processo di Poisson per l'informaticaL'esponenziale Exp(λ) è l'unica legge continua senza memoria: P(X>s+t | X>s)=P(X>t). Il minimo di esponenziali indipendenti è Exp(Σλ_i) e l'indice del minimo è i con probabilità λ_i/Σλ (indipendente dal valore del minimo); il massimo di n esponenziali Exp(λ) ha media H_n/λ. Il processo di Poisson di intensità λ ha interarrivi Exp(λ) i.i.d., N(t) ~ Poisson(λt) e incrementi indipendenti; la scomposizione (ogni evento tenuto con probabilità p) dà due processi di Poisson indipendenti, la sovrapposizione dà un processo di intensità somma. Applicazioni: carichi Poisson delle urne (poissonizzazione, con costo e√m), server replicati, arrivi durante un servizio.Distribuzione esponenziale e processo di Poisson per l'informatica →.

Testo. Tre server hanno tempi di servizio esponenziali indipendenti con tassi $\mu_1=1$, $\mu_2=2$, $\mu_3=3$ al secondo.

1. La stessa richiesta viene inviata ai tre server e si usa la prima risposta. Legge e media del tempo di risposta; probabilità che risponda ciascun server.
2. Tempo medio perché tutti e tre abbiano finito (massimo).
3. Un lavoro su un server di tasso $2$ è in corso da $2$ secondi. Probabilità che duri ancora più di $1$ secondo.
4. Tre server identici di tasso $2$: media e $P(T>1)$ della prima risposta rispetto a un singolo server.
5. Una richiesta si divide in $10$ sotto-richieste indipendenti $\text{Exp}(1)$ e finisce quando finiscono tutte: media e probabilità di superare $5$ s.

Soluzione

1. Il minimo è $\text{Exp}(\mu_1+\mu_2+\mu_3)=\text{Exp}(6)$: tempo medio $\tfrac16\approx0{,}167$ s. Risponde il server $i$ con probabilità $\mu_i/6$: $\tfrac16,\ \tfrac13,\ \tfrac12$, indipendentemente dall'istante della risposta.

2. Metodo 1: fasi. Il primo completamento arriva dopo $\tfrac16$ s in media. Poi restano due server, che per l'assenza di memoria ricominciano da zero. Il massimo di due esponenziali di tassi $a,b$ ha media $\tfrac1a+\tfrac1b-\tfrac1{a+b}$ (inclusione-esclusione sulle code: $\max=X+Y-\min$):

• se ha finito il server $1$ (probabilità $\tfrac16$): restano $2$ e $3$, media $\tfrac12+\tfrac13-\tfrac15=\tfrac{19}{30}$;
• se ha finito il $2$ (probabilità $\tfrac13$): restano $1$ e $3$, media $1+\tfrac13-\tfrac14=\tfrac{13}{12}$;
• se ha finito il $3$ (probabilità $\tfrac12$): restano $1$ e $2$, media $1+\tfrac12-\tfrac13=\tfrac76$.

Quindi $E[\max]=\tfrac16+\tfrac16\cdot\tfrac{19}{30}+\tfrac13\cdot\tfrac{13}{12}+\tfrac12\cdot\tfrac76=\tfrac{30+19+65+105}{180}=\tfrac{219}{180}=\tfrac{73}{60}$.

Metodo 2: coda. $P(\max>t)=1-\prod_i(1-e^{-\mu_it})=\sum_ie^{-\mu_it}-\sum_{i<j}e^{-(\mu_i+\mu_j)t}+e^{-6t}$, e integrando su $[0,\infty)$: $$E[\max]=\sum_i\frac1{\mu_i}-\sum_{i<j}\frac1{\mu_i+\mu_j}+\frac1{\mu_1+\mu_2+\mu_3}=\Bigl(1+\tfrac12+\tfrac13\Bigr)-\Bigl(\tfrac13+\tfrac14+\tfrac15\Bigr)+\tfrac16=\frac{73}{60}.$$ Lo stesso risultato: $\boxed{E[\max]=\tfrac{73}{60}\approx1{,}217\text{ s}}$ (simulazione: $1{,}2168$).

3. Assenza di memoria: $P(T>3\mid T>2)=P(T>1)=e^{-2\cdot1}=\boxed{0{,}1353}$. L'attesa già trascorsa non dà alcuna informazione.

4. Il minimo di tre $\text{Exp}(2)$ è $\text{Exp}(6)$: media $\tfrac16$ s (contro $\tfrac12$ s per un singolo server) e $P(T>1)=e^{-6}=0{,}0025$ contro $e^{-2}=0{,}1353$: la coda scende di un fattore $55$. Il costo è che tre server lavorano per la stessa richiesta: il carico complessivo triplica (finché un server non chiude la richiesta degli altri).

5. Massimo di $n=10$ esponenziali i.i.d. $\text{Exp}(1)$: $E[\max]=H_{10}=1+\tfrac12+\dots+\tfrac1{10}=\tfrac{7381}{2520}=2{,}929$ s (rispetto a $1$ s per una sotto-richiesta). Inoltre $P(\max>5)=1-(1-e^{-5})^{10}=1-0{,}99326^{10}=0{,}0654$, circa dieci volte la probabilità $e^{-5}=0{,}0067$ di una singola sotto-richiesta. La varianza vale $\sum_{k=1}^{10}\tfrac1{k^2}=1{,}5498$ (deviazione standard $1{,}245$).

Codice di verifica

import numpy as np
from fractions import Fraction as F
mu = [1, 2, 3]
rng = np.random.default_rng(1)
X = rng.exponential(1 / np.array(mu), size=(2_000_000, 3))
print("min:", X.min(axis=1).mean(), " vince:", np.bincount(X.argmin(axis=1)) / len(X))
Emax = sum(F(1, m) for m in mu) - sum(F(1, mu[i] + mu[j]) for i in range(3) for j in range(i + 1, 3)) + F(1, sum(mu))
print("max esatto:", Emax, float(Emax), " simulato:", X.max(axis=1).mean())
Y = rng.exponential(1, size=(500_000, 10)).max(axis=1)
print("10 sotto-richieste:", Y.mean(), Y.var(), (Y > 5).mean())

Output: min: 0.1666... vince: [0.1669 0.3333 0.4998], max esatto: 73/60 1.2166... simulato: 1.2168, 10 sotto-richieste: 2.926 1.545 0.0649 (simulato, circa i valori esatti $2{,}929$, $1{,}550$, $0{,}0654$).