Palline e urne - compleanno, carico massimo e approssimazione di Poisson

In questa pagina 6

Il modello più semplice di casualità negli algoritmi: chiavi in una tabella hash (Tabelle hash), job assegnati a server, pacchetti su collegamenti. Qui si studia il modello in sé; l'hashing con garanzie dimostrabili è in Hashing randomizzato - famiglie universali, filtri di Bloom e fingerprint. Prerequisiti: Calcolo combinatorio per la probabilità, Bernoulli, binomiale e uniforme discreta, Linearità del valore atteso e variabili indicatrici.

Definizione (palline e urne). Si lanciano $m$ palline in $n$ urne: ogni pallina sceglie la sua urna uniformemente e indipendentemente dalle altre. Il carico dell'urna $i$ è $L_i$ = numero di palline in $i$ . Vale $L_1+\dots+L_n=m$ .

Ogni $L_i$ è una $\text{Bin}(m,1/n)$ (Bernoulli, binomiale e uniforme discreta), con media $m/n$ . Ma $L_1,\dots,L_n$ non sono indipendenti: la somma è fissata a $m$ (se un'urna è piena le altre ricevono meno). Questa dipendenza è la difficoltà tecnica del modello, e l'approssimazione di Poisson in fondo serve a toglierla.

Il paradosso del compleanno

Domanda. Quante palline ( $m$ ) servono perché con probabilità almeno $1/2$ due finiscano nella stessa urna? Con $n=365$ è la domanda "quante persone perché due compiano gli anni lo stesso giorno".

La pallina $i$ evita le $i-1$ urne già occupate con probabilità $1-\frac{i-1}{n}$ , quindi $P(\text{nessuna collisione})=\prod_{i=0}^{m-1}\Bigl(1-\frac{i}{n}\Bigr).$

Teorema (soglia del compleanno). Per $m\le n/2$ $\exp\Bigl(-\frac{m(m-1)}{2n}-\frac{m^3}{3n^2}\Bigr)\ \le\ P(\text{nessuna collisione})\ \le\ \exp\Bigl(-\frac{m(m-1)}{2n}\Bigr).$ Quindi la collisione ha probabilità circa $1/2$ per $m\approx\sqrt{2n\ln 2}\approx 1{,}18\sqrt n$ : la soglia è $\Theta(\sqrt n)$ , non $\Theta(n)$ .

Dimostrazione. Estremo superiore: $1-x\le e^{-x}$ per ogni $x$ (la retta $1-x$ è tangente in $0$ alla funzione convessa $e^{-x}$ ), quindi $\prod(1-\frac in)\le\exp(-\sum_{i<m}\frac in)=\exp(-\frac{m(m-1)}{2n})$ perché $\sum_{i=0}^{m-1}i=\frac{m(m-1)}2$ . Estremo inferiore: per $0\le x\le\frac12$ vale $-\ln(1-x)=x+\frac{x^2}2+\frac{x^3}3+\dots\le x+x^2\bigl(\frac12+\frac x3+\frac{x^2}4+\dots\bigr)\le x+x^2$ (la parentesi è $<\frac12+\frac16+\frac1{16}+\dots<1$ ), cioè $1-x\ge e^{-x-x^2}$ . Si somma con $x=\frac in\le\frac12$ : $\sum_{i<m}\frac{i^2}{n^2}\le\frac{m^3}{3n^2}$ . $\square$

Esempio ( $n=365$ ). Il limite superiore dà $P(\text{nessuna})\le\frac12$ non appena $m(m-1)\ge 2n\ln2=2\cdot365\cdot0{,}6931=505{,}997$ . Con $m=23$ : $23\cdot22=506\ge505{,}997$ , quindi $m=23$ basta; con $m=22$ : $22\cdot21=462<506$ . Il calcolo esatto del prodotto conferma: $P(\text{collisione})=0{,}4757$ per $m=22$ e $0{,}5073$ per $m=23$ (il limite dà $0{,}4689$ e $0{,}5000$ ). Per il $99\%$ servono $m=57$ persone ( $0{,}9901$ ).

Grafico interattivo: Probabilità di nessuna collisione con n = 365: limite superiore e inferiore, e soglia 1/2 raggiunta a m = 23

Perché $\sqrt n$ . Le coppie di palline sono $\binom m2$ e ognuna collide con probabilità $\frac1n$ : per la linearità del valore atteso (Linearità del valore atteso e variabili indicatrici) il numero atteso di coppie in collisione è $\binom m2\frac1n\approx\frac{m^2}{2n}$ , che diventa $\Theta(1)$ per $m=\Theta(\sqrt n)$ . Lo stesso conto per le terne nella stessa urna dà $\binom m3\frac1{n^2}$ , quindi servono $m\approx(6)^{1/3}n^{2/3}$ palline ( $92{,}8$ per $n=365$ : con $m=88$ le terne attese sono $0{,}82$ ).

Conseguenza per l'hashing. Una funzione hash a $b$ bit ha $n=2^b$ valori. Con $b=32$ ci si aspetta la prima collisione dopo circa $\sqrt{\pi n/2}\approx 82\,000$ chiavi (il tempo atteso di prima collisione è $\sqrt{\pi n/2}+\frac23$ , vedi l'esercizio): $77\,164$ chiavi bastano già per probabilità $1/2$ . Nemmeno un hash a $32$ bit permette di identificare in modo affidabile milioni di oggetti.

