Esercizio - Poissonizzazione di cento palline in cento urne e confronto con il modello esatto

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 →; carico massimo: 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 →.

Testo. Si lanciano $m=100$ palline in $n=100$ urne, ciascuna in un'urna uniforme e indipendentemente dalle altre ("modello esatto"). Nel "modello poissoniano" il numero di palline è invece $N\sim\text{Poisson}(100)$.

1. Nel modello poissoniano, qual è la legge dei carichi $L_1,\dots,L_n$? Calcolare il numero atteso di urne vuote e confrontarlo con il modello esatto.
2. Calcolare $P(\max_jL_j\ge k)$ per $k=4,\dots,7$ nei due modelli (esatto con un calcolo dei coefficienti, poissoniano con la formula del punto 1).
3. Dimostrare che ogni evento di probabilità $p_P$ nel modello poissoniano ha probabilità $\le e\sqrt m\,p_P$ nel modello esatto.
4. Usare il punto 3 per maggiorare $P(\max\ge10)$ nel modello esatto, e confrontare con il valore vero.

Soluzione

1. Ogni pallina del processo di Poisson va nell'urna $j$ con probabilità $\tfrac1n$: per la scomposizione i conteggi sono Poisson indipendenti di media $m/n=1$. Quindi $L_j\sim\text{Poisson}(1)$ i.i.d. e $P(L_j=0)=e^{-1}$. Urne vuote attese nel modello poissoniano: $100\,e^{-1}=36{,}79$. Nel modello esatto, $P(\text{urna vuota})=\bigl(1-\tfrac1{100}\bigr)^{100}$ e per linearità del valore atteso (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 →) le urne vuote attese sono $100\cdot0{,}99^{100}=36{,}60$. Differenza dello $0{,}5\%$.

2. Modello poissoniano: i carichi sono indipendenti, quindi $P(\max<k)=\bigl(P(\text{Poi}(1)<k)\bigr)^{100}$ e $$P(\max\ge k)=1-\Bigl(\sum_{j<k}\frac{e^{-1}}{j!}\Bigr)^{100}.$$ Per $k=5$: $P(\text{Poi}(1)\ge5)=0{,}003660$, quindi $1-(1-0{,}003660)^{100}=0{,}3070$. Modello esatto: $P(\max\le k)=\dfrac{m!}{n^m}\,[x^m]\Bigl(\sum_{j=0}^{k}\tfrac{x^j}{j!}\Bigr)^n$ (conteggio delle disposizioni con ogni urna di al più $k$ palline). Calcolato con frazioni esatte:

(simulazione di $10^5$ lanci: $P(\max\ge5)=0{,}298$). I due modelli danno valori molto vicini. Per $k\ge5$ nell'esatto le code sono un po' più leggere: i carichi hanno somma fissa $100$ (correlazione negativa), quindi i grandi valori sono un po' meno probabili; a $k=4$, evento tipico, il confronto si inverte.

3. Sia $E$ un evento che dipende dai carichi. Dalla formula delle probabilità totali sul numero di palline, $$p_P=\sum_{k\ge0}P(E\mid N=k)\,P(N=k)\ge P(E\mid N=m)\,P(N=m)=p_E\cdot e^{-m}\frac{m^m}{m!}.$$ Con la maggiorazione di Stirling $m!\le e\sqrt m\,(m/e)^m$ (per $m\ge1$) si ha $e^{-m}m^m/m!\ge\dfrac1{e\sqrt m}$, quindi $p_E\le e\sqrt m\,p_P$. Per $m=100$: $P(N=100)=0{,}03986\ge\tfrac1{e\cdot10}=0{,}03679$ ✓ e $e\sqrt{100}=27{,}18$. $\blacksquare$

4. Nel modello poissoniano $P(\max\ge10)=1-(1-P(\text{Poi}(1)\ge10))^{100}\approx1{,}11\cdot10^{-5}$ (con $P(\text{Poi}(1)\ge10)=1{,}11\cdot10^{-7}$). Nel modello esatto il punto 3 dà $P(\max\ge10)\le27{,}18\cdot1{,}11\cdot10^{-5}=\boxed{3{,}0\cdot10^{-4}}$. Il valore vero è $7{,}6\cdot10^{-6}$: la maggiorazione è larga, ma è sufficiente a mostrare che un carico $\ge10$ è un evento raro, senza calcolare i coefficienti esatti. Per eventi tipici (probabilità vicine a $\tfrac12$) il fattore $27$ è invece inutile, come mostra $27{,}18\cdot0{,}3070>1$ per $k=5$.

Codice di verifica

from fractions import Fraction as F
from math import exp, factorial, e, sqrt
import numpy as np

n = m = 100
poi = lambda j: exp(-1) / factorial(j)
print("urne vuote:", n * (1 - 1 / n)**m, n * exp(-1))

def pmax_le(k):                              # P(max <= k) esatta: m!/n^m [x^m] (sum_{j<=k} x^j/j!)^n
    base = [F(1, factorial(j)) if j <= k else F(0) for j in range(m + 1)]
    res, ex = [F(1)] + [F(0)] * m, n
    def mul(a, b):
        out = [F(0)] * (m + 1)
        for i, ai in enumerate(a):
            if ai:
                for j in range(m + 1 - i): out[i + j] += ai * b[j]
        return out
    while ex:
        if ex & 1: res = mul(res, base)
        base, ex = mul(base, base), ex >> 1
    return res[m] * factorial(m) / F(n)**m

for k in (4, 5, 6, 7, 8, 10):
    ex = 1 - float(pmax_le(k - 1))
    po = 1 - (1 - (1 - sum(poi(j) for j in range(k))))**n
    print(k, ex, po)
print("e sqrt(m) =", e * sqrt(m), " P(N=m) =", exp(-m) * m**m / factorial(m))
rng = np.random.default_rng(1)
mx = [np.bincount(rng.integers(0, n, m), minlength=n).max() for _ in range(100_000)]
print("simulazione P(max >= 5):", np.mean(np.array(mx) >= 5))