Esercizio - Urne vuote e carico massimo con mille server

Teoria: Palline e urne - compleanno, carico massimo e approssimazione di PoissonModello palline e urne (m palline, n urne, scelte indipendenti e uniformi): paradosso del compleanno con soglia sqrt(2 n ln 2), urne vuote attese n e^(-m/n), carico massimo ln n / ln ln n con dimostrazione (first moment e union bound), approssimazione di Poisson con il fattore e sqrt(m), potere delle due scelte (ln ln n / ln 2).Palline e urne - compleanno, carico massimo e approssimazione di Poisson → (urne vuote e carico massimo), Linearità del valore atteso e variabili indicatriciLa linearità $E[X+Y]=E[X]+E[Y]$ vale sempre, anche senza indipendenza; con le variabili indicatrici ($E[I_A]=P(A)$) trasforma un conteggio in una somma di probabilità. Applicazioni: attesa del primo successo $1/p$, collezionista di figurine $nH_n$, punti fissi di una permutazione (media $1$), record (media $H_n$), inversioni ($n(n-1)/4$), attesa condizionata, identità di Wald $E[S_N]=E[N]E[X]$.Linearità del valore atteso e variabili indicatrici →, Momenti e deviazioni - Markov, Chebyshev e mediana randomizzataVar(ΣX_i) = ΣVar + 2ΣCov, e basta l'indipendenza a coppie perché la varianza si sommi. Chebyshev dà code polinomiali (collezionista: P(T ≥ nH_n + cn) ≤ π²/(6c²)); il metodo del secondo momento dà P(X=0) ≤ Var(X)/E[X]². Algoritmo della mediana: campione di n^(3/4) elementi, due estremi d e u a ±√n, ordinamento dei soli elementi tra d e u; fallisce con probabilità ≤ n^(-1/4) ed è Las Vegas con 2n + o(n) confronti.Momenti e deviazioni - Markov, Chebyshev e mediana randomizzata →.

Testo. Un bilanciatore assegna ogni richiesta a uno di $n=1000$ server scelto uniformemente e indipendentemente.

1. Dopo $m=1000$ richieste, sia $Z$ il numero di server che non hanno ricevuto nulla. Calcolare $E[Z]$, $\text{Var}(Z)$, la deviazione standard e il limite di Chebyshev su $P(Z\ge400)$.
2. Quante richieste servono perché, con probabilità almeno $0{,}95$, tutti i server ne abbiano ricevuta almeno una? Confrontare il valore minimo (con il limite di Markov $P(Z\ge1)\le E[Z]$) con $n(\ln n+3)$.
3. Con $n=10^6$ server e $10^6$ richieste, trovare il più piccolo $k$ per cui l'union bound garantisce $P(\text{carico massimo}\ge k)\le1\%$, usando (a) la coda binomiale esatta e (b) il limite $\frac1{k!}$. Confrontare con il valore $\lceil3\ln n/\ln\ln n\rceil$ del teorema e con una simulazione.

Soluzione

1. Urne vuote. Sia $I_i=1$ se il server $i$ è vuoto: $P(I_i=1)=(1-\frac1n)^m$, perché ciascuna delle $m$ richieste deve evitarlo. Per la linearità $$E[Z]=n\Bigl(1-\frac1n\Bigr)^m=1000\cdot0{,}999^{1000}=\boxed{367{,}70}\quad(\text{contro }ne^{-1}=367{,}88).$$ Per la varianza serve $E[I_iI_j]=(1-\frac2n)^m$ ($i\ne j$: le richieste evitano entrambi), quindi $$\text{Var}(Z)=n(n-1)\Bigl(1-\frac2n\Bigr)^m+n\Bigl(1-\frac1n\Bigr)^m-n^2\Bigl(1-\frac1n\Bigr)^{2m}=\boxed{97{,}23},\qquad\text{sd}=9{,}86.$$ Il primo termine è $\sum_{i\ne j}E[I_iI_j]$, il secondo è $\sum_iE[I_i]=E[Z]$ (perché $I_i^2=I_i$), il terzo è $E[Z]^2$. Chebyshev: $P(Z\ge400)\le P(|Z-\mu|\ge32{,}3)\le\frac{97{,}23}{32{,}3^2}=\boxed{0{,}093}$. Il limite è largo: in $20\,000$ simulazioni $Z$ ha media $367{,}6$ e deviazione $9{,}85$ e $Z\ge400$ capita nello $0{,}085\%$ dei casi ($17$ volte).

