Limiti di Chernoff e di Hoeffding

ChebyshevVar(ΣX_i) = ΣVar + 2ΣCov, e basta l'indipendenza a coppie perché la varianza si sommi. Chebyshev dà code polinomiali (collezionista: P(T ≥ nH_n + cn) ≤ π²/(6c²)); il metodo del secondo momento dà P(X=0) ≤ Var(X)/E[X]². Algoritmo della mediana: campione di n^(3/4) elementi, due estremi d e u a ±√n, ordinamento dei soli elementi tra d e u; fallisce con probabilità ≤ n^(-1/4) ed è Las Vegas con 2n + o(n) confronti.Momenti e deviazioni - Markov, Chebyshev e mediana randomizzata → limita la coda con $1/a^2$. Per somme di variabili indipendenti si può fare molto meglio: la coda decresce in modo esponenziale. L'idea è sempre la stessa: Markov applicato a $e^{tX}$. Prerequisiti: Funzione generatrice dei momentiLa funzione generatrice dei momenti M_X(t) = E[e^(tX)] (quando è finita vicino a 0) produce i momenti per derivazione, E[X^k] = M_X^(k)(0); trasforma le somme di v.a. indipendenti in prodotti, M_(X+Y) = M_X M_Y, e se finita in un intorno di 0 determina la legge.Funzione generatrice dei momenti →, Disuguaglianze di Markov, Chebyshev e JensenMarkov: per X ≥ 0, P(X ≥ a) ≤ E[X]/a; Chebyshev: P(|X − μ| ≥ ε) ≤ Var(X)/ε²; Jensen: per φ convessa, φ(E[X]) ≤ E[φ(X)]. Stimano probabilità e medie conoscendo solo media e varianza.Disuguaglianze di Markov, Chebyshev e Jensen →, Bernoulli, binomiale e uniforme discretaBernoulli Be(p): un solo tentativo, vale 1 con probabilità p; binomiale Bin(n, p): numero di successi in n prove indipendenti, P(X = k) = C(n,k) p^k (1−p)^(n−k), media np e varianza np(1−p); uniforme discreta: n valori equiprobabili.Bernoulli, binomiale e uniforme discreta →.

Il metodo della funzione generatrice dei momenti

Per ogni $t>0$ la funzione $x\mapsto e^{tx}$ è crescente e positiva, quindi $X\ge a \iff e^{tX}\ge e^{ta}$. Markov dà $$P(X \ge a) = P(e^{tX} \ge e^{ta}) \le \frac{E[e^{tX}]}{e^{ta}} = e^{-ta}\,M_X(t),$$ e si sceglie $t>0$ che rende minimo il secondo membro. Per la coda inferiore si usa $t<0$: $P(X\le a)=P(e^{tX}\ge e^{ta})\le e^{-ta}M_X(t)$.

Il vantaggio rispetto a Chebyshev è che se $X=X_1+\dots+X_n$ con $X_i$ indipendenti, la funzione generatrice si fattorizza: $$M_X(t) = E\Big[\prod_i e^{tX_i}\Big] = \prod_i M_{X_i}(t).$$ Qui l'indipendenza (non solo a coppie) è indispensabile.

Chernoff per somme di Bernoulli

Ipotesi. $X=\sum_{i=1}^n X_i$, con $X_i\in\{0,1\}$ indipendenti, $P(X_i=1)=p_i$ (le $p_i$ possono essere diverse: variabili di Poisson-Bernoulli). $\mu=E[X]=\sum_i p_i$.

Funzione generatrice. $M_{X_i}(t)=1-p_i+p_ie^t=1+p_i(e^t-1)\le e^{p_i(e^t-1)}$, perché $1+y\le e^y$. Moltiplicando: $$M_X(t)\le \exp\big(\mu(e^t-1)\big).$$

Teorema (Chernoff, forma esatta). $$P\big(X\ge(1+\delta)\mu\big)\le\Big[\frac{e^{\delta}}{(1+\delta)^{1+\delta}}\Big]^{\mu}\quad(\delta>0),\qquad P\big(X\le(1-\delta)\mu\big)\le\Big[\frac{e^{-\delta}}{(1-\delta)^{1-\delta}}\Big]^{\mu}\quad(0<\delta<1).$$

