Esercizio - Paradosso del compleanno e collisioni di un hash a 32 bit

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 → (soglia del compleanno), Calcolo combinatorio per la probabilitàNegli spazi uniformi bisogna contare: principio di moltiplicazione, disposizioni con ripetizione n^k, disposizioni semplici n!/(n−k)!, permutazioni n!, combinazioni (n su k); estrazioni con e senza reinserimento e distribuzione ipergeometrica.Calcolo combinatorio per la probabilità →.

Testo. Si lanciano $m$ palline in $n$ urne in modo uniforme e indipendente. Con $n=365$ le palline sono persone e le urne i giorni dell'anno (anni non bisestili, compleanni uniformi).

1. Dimostrare, con il limite $P(\text{nessuna collisione})\le e^{-m(m-1)/2n}$, che $m=23$ basta per avere probabilità di collisione almeno $\frac12$ e che $m=22$ non è dimostrato dallo stesso limite. Calcolare poi le probabilità esatte per $m=22$ e $m=23$.
2. Quante persone servono per avere probabilità almeno $0{,}99$ di un compleanno comune?
3. Un sistema genera identificatori con un hash a $32$ bit ($n=2^{32}$ valori, uniformi). Dopo quanti identificatori la probabilità di collisione supera $10^{-3}$? E quella di $\frac12$?
4. Per $m=23$ calcolare il numero atteso di coppie con lo stesso compleanno e spiegare perché non coincide con la probabilità di almeno una coppia.
5. Calcolare il numero atteso $E[T]$ di persone da interrogare fino alla prima coincidenza (compresa) per $n=365$.

Soluzione

1. Limite superiore. La persona $i$ ($i=0,\dots,m-1$ già presenti) evita i giorni occupati con probabilità $1-\frac in$, quindi $P(\text{nessuna})=\prod_{i=0}^{m-1}(1-\frac in)\le\prod e^{-i/n}=e^{-m(m-1)/2n}$, dove si è usato $1-x\le e^{-x}$ e $\sum_{i<m}i=\frac{m(m-1)}2$. Si vuole che il membro di destra sia $\le\frac12$: $$\frac{m(m-1)}{2n}\ge\ln2\iff m(m-1)\ge2\cdot365\cdot\ln2=730\cdot0{,}69315=505{,}997.$$ Con $m=23$: $23\cdot22=506\ge505{,}997$ (di un soffio). Con $m=22$: $22\cdot21=462<505{,}997$, il limite non basta (e infatti la probabilità esatta è sotto $\frac12$). Esatto: $P(\text{coll.})=1-\prod_{i<m}(1-\frac i{365})$ vale $0{,}4757$ per $m=22$ e $\boxed{0{,}5073}$ per $m=23$; il limite dà $0{,}4689$ e $0{,}5000$.

2. Si cerca il minimo $m$ con $1-\prod(1-\frac i{365})\ge0{,}99$: per $m=56$ si ha meno di $0{,}99$ e per $m=57$ si ottiene $\boxed{0{,}9901}$. Dal limite: $e^{-m(m-1)/730}\le0{,}01$ dà $m(m-1)\ge730\ln100=3361{,}6$, $m\ge58{,}5$: $m=59$ è dimostrato, il valore esatto è appena sotto.

3. La formula approssimata $m\approx\sqrt{2n\ln\frac1{1-p}}$ viene dall'esponenziale. Per $p=10^{-3}$: $\sqrt{2\cdot2^{32}\cdot0{,}0010005}=2931{,}6$; il calcolo esatto del prodotto dà che servono $\boxed{2933}$ identificatori (probabilità $0{,}0010006$), $2932$ non bastano. Per $p=\frac12$: $\sqrt{2\cdot2^{32}\ln2}=77\,162{,}7$ e il valore esatto è $\boxed{77\,164}$ (con $77\,163$ la probabilità è $0{,}49999989$). Quindi un hash a $32$ bit non è adatto a identificare in modo unico decine di migliaia di oggetti.

4. Per la linearità il numero atteso di coppie coincidenti è $\binom{23}2\cdot\frac1{365}=\frac{253}{365}=0{,}6932$. Non è la probabilità di almeno una coppia ($0{,}5073$): la variabile $X$ = numero di coppie può valere più di $1$ (tre persone con lo stesso compleanno formano $3$ coppie; due coppie disgiunte ne danno $2$). Vale sempre $P(X\ge1)\le E[X]$ (Markov), qui $0{,}5073\le0{,}6932$; la differenza misura la sovrapposizione degli eventi.

5. $T$ = numero di persone fino alla prima coincidenza. $T>k$ significa nessuna coincidenza tra le prime $k$, quindi $P(T>k)=\prod_{i<k}(1-\frac i{365})$ e $E[T]=\sum_{k\ge0}P(T>k)=\boxed{24{,}617}$ (il termine $k=0$ vale $1$, e i termini sono nulli da $k=366$). Coincide con la formula asintotica $\sqrt{\frac{\pi n}2}+\frac23=23{,}94+0{,}67=24{,}61$ (si noti che la mediana è $23$, la media $24{,}6$).

Codice di verifica

from math import log, log1p, exp, sqrt

def p_coll(m, n):
    """Probabilità di almeno una collisione con m palline in n urne."""
    if m > n:                            # più palline che urne: collisione certa
        return 1.0
    return 1 - exp(sum(log1p(-i / n) for i in range(m)))

def minimo(p, n):
    lo, hi = 1, 10 ** 6
    while lo < hi:                       # ricerca binaria: p_coll è crescente in m
        mid = (lo + hi) // 2
        lo, hi = (lo, mid) if p_coll(mid, n) >= p else (mid + 1, hi)
    return lo

print(p_coll(22, 365), p_coll(23, 365))
print(minimo(0.99, 365), minimo(1e-3, 2**32), minimo(0.5, 2**32))
print(sum(1 - p_coll(k, 365) if k else 1 for k in range(366)))   # E[T]

Risultato: 0.4757 0.5073, poi 57 2933 77164, infine 24.6166.