Urne vuote

Teorema (urne vuote). Sia $Z$ il numero di urne vuote. Allora $E[Z]=n\Bigl(1-\frac1n\Bigr)^m\approx n\,e^{-m/n},\qquad \text{Var}(Z)=n(n-1)\Bigl(1-\frac2n\Bigr)^m+n\Bigl(1-\frac1n\Bigr)^m-n^2\Bigl(1-\frac1n\Bigr)^{2m}.$

Dimostrazione. $Z=\sum_i I_i$ con $I_i=1$ se l'urna $i$ è vuota. $P(I_i=1)=(1-\frac1n)^m$ perché ogni pallina deve evitare $i$ . Per la linearità $E[Z]=nP(I_1=1)$ . Per la varianza: $E[Z^2]=\sum_iE[I_i]+\sum_{i\ne j}E[I_iI_j]$ con $E[I_iI_j]=(1-\frac2n)^m$ (le $m$ palline evitano entrambe le urne $i$ e $j$ ), da cui $\text{Var}(Z)=E[Z^2]-E[Z]^2$ è la formula scritta. $\square$

Si usa $(1-\frac1n)^m\approx e^{-m/n}$ perché $1-x\le e^{-x}$ (e la differenza è piccola per $n$ grande). Per $m=n$ la frazione di urne vuote è $\approx e^{-1}=0{,}368$ e il resto ha carico $\ge1$ (alcune ne hanno molte). Esempio ( $n=m=1000$ ): $E[Z]=367{,}70$ e $\text{sd}(Z)=\sqrt{97{,}23}=9{,}86$ : una simulazione di $1000$ prove dà $367{,}7$ e $9{,}82$ . Lo scarto tipico è piccolo rispetto alla media: $Z$ è concentrato (varianza $O(n)$ , Momenti e deviazioni - Markov, Chebyshev e mediana randomizzata).

Quando non resta nessuna urna vuota. Con $m=n\ln n+cn$ palline $E[Z]\approx ne^{-m/n}=e^{-c}$ e, per Markov, $P(Z\ge1)\le E[Z]\approx e^{-c}$ . Per $n=1000$ e $m=n(\ln n+3)=9908$ si ha $E[Z]=0{,}0495$ : tutte le urne sono occupate con probabilità almeno $0{,}95$ . È il problema del collezionista di figurine (Linearità del valore atteso e variabili indicatrici): per riempire tutte le urne servono in media $nH_n\approx n\ln n$ palline.

Carico massimo

Con $m=n$ la media è $1$ , ma il carico massimo è molto più grande.

