Esercizio - Approssimazione di Poisson dei carichi e limite sul carico massimo

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 → (approssimazione di Poisson e teorema esatto contro Poisson), 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 →.

Testo. Si lanciano $n$ palline in $n$ urne ($m=n$).

1. Per $n=100$ confrontare la probabilità esatta che un'urna abbia $k$ palline ($k=0,\dots,5$) con quella di $\text{Poi}(1)$ e calcolare la distanza in variazione totale. Quante urne vuote ci si aspetta secondo i due modelli?
2. Dimostrare che $P(\text{Poi}(m)=m)\ge\frac1{e\sqrt m}$ usando $m!\le e\sqrt m\,(m/e)^m$, e verificare la disuguaglianza per $m=100$.
3. Usando il teorema $P(L\in A)\le e\sqrt m\,P(Y\in A)$ con l'union bound nel modello di Poisson, dare un limite superiore a $P(\max_iL_i\ge k)$ per $n=1000$ e $k=8,9,10$, e confrontarlo con una simulazione.
4. Rifare il confronto per $n=100$ e $k=5,6,7,8$. Quando il limite è inutile?

Soluzione

1. Binomiale contro Poisson. $L_i\sim\text{Bin}(100,\frac1{100})$, quindi $P(L_i=k)=\binom{100}k0{,}01^k0{,}99^{100-k}$:

La distanza in variazione totale $\frac12\sum_k|P_{\text{Bin}}(k)-P_{\text{Poi}}(k)|$ vale $\boxed{0{,}00278}$. Urne vuote attese: $100\cdot0{,}36603=36{,}60$ (esatto) contro $100\cdot e^{-1}=36{,}79$ (Poisson). Il modello di Poisson dà frazioni quasi identiche, con errore sotto l'$1\%$.

2. $P(\text{Poi}(m)=m)=\frac{e^{-m}m^m}{m!}$. Dalla disuguaglianza $m!\le e\sqrt m\,(m/e)^m=e\sqrt m\,m^me^{-m}$ si ha $$\frac{e^{-m}m^m}{m!}\ge\frac{e^{-m}m^m}{e\sqrt m\,m^me^{-m}}=\frac1{e\sqrt m}.$$ Per $m=100$: il membro sinistro vale $0{,}03986$ e il destro $\frac1{e\cdot10}=0{,}03679$. (Il valore giusto è $\approx\frac1{\sqrt{2\pi m}}=0{,}03989$ per Stirling: il fattore $e$ al posto di $\sqrt{2\pi}=2{,}507$ è il prezzo di una disuguaglianza valida per ogni $m$.)

3. Limite per $n=1000$. Nel modello di Poisson $Y_i\sim\text{Poi}(1)$ sono indipendenti e per l'union bound $$P(\max Y_i\ge k)\le n\,P(\text{Poi}(1)\ge k).$$ Il teorema moltiplica per $e\sqrt m=e\sqrt{1000}=85{,}96$:

Il limite è corretto ma più largo di un fattore $\approx86$ (il fattore $e\sqrt m$ stesso), e per $k=8$ vale $0{,}88$: utile solo per $k\ge9$. Si noti che nel modello Poisson l'union bound è quasi esatto (il valore $n\,P(\text{Poi}\ge k)$ è molto vicino alla simulazione nel modello esatto), quindi tutto lo spreco è nel fattore $e\sqrt m$.

4. $n=100$. Ora il fattore è $e\sqrt{100}=27{,}18$.

Per $k=5,6$ il limite supera $1$: vuoto. Il metodo è utile solo quando $n\,P(\text{Poi}\ge k)\ll\frac1{e\sqrt m}$, cioè sulle code lontane. L'union bound sul modello esatto, senza il fattore, dà $0{,}0071$ per $k=7$ ma richiede di gestire la dipendenza tra i carichi.

Codice di verifica

import numpy as np
from math import comb, exp, factorial, e, sqrt

n = 100
bino = [comb(n, k) * 0.01 ** k * 0.99 ** (n - k) for k in range(6)]
poi = [exp(-1) / factorial(k) for k in range(6)]
print([round(x, 5) for x in bino], [round(x, 5) for x in poi])
print(0.5 * sum(abs(comb(n, k) * 0.01 ** k * 0.99 ** (n - k) - exp(-1) / factorial(k)) for k in range(n + 1)))

def prova(n, T, ks):
    rng = np.random.default_rng(1)
    mx = np.array([np.bincount(rng.integers(0, n, size=n), minlength=n).max() for _ in range(T)])
    for k in ks:
        P = n * (1 - sum(exp(-1) / factorial(j) for j in range(k)))     # n P(Poi(1) >= k)
        print(n, k, round(P, 5), round(P * e * sqrt(n), 4), (mx >= k).mean())

prova(1000, 100000, (8, 9, 10))
prova(100, 100000, (5, 6, 7, 8))

Risultato: le due liste della tabella, 0.002775, poi righe n k P limite frequenza come 1000 8 0.01025 0.881 0.00964 e 100 6 0.05942 1.6152 0.0533 (i valori delle due tabelle).