2. Tutti i server raggiunti. Per Markov $P(Z\ge1)\le E[Z]=n(1-\frac1n)^m$. Si vuole $\le0{,}05$: il minimo $m$ intero con $1000\cdot0{,}999^m\le0{,}05$ è $\boxed{m=9899}$ (dà $0{,}04998$; con $m=9898$ si supera $0{,}05$). Con la stima $(1-\frac1n)^m\le e^{-m/n}$: $ne^{-m/n}\le0{,}05\iff m\ge n\ln(20n)=9903{,}5$, vicino al valore esatto. Il valore $n(\ln n+3)=9907{,}8$ garantisce $ne^{-m/n}=e^{-3}=0{,}0498$. Il tempo medio per riempire tutti i server è $nH_n\approx7485$ ($H_{1000}=7{,}485$): serve più del doppio per avere il $95\%$ di sicurezza (collezionista di figurine, Linearità del valore atteso e variabili indicatriciLa linearità $E[X+Y]=E[X]+E[Y]$ vale sempre, anche senza indipendenza; con le variabili indicatrici ($E[I_A]=P(A)$) trasforma un conteggio in una somma di probabilità. Applicazioni: attesa del primo successo $1/p$, collezionista di figurine $nH_n$, punti fissi di una permutazione (media $1$), record (media $H_n$), inversioni ($n(n-1)/4$), attesa condizionata, identità di Wald $E[S_N]=E[N]E[X]$.Linearità del valore atteso e variabili indicatrici →).

3. Carico massimo con $n=m=10^6$. Per un server $P(L_1\ge k)=P(\text{Bin}(10^6,10^{-6})\ge k)$; per l'union bound $P(\max\ge k)\le n\,P(L_1\ge k)$.

• (a) Coda binomiale esatta: $n\,P(L_1\ge k)=1{,}125;\ 0{,}111;\ 0{,}01005;\ 0{,}00083$ per $k=9,10,11,12$. Per $k=11$ si è appena sopra $0{,}01$: il minimo con garanzia $1\%$ è $\boxed{k=12}$.
• (b) Il limite $\frac1{k!}$ (da $\binom nk n^{-k}\le\frac1{k!}$) dà $n/k!=2{,}76;\ 0{,}276;\ 0{,}0251;\ 0{,}0021$ per $k=9,\dots,12$: di nuovo $\boxed{k=12}$.
• Il teorema (con $3\ln n/\ln\ln n$) dà $k=\lceil3\cdot13{,}816/2{,}626\rceil=\lceil15{,}79\rceil=16$ con probabilità di errore $\le\frac1n$: una garanzia molto più forte ma con costante larga.
• Simulazione (300 prove di $10^6$ richieste): massimo $8$ in $105$ prove, $9$ in $160$, $10$ in $35$. Quindi $P(\max\ge10)\approx0{,}117$ (il valore dell'union bound esatto è $0{,}111$) e mai $\ge11$ in 300 prove.

Codice di verifica

import numpy as np
from math import comb, lgamma, log, log1p, exp, factorial

n, m = 1000, 1000
Ez = n * (1 - 1 / n) ** m
var = n * (n - 1) * (1 - 2 / n) ** m + Ez - Ez ** 2
print(round(Ez, 2), round(var, 2), round(var ** 0.5, 2), var / (400 - Ez) ** 2)

mm = 1
while n * (1 - 1 / n) ** mm > 0.05:      # minimo m con E[Z] <= 0,05
    mm += 1
print(mm)

N = 10 ** 6
def coda(k):                             # P(Bin(N, 1/N) >= k), somma dei primi 60 termini
    p = 1 / N
    return sum(exp(lgamma(N + 1) - lgamma(j + 1) - lgamma(N - j + 1)
                   + j * log(p) + (N - j) * log1p(-p)) for j in range(k, k + 60))
for k in (9, 10, 11, 12):
    print(k, round(N * coda(k), 5), round(N / factorial(k), 4))

rng = np.random.default_rng(5)
mx = [np.bincount(rng.integers(0, N, size=N), minlength=N).max() for _ in range(40)]
print(sorted(set(mx)), np.mean(mx))

Risultato: 367.7 97.23 9.86 0.0932, poi 9899, poi le righe 9 1.12517 2.7557, 10 0.11142 0.2756, 11 0.01005 0.0251, 12 0.00083 0.0021; l'ultima riga (40 prove) mostra massimi tra $8$ e $10$.