Teorema (carico massimo, estremo superiore). Lanciando $n$ palline in $n$ urne, con probabilità almeno $1-\frac1n$ il carico massimo è al più $k=\bigl\lceil\frac{3\ln n}{\ln\ln n}\bigr\rceil$ (per $n\ge16$ , così che $\ln\ln n>1$ ).

Dimostrazione. Si fissa l'urna $1$ . Per avere almeno $k$ palline bisogna scegliere $k$ palline ( $\binom nk$ modi) che vadano tutte lì (probabilità $n^{-k}$ ). Per l'union bound sui sottoinsiemi (Union bound e verifica randomizzata - identità polinomiali e prodotti di matrici): $P(L_1\ge k)\le\binom nk\frac1{n^k}\le\frac{n^k}{k!\,n^k}=\frac1{k!}\le\Bigl(\frac ek\Bigr)^k,$ dove l'ultimo passo è $k!\ge(k/e)^k$ (da $e^k=\sum_j k^j/j!\ge k^k/k!$ ). Per $k\ge\frac{3\ln n}{\ln\ln n}$ si vuole $(e/k)^k\le n^{-2}$ . Posto $t=\ln\ln n$ , $k_0=\frac{3\ln n}{t}$ e usando la disuguaglianza della tangente $\ln t\le\frac t3+\ln3-1$ (la concava $\ln t$ sta sotto la tangente in $t=3$ ): $\ln\frac{k_0}{e}=\ln3+t-\ln t-1\ge\frac{2t}3\quad\Longrightarrow\quad k_0\ln\frac{k_0}e\ge\frac{3\ln n}{t}\cdot\frac{2t}3=2\ln n.$ Quindi $(e/k_0)^{k_0}\le n^{-2}$ , e vale anche per $k\ge k_0$ intero perché $(e/k)^k$ decresce per $k\ge1$ . Un'ultima union bound sulle $n$ urne: $P(\max L_i\ge k)\le n\cdot n^{-2}=\frac1n$ . $\square$

L'estremo inferiore ha lo stesso ordine (si dimostra con il metodo del secondo momento, Momenti e deviazioni - Markov, Chebyshev e mediana randomizzata): con probabilità alta $\max_i L_i\ge(1-o(1))\frac{\ln n}{\ln\ln n}$ . Quindi il carico massimo è $\Theta(\ln n/\ln\ln n)$ , e non $O(1)$ come la media. Con $m\ge n\ln n$ palline il carico massimo è invece $\frac mn+O\bigl(\sqrt{\frac mn\ln n}\bigr)$ , cioè vicino alla media (Chernoff, Limiti di Chernoff e di Hoeffding).

Numeri ( $n=10^6$ ). La costante $3$ è larga: il limite dimostrato dà $k=16$ , mentre il conto con la binomiale esatta dà $n\cdot P(\text{Bin}(n,1/n)\ge k)=0{,}111$ per $k=10$ , $0{,}0100$ per $k=11$ e $0{,}0008$ per $k=12$ . Nelle simulazioni il massimo è quasi sempre $8$ o $9$ , e $10$ in circa una prova su dieci, come prevede il valore $0{,}111$ . Il confronto è nella tabella.

$n$	$\ln n/\ln\ln n$	massimo osservato (una scelta)	massimo osservato (due scelte)
$10^3$	$3{,}57$	da $4$ a $7$ (più spesso $5$ )	$3$
$10^4$	$4{,}15$	da $5$ a $9$ (più spesso $6$ o $7$ )	$3$ o $4$
$10^5$	$4{,}71$	da $7$ a $10$ (più spesso $7$ o $8$ )	$3$ o $4$
$10^6$	$5{,}26$	da $8$ a $10$ (più spesso $9$ )	$4$

La crescita è lenta (logaritmo di un logaritmo): per questo in pratica le tabelle hash con catene hanno catene lunghe al massimo qualche unità.

Approssimazione di Poisson

