Esercizio - urne vuote e disuguaglianza delle differenze limitate

Teoria: Limiti di Chernoff e di HoeffdingMarkov applicato a e^(tX) dà code esponenziali. Per somme di Bernoulli indipendenti con media μ: P(X ≥ (1+δ)μ) ≤ [e^δ/(1+δ)^(1+δ)]^μ ≤ e^(-δ²μ/3) per 0<δ≤1, P(X ≤ (1-δ)μ) ≤ e^(-δ²μ/2), P(X ≥ R) ≤ 2^(-R) se R ≥ 6μ. Hoeffding per X_i in [a_i,b_i]: P(|S-E[S]| ≥ t) ≤ 2exp(-2t²/Σ(b_i-a_i)²). Applicazioni: n ≥ ln(2/δ)/(2ε²) campioni per stimare una probabilità, amplificazione BPP con k = O(log 1/ε) ripetizioni, bilanciamento di insiemi con scarto √(4m ln n).Limiti di Chernoff e di Hoeffding → (differenze limitate, Azuma-Hoeffding) e 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=1000$ palline in $n=1000$ urne, ognuna scelta uniformemente e indipendentemente. $Z$ è il numero di urne vuote.

1. Calcolare $E[Z]$ e $\mathrm{Var}(Z)$.
2. Mostrare che spostare una sola pallina cambia $Z$ al più di $1$.
3. Limitare $P(|Z-E[Z]|\ge t)$ per $t=50,100,150$ con Azuma, con McDiarmid e con Chebyshev.
4. Confrontare con una simulazione.

Soluzione

1. Media e varianza. $Z=\sum_{j=1}^nJ_j$, con $J_j=1$ se l'urna $j$ è vuota. $P(J_j=1)=(1-\frac1n)^m=:q_1$ e $P(J_j=J_k=1)=(1-\frac2n)^m=:q_2$ per $j\ne k$ (nessuna pallina in due urne fissate). Allora $$E[Z]=nq_1=1000\cdot0{,}999^{1000}=367{,}70\quad(\text{vicino a }n/e=367{,}88),$$ $$\mathrm{Var}(Z)=nq_1(1-q_1)+n(n-1)(q_2-q_1^2)=232{,}5-135{,}3=97{,}23,\quad\sigma=9.86.$$ Qui le $J_j$ non sono indipendenti (covarianza $q_2-q_1^2<0$): la formula tiene conto delle coppie. Controllo con enumerazione per $n=m=4$: $E[Z]=\frac{81}{64}=4\cdot(\frac34)^4$ e $\mathrm{Var}(Z)=\frac{1695}{4096}=0{,}4138$, che coincide con la formula ($4\cdot0{,}3164\cdot0{,}6836+12\,(0{,}0625-0{,}1001)=0{,}4138$).

2. Differenze limitate. $Z$ è funzione delle posizioni $X_1,\dots,X_m$ delle palline, indipendenti. Si sposta la pallina $i$ dall'urna $a$ all'urna $b$. L'urna $a$ diventa vuota solo se $i$ era la sua unica pallina ($Z$ aumenta di $1$); l'urna $b$ smette di essere vuota solo se lo era prima ($Z$ diminuisce di $1$); le altre urne non cambiano. Le due variazioni insieme danno $-1$, $0$ o $+1$. Quindi $c_i=1$ (verificato per enumerazione per $n=m=4$: la differenza massima è $1$).

3. Limiti. Con $\sum c_i^2=m=1000$:

• Azuma-Hoeffding (martingala): $2e^{-t^2/(2\cdot1000)}$.
• McDiarmid (variabili indipendenti): $2e^{-2t^2/1000}$.
• Chebyshev con la varianza esatta: $\frac{97{,}23}{t^2}$.

Per $t=150$ i due limiti esponenziali battono Chebyshev di ordini di grandezza; per $t=50$ e $t=100$ Azuma è peggiore di Chebyshev. Il vantaggio di Azuma e McDiarmid è che non richiedono di calcolare la varianza (qui servono le coppie di urne); il loro difetto è che la costante $c_i=1$ è pessimista rispetto allo scostamento vero ($\sigma=9{,}86$, mentre McDiarmid ragiona come se fosse $\approx\sqrt{m/4}=15{,}8$).

4. Simulazione. Su $20000$ lanci: media $367{,}61$, varianza $96{,}9$ (teoria $367{,}70$ e $97{,}2$), scarto massimo da $E[Z]$ pari a $39{,}3$ e $P(|Z-E[Z]|\ge30)=0{,}2\%$. Nessuna prova arriva a $50$, in accordo con tutti i limiti (che sono validi ma non stretti: la vera coda è circa gaussiana, con $\sigma=9{,}86$).

Risultato. $E[Z]=367{,}7$, $\mathrm{Var}(Z)=97{,}23$, $c_i=1$; per $t=100$: Azuma $0{,}0135$, McDiarmid $4{,}1\times10^{-9}$, Chebyshev $0{,}0097$.

Verifica.

import math
import numpy as np
from itertools import product
from fractions import Fraction as F

n = m = 1000
q1 = (1 - 1 / n)**m; q2 = (1 - 2 / n)**m
E = n * q1; V = n * q1 * (1 - q1) + n * (n - 1) * (q2 - q1 * q1)
print(E, V)                                             # 367.7 97.23
for t in (50, 100, 150):
    print(t, 2 * math.exp(-t * t / (2 * m)), 2 * math.exp(-2 * t * t / m), V / t**2)

# controllo di c_i = 1 e di media/varianza per n = m = 4
vuote = lambda t: 4 - len(set(t))
vals = [vuote(t) for t in product(range(4), repeat=4)]
diff = max(abs(vuote(t[:i] + (b,) + t[i + 1:]) - vuote(t)) for t in product(range(4), repeat=4) for i in range(4) for b in range(4))
E4 = F(sum(vals), len(vals)); print(diff, E4, F(sum(v * v for v in vals), len(vals)) - E4**2)   # 1 81/64 1695/4096

rng = np.random.default_rng(5)
Z = np.array([(np.bincount(rng.integers(0, n, size=m), minlength=n) == 0).sum() for _ in range(20000)])
print(Z.mean(), Z.var(), np.abs(Z - E).max(), np.mean(np.abs(Z - E) >= 30))