Dimostrazione. Coda superiore, $t>0$: $P(X\ge(1+\delta)\mu)\le e^{-t(1+\delta)\mu}e^{\mu(e^t-1)}=\exp\big(\mu(e^t-1-t(1+\delta))\big)$. L'esponente ha derivata $\mu(e^t-(1+\delta))$ che si annulla in $t=\ln(1+\delta)>0$ (minimo, perché è convesso). Sostituendo $e^t=1+\delta$: $\exp(\mu(\delta-(1+\delta)\ln(1+\delta)))$, cioè $\big[e^\delta/(1+\delta)^{1+\delta}\big]^\mu$. Coda inferiore, $t<0$: $P(X\le(1-\delta)\mu)\le\exp\big(\mu(e^t-1-t(1-\delta))\big)$ e si prende $t=\ln(1-\delta)<0$: $e^t=1-\delta$, esponente $\mu(-\delta-(1-\delta)\ln(1-\delta))$. $\blacksquare$

Forme semplificate

Teorema. Con le stesse ipotesi:

1. per $0<\delta\le1$: $P(X\ge(1+\delta)\mu)\le e^{-\delta^2\mu/3}$;
2. per $0<\delta<1$: $P(X\le(1-\delta)\mu)\le e^{-\delta^2\mu/2}$;
3. per $R\ge 6\mu$: $P(X\ge R)\le 2^{-R}$.

Insieme: $P(|X-\mu|\ge\delta\mu)\le 2e^{-\delta^2\mu/3}$ per $0<\delta\le1$.

Dimostrazione. (1) Si deve mostrare $f(\delta)=\delta-(1+\delta)\ln(1+\delta)+\delta^2/3\le0$ su $[0,1]$. Si ha $f(0)=0$, $f'(\delta)=-\ln(1+\delta)+\frac{2\delta}{3}$, $f'(0)=0$ e $f''(\delta)=-\frac1{1+\delta}+\frac23$, negativa per $\delta<\frac12$ e positiva dopo. Quindi $f'$ prima scende da $0$ e poi risale, e a fine intervallo $f'(1)=\frac23-\ln2=-0{,}026<0$: $f'\le0$ su tutto $[0,1]$, dunque $f$ è decrescente da $f(0)=0$ e $f\le 0$. (2) Serve $-\delta-(1-\delta)\ln(1-\delta)\le-\delta^2/2$. Lo sviluppo $(1-\delta)\ln(1-\delta)=-\delta+\frac{\delta^2}{2}+\frac{\delta^3}{6}+\frac{\delta^4}{12}+\dots$ ha tutti i termini oltre $-\delta+\delta^2/2$ positivi, quindi $(1-\delta)\ln(1-\delta)\ge-\delta+\delta^2/2$ e si conclude. (3) Si pone $R=(1+\delta)\mu$. Dal limite esatto, $P(X\ge R)\le e^{R-\mu}\,(\mu/R)^{R}\le(e\mu/R)^R\le(e/6)^R\le2^{-R}$, perché $e/6=0{,}453<\frac12$. $\blacksquare$

I due limiti con $e^{-\delta^2\mu/3}$ e $e^{-\delta^2\mu/2}$ sono comodi ma non stretti. Se di $\mu$ si conosce solo un maggiorante $\mu_H\ge E[X]$ i limiti superiori valgono con $\mu_H$ al posto di $\mu$. Per $\delta>1$ si può usare $e^{-\mu\delta^2/(2+\delta)}$, valida per ogni $\delta>0$: dimostrazione, e un esempio di che cosa succede quando l'indipendenza manca, in Esercizio - Chernoff e i mutui del 2008, perché serve l'indipendenza (lezioni MIT).

Confronto numerico

Lancio di 1000 monete, probabilità di almeno $600$ teste ($\mu=500$, $\delta=0{,}2$):

Chernoff passa da $0{,}0125$ di Chebyshev a $10^{-4}$. Hoeffding è molto più vicino al vero perché sfrutta che per $p=\frac12$ la varianza è la metà di $\mu$; Chernoff, che usa solo la media, è più adatto a $p$ piccolo (conteggio di eventi rari). Anche la forma esatta di Chernoff, per $\mu$ fissato, è più stretta della semplificata.

Il limite di Hoeffding

Chernoff vale per variabili 0-1. Per variabili limitate qualsiasi si usa Hoeffding.