Per $n$ grande $\text{Bin}(m,\frac1n)\approx\text{Poi}(\lambda)$ con $\lambda=\frac mn$ (Distribuzione di Poisson). Per $m=n=100$ la probabilità che un'urna abbia $k$ palline è:

$k$	$0$	$1$	$2$	$3$	$4$	$5$
binomiale	$0{,}3660$	$0{,}3697$	$0{,}1849$	$0{,}0610$	$0{,}0149$	$0{,}0029$
Poisson $(1)$	$0{,}3679$	$0{,}3679$	$0{,}1839$	$0{,}0613$	$0{,}0153$	$0{,}0031$

La distanza in variazione totale tra le due leggi vale $0{,}0293$ per $n=10$ , $0{,}0028$ per $n=100$ e $0{,}00028$ per $n=1000$ (cala come $1/n$ ). Il modello di Poisson sostituisce i carichi con $n$ variabili $Y_i\sim\text{Poi}(m/n)$ indipendenti: la somma non è più fissa, ma i calcoli diventano un prodotto di probabilità.

Teorema (esatto contro Poisson). Sia $L=(L_1,\dots,L_n)$ il vettore dei carichi esatti e $Y=(Y_1,\dots,Y_n)$ quello Poisson con media $m/n$ . Per ogni funzione $f\ge0$ $E[f(L)]\le e\sqrt m\;E[f(Y)].$ In particolare, per ogni evento $A$ sui carichi: $P(L\in A)\le e\sqrt m\,P(Y\in A)$ .

Dimostrazione. (1) Condizionando a $\sum Y_i=m$ , il vettore $Y$ ha la stessa legge di $L$ : infatti $P\Bigl(Y=y\ \Big|\ \textstyle\sum Y_i=m\Bigr)=\frac{\prod_i e^{-m/n}(m/n)^{y_i}/y_i!}{e^{-m}m^m/m!}=\frac{m!}{\prod_iy_i!}\,n^{-m},$ la multinomiale con $n$ urne equiprobabili. (2) $E[f(Y)]=\sum_jP(\sum Y_i=j)E[f(Y)\mid\sum Y_i=j]\ge P(\sum Y_i=m)\,E[f(L)]$ . (3) $\sum Y_i\sim\text{Poi}(m)$ , quindi $P(\sum Y_i=m)=e^{-m}m^m/m!\ge\frac1{e\sqrt m}$ per la disuguaglianza $m!\le e\sqrt m\,(m/e)^m$ . $\square$

Uso. Per $n=m=1000$ si vuole $P(\max L_i\ge10)$ . Nel modello di Poisson l'union bound dà $n\,P(\text{Poi}(1)\ge10)=1{,}1\cdot10^{-4}$ , e il teorema moltiplica per $e\sqrt{1000}=85{,}96$ : $P(\max L_i\ge10)\le0{,}0096$ . Il fattore $e\sqrt m$ è grande ma costante rispetto agli esponenziali in gioco, e si può usare per qualsiasi evento: quando la probabilità nel modello Poisson è $o(1/\sqrt m)$ lo è anche nel modello esatto.

Il potere delle due scelte

Algoritmo (due scelte). Per ogni pallina si scelgono due urne a caso e la pallina va in quella meno carica (a parità, una qualsiasi).

Il carico massimo cala da $\Theta(\ln n/\ln\ln n)$ a $\frac{\ln\ln n}{\ln 2}+O(1)$ con alta probabilità: un miglioramento esponenziale con una sola scelta in più. Con $d\ge2$ scelte è $\frac{\ln\ln n}{\ln d}+O(1)$ . Idea della dimostrazione: indicando con $\beta_i$ la frazione di urne con carico $\ge i$ , un'urna raggiunge il carico $i+1$ solo se entrambe le scelte cadono su urne di carico $\ge i$ , quindi $\beta_{i+1}\lesssim\beta_i^2$ e la frazione crolla con esponente doppio ( $\beta_i\approx2^{-2^{i}}$ ); si ferma quando $\beta_i<1/n$ , cioè dopo $\log_2\log_2 n$ passi. Applicazioni: bilanciamento del carico tra server, hashing con due funzioni, cuckoo hashing. Nei numeri della tabella sopra, $n=10^6$ passa da $8$ - $9$ a $4$ .

