Esercizio - mille lanci di moneta, cinque limiti per la coda

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 → e Momenti e deviazioni - Markov, Chebyshev e mediana randomizzataVar(Σ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 →.

Testo. Si lancia $1000$ volte una moneta equa; $X$ è il numero di teste ($\mu=500$, $\mathrm{Var}(X)=250$).

1. Limitare $P(X\ge550)$ e $P(X\ge600)$ con Markov, Chebyshev, Chernoff (forma esatta e semplificata) e Hoeffding.
2. Calcolare i valori esatti e confrontare.
3. Qual è il più piccolo $t$ per cui Hoeffding garantisce $P(X\ge500+t)\le10^{-6}$? Quanto vale la soglia vera?

Soluzione

Markov ($X\ge0$): $P(X\ge550)\le\frac{500}{550}=0{,}909$; $P(X\ge600)\le\frac{500}{600}=0{,}833$.

Chebyshev. $P(|X-500|\ge a)\le\frac{250}{a^2}$. Per $a=50$: $0{,}100$; per $a=100$: $0{,}025$. La distribuzione è simmetrica attorno a $500$, quindi la coda destra è la metà: $0{,}05$ e $0{,}0125$.

Chernoff. Qui $\delta=\frac{50}{500}=0{,}1$ e $\delta=\frac{100}{500}=0{,}2$.

• Forma esatta $\big[e^\delta/(1+\delta)^{1+\delta}\big]^\mu$: per $\delta=0{,}1$: $e^{0{,}1}=1{,}10517$, $1{,}1^{1{,}1}=1{,}11053$, rapporto $0{,}99517$, alla $500$: $0{,}0889$. Per $\delta=0{,}2$: $\frac{e^{0{,}2}}{1{,}2^{1{,}2}}=\frac{1{,}22140}{1{,}24457}=0{,}98138$, alla $500$: $8{,}3\times10^{-5}$.
• Forma semplificata $e^{-\delta^2\mu/3}$: $e^{-0{,}1^2\cdot500/3}=e^{-1{,}667}=0{,}189$; $e^{-0{,}2^2\cdot500/3}=e^{-6{,}667}=1{,}27\times10^{-3}$.

Hoeffding (ogni lancio in $[0,1]$, $c=\sum(b_i-a_i)^2=1000$): $e^{-2t^2/1000}$. Per $t=50$: $e^{-5}=6{,}7\times10^{-3}$; per $t=100$: $e^{-20}=2{,}06\times10^{-9}$.

Valori esatti (somma della binomiale $\mathrm{Bin}(1000,\frac12)$): $P(X\ge550)=8{,}65\times10^{-4}$ e $P(X\ge600)=1{,}36\times10^{-10}$.

Osservazioni: per $\delta$ piccolo (550) Chernoff è addirittura peggiore di Chebyshev; Hoeffding è sempre il migliore perché per $p=\frac12$ sfrutta che la varianza vale metà della media. Per deviazioni grandi (600) gli esponenziali superano di molto Chebyshev. Tutti sono limiti validi, nessuno è stretto: l'esatto è sempre più piccolo.

3. Soglia. $e^{-2t^2/1000}\le10^{-6}\iff t\ge\sqrt{\frac{1000\ln10^6}{2}}=\sqrt{6907{,}8}=83{,}1$, quindi $t=84$: con $X\ge584$ Hoeffding garantisce probabilità $\le10^{-6}$. Il valore vero è più basso: $P(X\ge x)\le10^{-6}$ già da $x=576$.

Risultato. Tabella sopra; per $t=100$ i limiti vanno da $0{,}833$ (Markov) a $2{,}06\times10^{-9}$ (Hoeffding), contro l'esatto $1{,}36\times10^{-10}$.

Verifica.

import math

def coda(n, p, k): return sum(math.comb(n, i) * p**i * (1 - p)**(n - i) for i in range(k, n + 1))

mu, var = 500, 250
for a, t in ((550, 50), (600, 100)):
    d = t / mu
    print(a, mu / a, var / t**2 / 2, (math.exp(d) / (1 + d)**(1 + d))**mu, math.exp(-d * d * mu / 3),
          math.exp(-2 * t * t / 1000), coda(1000, .5, a))
print(math.sqrt(1000 * math.log(1e6) / 2), min(x for x in range(500, 700) if coda(1000, .5, x) <= 1e-6))