Lemma di Hoeffding. Se $a\le X\le b$ e $E[X]=0$, per ogni $s\in\mathbb R$: $E[e^{sX}]\le e^{s^2(b-a)^2/8}$.

Dimostrazione. Per la convessità di $x\mapsto e^{sx}$, su $[a,b]$ sta sotto la corda: $e^{sx}\le\frac{b-x}{b-a}e^{sa}+\frac{x-a}{b-a}e^{sb}$. Prendendo la media con $E[X]=0$: $$E[e^{sX}]\le\frac{b}{b-a}e^{sa}-\frac{a}{b-a}e^{sb}.$$ Con $p=-\frac{a}{b-a}\in[0,1]$ e $u=s(b-a)$ il secondo membro è $e^{\varphi(u)}$, $\varphi(u)=-pu+\ln(1-p+pe^u)$. Si ha $\varphi(0)=0$, $\varphi'(0)=0$ e $\varphi''(u)=q(1-q)\le\frac14$, con $q=\frac{pe^u}{1-p+pe^u}\in[0,1]$. Per Taylor con resto di Lagrange $\varphi(u)=\frac12\varphi''(\xi)u^2\le\frac{u^2}{8}=\frac{s^2(b-a)^2}{8}$. $\blacksquare$

Teorema (Hoeffding). $X_1,\dots,X_n$ indipendenti con $a_i\le X_i\le b_i$, $S=\sum X_i$, $c=\sum_i(b_i-a_i)^2$. Per ogni $t>0$: $$P(S-E[S]\ge t)\le e^{-2t^2/c},\qquad P(|S-E[S]|\ge t)\le2e^{-2t^2/c}.$$

Dimostrazione. Per $s>0$, Markov su $e^{s(S-E[S])}$ e indipendenza: $P(S-E[S]\ge t)\le e^{-st}\prod_iE[e^{s(X_i-E[X_i])}]\le e^{-st}\prod_ie^{s^2(b_i-a_i)^2/8}=\exp(-st+s^2c/8)$. Il minimo è in $s=4t/c$ e vale $\exp(-2t^2/c)$. L'altra coda è identica con $-X_i$. $\blacksquare$

Per $n$ monete $c=n$: $P(S-\frac n2\ge t)\le e^{-2t^2/n}$. Con $n=1000$ e $t=100$ si ottiene $e^{-20}=2{,}06\times10^{-9}$, il valore della tabella.

Quale limite usare.

• Solo media e varianza note: Chebyshev.
• Conteggio di eventi 0-1 con media piccola, o errore relativo (scarto $\delta\mu$ proporzionale alla media): Chernoff.
• Variabili limitate, errore additivo: Hoeffding.

Applicazioni

Stima di una probabilità con intervallo di confidenza

Si vuole stimare $p$ (per esempio la frazione di input su cui un programma sbaglia) con $n$ campioni indipendenti $X_i\in\{0,1\}$ e $\hat p=\frac1n\sum X_i$ (Legge dei grandi numeri e metodo Monte CarloSe X₁, X₂, ... sono i.i.d. con media μ, la media campionaria X̄ₙ = (X₁ + ... + Xₙ)/n converge a μ: in probabilità (legge debole, dimostrata con Chebyshev se la varianza è finita: P(|X̄ₙ − μ| > ε) ≤ σ²/(nε²)) e quasi certamente (legge forte). Metodo Monte Carlo: ∫ g = E[g(U)] si stima con la media di g(U₁), ..., g(Uₙ) per uniformi indipendenti.Legge dei grandi numeri e metodo Monte Carlo →). Hoeffding con $t=n\varepsilon$: $P(|\hat p-p|\ge\varepsilon)\le2e^{-2n\varepsilon^2}$. Questo è $\le\delta$ se $$n\ \ge\ \frac{\ln(2/\delta)}{2\varepsilon^2}.$$ Allora $[\hat p-\varepsilon,\ \hat p+\varepsilon]$ contiene $p$ con probabilità almeno $1-\delta$.