python

import random

def max_carico(n, scelte=1):
    c = [0] * n
    for _ in range(n):                       # n palline in n urne
        i = min((random.randrange(n) for _ in range(scelte)), key=lambda j: c[j])
        c[i] += 1                            # va nell'urna meno carica fra le scelte
    return max(c)

print(max_carico(10**5, 1), max_carico(10**5, 2))   # tipicamente 7 o 8, e 3 o 4

Domande d'esame

Dimostra che con $m=\lceil\sqrt{2n\ln 2}\rceil+1$ palline la probabilità di collisione è almeno $1/2$ . Per $m(m-1)\ge2n\ln2$ , il limite superiore $\prod(1-\frac in)\le e^{-m(m-1)/2n}\le e^{-\ln2}=\frac12$ dà $P(\text{collisione})\ge\frac12$ ; con $m-1\ge\sqrt{2n\ln2}$ si ha $m(m-1)\ge(m-1)^2\ge2n\ln2$ .
Quante urne vuote ci si aspetta lanciando $n$ palline in $n$ urne, e perché? $n(1-\frac1n)^n\approx n/e$ : per l'indicatore di ogni urna vale $(1-\frac1n)^n$ , e la linearità non richiede indipendenza.
Perché non basta il limite $P(L_1\ge k)\le1/k!$ per concludere sul massimo? Vale per una singola urna; per il massimo serve la union bound sulle $n$ urne, quindi la probabilità per una singola urna va portata sotto $1/n^2$ (così la somma sulle $n$ urne resta $\le 1/n$ ), cioè $k!\ge n^{2}$ , che dà $k=\Theta(\ln n/\ln\ln n)$ .
Cosa dice il teorema esatto contro Poisson e come si dimostra? Che ogni evento ha nel modello esatto probabilità al più $e\sqrt m$ volte quella nel modello Poisson: si condiziona il modello Poisson alla somma $m$ (diventa la multinomiale) e si limita dal basso $P(\text{Poi}(m)=m)\ge1/(e\sqrt m)$ .

Versione ripasso

