Esercizio - Union bound e inclusione-esclusione, due dadi e collisioni di una funzione hash

Testo.

1. Si lanciano due dadi equi. $A$: il primo dà $6$; $B$: il secondo dà $6$; $C$: la somma è $\ge10$. Calcolare $\Pr(A\cup B\cup C)$ con l'inclusione-esclusione e confrontarla con la somma delle probabilità e con la somma meno le coppie.
2. Si inseriscono $n$ chiavi in una tabella con $m=10^6$ celle, ogni chiave in una cella uniforme e indipendente. Con l'union bound, qual è il massimo $n$ per cui $\Pr[\text{collisione}]\le1\%$? Quanto vale la probabilità vera per quell'$n$ e qual è il massimo $n$ per il valore vero?
3. Quante celle $m$ servono per $n=1000$ chiavi e probabilità di collisione $\le10^{-3}$?

Teoria: Union bound e verifica randomizzata - identità polinomiali e prodotti di matriciSpazi discreti richiamati; inclusione-esclusione (con le troncate di Bonferroni) e union bound Pr[unione] ≤ somma, valido senza indipendenza e stretto quando gli eventi sono rari (collisioni: C(n,2)/m). Principio delle decisioni differite: si fissa tutto tranne una scelta casuale e si limita la probabilità su quella. Lemma di Schwartz-Zippel: un polinomio non nullo di grado totale d, valutato in un punto di S^n scelto uniformemente, si annulla con prob ≤ d/|S| (induzione sul numero di variabili); test di identità polinomiale con errore unilaterale, ripetuto (d/|S|)^k. Freivalds: per verificare AB=C si controlla A(Br)=Cr con r in {0,1}^n in tempo O(n^2), errore ≤ 1/2 (stretto), 2^-k con k prove. Fingerprint: due stringhe di n bit si confrontano con a mod p per un primo casuale p ≤ M, errore ≤ n/π(M).Union bound e verifica randomizzata - identità polinomiali e prodotti di matrici → (sezione 1); Tabelle hashTabella hash per implementare una mappa: funzione hash = hash code + compression function, bucket array, separate chaining; hash code per numeri e stringhe (polynomial, cyclic shift), division e MAD; load factor, complessità al caso pessimo Theta(n) e medio O(1+lambda), rehashing; esempio svolto con inserimenti e collisioni.Tabelle hash →.

Soluzione

Punto 1. Spazio: $36$ coppie equiprobabili. $\Pr(A)=\Pr(B)=\Pr(C)=\frac16$: per $C$ gli esiti sono $(4,6),(5,5),(6,4),(5,6),(6,5),(6,6)$, sei su $36$.

• $A\cap B=\{(6,6)\}$: $\frac1{36}$.
• $A\cap C=\{(6,4),(6,5),(6,6)\}$: $\frac3{36}$; $B\cap C=\{(4,6),(5,6),(6,6)\}$: $\frac3{36}$.
• $A\cap B\cap C=\{(6,6)\}$: $\frac1{36}$.

Inclusione-esclusione: $$\Pr(A\cup B\cup C)=\tfrac{18}{36}-\Big(\tfrac1{36}+\tfrac3{36}+\tfrac3{36}\Big)+\tfrac1{36}=\tfrac{18-7+1}{36}=\tfrac{12}{36}=\tfrac13 .$$ Conteggio diretto: la somma delle probabilità $\frac12$ è un maggiorante (union bound); somma meno le coppie $\frac{11}{36}=0{,}306$ è un minorante; il valore vero $\frac{12}{36}=\frac13$ sta in mezzo (disuguaglianze di Bonferroni).

Punto 2. Per ogni coppia di chiavi $\{i,j\}$ l'evento «stessa cella» ha probabilità $1/m$. L'union bound sulle $\binom n2$ coppie dà $\Pr\le\binom n2/m$. Si vuole $\frac{n(n-1)}{2\cdot10^6}\le0{,}01$, cioè $n(n-1)\le20000$. Con $n=141$: $141\cdot140=19740\le20000$; con $n=142$: $142\cdot141=20022>20000$. Quindi $n=141$ (bound $0{,}00987$).

• Probabilità vera per $n=141$: $1-\prod_{i=0}^{140}(1-i/m)=0{,}00982$, praticamente uguale al bound (eventi rari).
• Il valore vero rimane $\le1\%$ fino a $n=142$ ($0{,}00996$) e supera $1\%$ per $n=143$: il massimo vero è $142$, uno in più del bound.

Punto 3. $\binom{1000}2/m=\frac{499500}m\le10^{-3}$ dà $m\ge4{,}995\cdot10^8$: $m=5\cdot10^8$ (bound $0{,}0009990$, valore vero $0{,}0009985$). La $m$ minima per il valore vero è $499\,250\,542$, appena $0{,}15\%$ in meno ($749\,458$ celle su $5\cdot10^8$): qui l'union bound è quasi esatto.

Risultati: $\frac13$ (con $\frac12$ e $\frac{11}{36}$ come maggiorante e minorante); $n=141$ (vero $0{,}00982$); $m=5\cdot10^8$.

from fractions import Fraction as F
from math import comb
import itertools
S = list(itertools.product(range(1, 7), repeat=2))
P = lambda f: F(sum(1 for o in S if f(o)), 36)
A = lambda o: o[0] == 6; B = lambda o: o[1] == 6; C = lambda o: o[0] + o[1] >= 10
print(P(lambda o: A(o) or B(o) or C(o)), P(A) + P(B) + P(C), P(A) + P(B) + P(C) - F(7, 36))    # 1/3  1/2  11/36
def vero(n, m):
    q = 1.0
    for i in range(n): q *= (m - i) / m
    return 1 - q
print(comb(141, 2) / 1e6, vero(141, 10**6), vero(142, 10**6), vero(143, 10**6))
print(comb(1000, 2) / 5e8, vero(1000, 5 * 10**8))