Numeri. $\varepsilon=0{,}01$, $\delta=0{,}05$: $n\ge\frac{\ln 40}{2\cdot10^{-4}}=\frac{3{,}689}{0{,}0002}=18444{,}4$, quindi $18445$ campioni. Con Chebyshev ($\mathrm{Var}(\hat p)\le\frac1{4n}$) servirebbe $n\ge\frac1{4\varepsilon^2\delta}=50000$: la dipendenza da $\delta$ è $\ln(1/\delta)$ contro $1/\delta$. Per $p\approx0{,}01$ con errore relativo del $10\%$ (cioè $|\hat p-p|\le0{,}1\,p$), Chernoff con $\mu=np$ dà $P(|X-\mu|\ge\varepsilon\mu)\le2e^{-\varepsilon^2np/3}\le\delta$ con $\varepsilon=0{,}1$, cioè $n\ge\frac{3\ln(2/\delta)}{\varepsilon^2p}=\frac{3\cdot3{,}689}{0{,}01\cdot0{,}01}\approx110700$ campioni; Hoeffding per lo stesso errore assoluto $0{,}001$ ne chiederebbe $1844440$.

Amplificazione di un algoritmo BPP

Un algoritmo randomizzato a errore bilatero ha probabilità di errore $\le\frac13$ (Algoritmi randomizzati - Monte Carlo, Las Vegas e amplificazioneUn algoritmo randomizzato usa bit casuali indipendenti; la probabilità è sulle scelte dell'algoritmo, mai sull'input (garanzia per ogni input). Las Vegas: sempre corretto, tempo aleatorio (conta il tempo atteso). Monte Carlo: tempo fisso, risposta sbagliata con probabilità limitata; errore unilaterale (RP: accetta solo se x sta nel linguaggio, accetta con prob almeno 1/2) o bilaterale (BPP: giusto con prob almeno 2/3). ZPP = RP ∩ co-RP = Las Vegas con tempo atteso polinomiale. Amplificazione: unilaterale, k ripetizioni indipendenti, errore (1-p)^k ≤ e^(-pk), serve k ≥ ln(1/ε)/p; bilaterale, voto di maggioranza su k esecuzioni, errore binomiale esatto, esponenziale in k (Chernoff, e^(-k/18) per p=2/3) mentre Chebyshev dà solo 8/k. Las Vegas -> Monte Carlo: interrompere a c volte il tempo atteso (Markov, errore ≤ 1/c). Monte Carlo -> Las Vegas: solo se la risposta si verifica in fretta. Esempio: Miller-Rabin, errore ≤ 1/4 per esecuzione.Algoritmi randomizzati - Monte Carlo, Las Vegas e amplificazione →). Si ripete $k$ volte con casualità indipendente e si risponde con la maggioranza. Sia $Y$ il numero di esecuzioni sbagliate: la risposta finale è sbagliata solo se $Y\ge k/2$, con $E[Y]\le k/3$.

• Hoeffding: $P(Y-\frac k3\ge\frac k6)\le e^{-2(k/6)^2/k}=e^{-k/18}$.
• Chernoff con $\delta=\frac12$ su $\mu=\frac k3$: $e^{-\delta^2\mu/3}=e^{-k/36}$.

L'errore scende esponenzialmente in $k$: per ottenere $2^{-20}$ bastano $k\ge18\cdot20\ln2=249{,}5$ (Hoeffding) o $k\ge36\cdot20\ln2=499{,}1$ (Chernoff semplice). Il minimo $k$ dispari per cui l'errore esatto (binomiale) è $\le2^{-20}$ è $193$ (errore $9{,}03\times10^{-7}$). I limiti sono prudenti di un fattore costante, ma hanno la forma giusta $k=O(\log(1/\varepsilon))$.

Bilanciamento di insiemi

Teorema. Sia $A$ una matrice $n\times m$ con entrate $0$ o $1$ ($n\ge3$). Esiste $b\in\{-1,+1\}^m$ tale che ogni riga ha $|(Ab)_i|\le\sqrt{4m\ln n}$.

Interpretazione: $m$ elementi e $n$ sottoinsiemi; si colorano gli elementi di rosso e blu in modo che ogni sottoinsieme abbia quasi tanti rossi quanto blu.