Modello. $m$ palline, $n$ urne, scelte indipendenti e uniformi; carico $L_i\sim\text{Bin}(m,1/n)$ (Bernoulli, binomiale e uniforme discreta), ma i $L_i$ sono dipendenti perché $\sum L_i=m$ . Gli indicatori e la linearità (Linearità del valore atteso e variabili indicatrici) non richiedono indipendenza e sono lo strumento principale.
Compleanno. $P(\text{nessuna collisione})=\prod_{i<m}(1-\frac in)$ . Superiormente $\le e^{-m(m-1)/2n}$ perché $1-x\le e^{-x}$ (tangente in $0$ della convessa $e^{-x}$ ); inferiormente $\ge\exp(-\frac{m(m-1)}{2n}-\frac{m^3}{3n^2})$ per $m\le n/2$ , perché $1-x\ge e^{-x-x^2}$ se $x\le\frac12$ . La soglia $1/2$ è a $m(m-1)\ge2n\ln2$ , cioè $m\approx1{,}18\sqrt n$ : per $n=365$ basta $m=23$ ( $23\cdot22=506\ge505{,}997$ ; esatto $0{,}5073$ , con $m=22$ solo $0{,}4757$ ), per il $99\%$ servono $57$ persone.
Perché $\sqrt n$ . Coppie in collisione attese $\binom m2/n\approx m^2/2n$ , che vale $1$ per $m\approx\sqrt{2n}$ ; per le terne $\binom m3/n^2$ , soglia $m\approx6^{1/3}n^{2/3}$ ( $92{,}8$ per $n=365$ ). Prima collisione dopo $\sqrt{\pi n/2}+\frac23$ palline in media. Hash a $32$ bit: $77\,164$ chiavi per probabilità $1/2$ .
Urne vuote. $Z=\sum I_i$ , $P(I_i=1)=(1-\frac1n)^m$ , quindi $E[Z]=n(1-\frac1n)^m\approx ne^{-m/n}$ (per $m=n$ : $n/e$ ). Per la varianza $E[I_iI_j]=(1-\frac2n)^m$ , da cui $\text{Var}(Z)=n(n-1)(1-\frac2n)^m+n(1-\frac1n)^m-n^2(1-\frac1n)^{2m}$ . Con $n=m=1000$ : $E[Z]=367{,}70$ , deviazione standard $9{,}86$ (simulazione $367{,}7$ e $9{,}82$ ). Con $m=n(\ln n+c)$ : $E[Z]\approx e^{-c}$ , e per Markov $P(\text{urna vuota})\le e^{-c}$ (per $n=1000$ , $c=3$ : $0{,}0495$ ); in media servono $nH_n$ palline.
Carico massimo ( $m=n$ ). $P(L_1\ge k)\le\binom nk n^{-k}\le\frac1{k!}\le(\frac ek)^k$ . Con $k=\lceil\frac{3\ln n}{\ln\ln n}\rceil$ e $t=\ln\ln n$ : $\ln\frac ke=\ln3+t-\ln t-1\ge\frac{2t}3$ (tangente $\ln t\le\frac t3+\ln3-1$ ), quindi $k\ln\frac ke\ge2\ln n$ e $(\frac ek)^k\le n^{-2}$ ; union bound sulle $n$ urne: $P(\max L_i\ge k)\le\frac1n$ . L'ordine è $\Theta(\ln n/\ln\ln n)$ (estremo inferiore: secondo momento). Con $n=10^6$ la binomiale esatta dà $n\,P(L_1\ge k)=0{,}111;\ 0{,}0100;\ 0{,}0008$ per $k=10,11,12$ ; osservato di solito $8$ o $9$ . Per $m\ge n\ln n$ : $\frac mn+O(\sqrt{\frac mn\ln n})$ (Limiti di Chernoff e di Hoeffding).
Poisson. $\text{Bin}(m,\frac1n)\approx\text{Poi}(\frac mn)$ (Distribuzione di Poisson); distanza in variazione totale $0{,}0293;\ 0{,}0028;\ 0{,}00028$ per $n=10,100,1000$ . Modello con $Y_i\sim\text{Poi}(m/n)$ indipendenti. Teorema: $E[f(L)]\le e\sqrt m\,E[f(Y)]$ per $f\ge0$ . Dimostrazione: (1) condizionato a $\sum Y_i=m$ , $Y$ è multinomiale come $L$ ; (2) $E[f(Y)]\ge P(\sum Y_i=m)E[f(L)]$ ; (3) $P(\text{Poi}(m)=m)=e^{-m}m^m/m!\ge\frac1{e\sqrt m}$ da $m!\le e\sqrt m(m/e)^m$ . Esempio $n=m=1000$ : $P(\max\ge10)\le85{,}96\cdot1{,}1\cdot10^{-4}\le0{,}0096$ .
Due scelte. Pallina nell'urna meno carica fra due a caso: massimo $\frac{\ln\ln n}{\ln2}+O(1)$ , perché $\beta_{i+1}\lesssim\beta_i^2$ ( $\beta_i$ frazione di urne con carico $\ge i$ ); con $d$ scelte $\frac{\ln\ln n}{\ln d}+O(1)$ . Per $n=10^6$ si passa da $8$ - $9$ a $4$ . Usi: bilanciamento del carico, cuckoo hashing (Tabelle hash).
Errori tipici. Soglia del compleanno $\Theta(n)$ invece di $\Theta(\sqrt n)$ ; trattare i carichi come indipendenti senza il fattore $e\sqrt m$ ; dimenticare l'union bound sulle $n$ urne; scambiare $1/k!$ per un limite sul massimo.