Dimostrazione. Si sceglie $b$ a caso, $\pm1$ uniformi indipendenti. La riga $i$ è $\sum_jA_{ij}b_j$, somma di $m$ termini indipendenti con $A_{ij}b_j\in[-1,1]$ (intervallo di ampiezza $2$, o ampiezza $0$ se $A_{ij}=0$), media $0$ e $c\le4m$. Hoeffding con $t=\sqrt{4m\ln n}$: $P(|(Ab)_i|\ge t)\le2e^{-2t^2/(4m)}=2e^{-2\ln n}=2/n^2$. Per l'unione sulle $n$ righe, la probabilità che almeno una superi $t$ è $\le2/n<1$ (per $n\ge3$), quindi esiste $b$ buono. Anzi, un $b$ scelto a caso lo è con probabilità $\ge1-2/n$. $\blacksquare$

Nell'esempio $n=m=100$ il limite è $\sqrt{400\ln100}=42{,}9$; su $2000$ scelte casuali di $b$ per una matrice casuale il massimo di $|Ab|$ tra le righe vale in media $16{,}7$ (al peggio $32$): il limite è valido con ampio margine. Si può fare meglio ($O(\sqrt m)$ per $n=m$, risultato di Spencer), ma serve un'altra dimostrazione.

Differenze limitate (Azuma) in breve

Disuguaglianza di Azuma-Hoeffding. Se $Z_0,\dots,Z_m$ è una martingala con $|Z_i-Z_{i-1}|\le c_i$, allora $P(|Z_m-Z_0|\ge t)\le2\exp\big(-t^2/(2\sum_ic_i^2)\big)$.

La martingala tipica è quella di Doob: $f(X_1,\dots,X_m)$ funzione di variabili indipendenti, $Z_i=E[f\mid X_1,\dots,X_i]$. Se cambiare una sola $X_i$ cambia $f$ di al più $c_i$ (differenze limitate), allora $|Z_i-Z_{i-1}|\le c_i$ e $f$ è concentrata intorno alla media. Con variabili indipendenti la costante migliora (disuguaglianza di McDiarmid, stessa dimostrazione ma con il lemma di Hoeffding): $P(|f-E[f]|\ge t)\le2\exp\big(-2t^2/\sum_ic_i^2\big)$. Conviene scegliere poche variabili, eventualmente raggruppandone molte in una sola: un esempio è in Esercizio - Concentrazione del numero cromatico di un grafo casuale con le differenze limitate (lezioni MIT).

Esempio: urne vuote. $m=1000$ palline in $n=1000$ urne (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 →); $Z$ è il numero di urne vuote. Spostare una pallina cambia $Z$ al più di $1$: $c_i=1$. $E[Z]=n(1-\frac1n)^m=367{,}7$. Per $t=100$: Azuma $2e^{-100^2/2000}=2e^{-5}=0{,}0135$; McDiarmid $2e^{-20000/1000}=4{,}1\times10^{-9}$; Chebyshev con la varianza esatta ($97{,}2$, calcolata con le coppie di urne) $0{,}0097$. Nella simulazione ($20000$ prove) lo scarto massimo è molto sotto $100$ (deviazione standard osservata $9{,}86$): il limite è vero ma non stretto. Il vantaggio è che non serve calcolare la varianza.

Domande d'esame

1. Dimostra che $P(X\ge(1+\delta)\mu)\le\big[e^\delta/(1+\delta)^{1+\delta}\big]^\mu$. Markov su $e^{tX}$, fattorizzazione di $M_X$, $M_{X_i}(t)\le e^{p_i(e^t-1)}$, e minimo in $t=\ln(1+\delta)$ (passaggi sopra).
2. Quante estrazioni per stimare una probabilità a meno di $0{,}02$ con confidenza $99\%$? $n\ge\frac{\ln(2/0{,}01)}{2\cdot0{,}02^2}=\frac{5{,}298}{0{,}0008}=6622{,}9$, quindi $6623$.
3. Perché per $p=\frac12$ Hoeffding batte Chernoff? Chernoff usa solo la media e ottiene un esponente $\delta^2\mu/3$; Hoeffding tiene conto che la varianza è $\frac n4=\frac\mu2$ e ottiene $2t^2/n$: per 1000 monete con $t=100$ l'esponente è $20$, contro $6{,}7$ della forma semplificata di Chernoff.
4. Un algoritmo sbaglia con probabilità $\frac13$. Come si porta l'errore sotto $\varepsilon$? Maggioranza su $k\ge18\ln(1/\varepsilon)$ esecuzioni indipendenti (Hoeffding), quindi $O(\log(1/\varepsilon))$.