Esercizio - Chernoff su una binomiale, code superiore e inferiore

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 → (forme esatte e semplificate); per la binomiale 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 →.

Testo. $X\sim\mathrm{Bin}(100,0{,}2)$ conta i pacchetti persi su $100$ trasmessi indipendenti, $\mu=20$.

1. Limitare $P(X\ge30)$ con Markov, Chebyshev, Chernoff esatto e semplificato.
2. Limitare $P(X\le10)$ con Chebyshev e Chernoff.
3. Limitare $P(|X-20|\ge10)$ con la forma bilatera semplificata.
4. Per $Y\sim\mathrm{Bin}(1000,0{,}01)$ ($\mu=10$) limitare $P(Y\ge60)$ con la regola $R\ge6\mu$.
5. Confrontare tutto con i valori esatti.

Soluzione

1. Coda superiore, $\delta=\frac{30-20}{20}=0{,}5$.

• Markov: $\frac{20}{30}=0{,}667$.
• Chebyshev: $\mathrm{Var}=100\cdot0{,}2\cdot0{,}8=16$, $P(X\ge30)\le P(|X-20|\ge10)\le\frac{16}{100}=0{,}16$.
• Chernoff esatto: $\big[\frac{e^{0{,}5}}{1{,}5^{1{,}5}}\big]^{20}=\big[\frac{1{,}64872}{1{,}83712}\big]^{20}=0{,}89745^{20}=\mathbf{0{,}115}$.
• Chernoff semplificato: $e^{-0{,}5^2\cdot20/3}=e^{-1{,}667}=0{,}189$.

2. Coda inferiore, $\delta=\frac{20-10}{20}=0{,}5$. Chebyshev: $0{,}16$. Chernoff esatto: $\big[\frac{e^{-0{,}5}}{0{,}5^{0{,}5}}\big]^{20}=\big[\frac{0{,}60653}{0{,}70711}\big]^{20}=0{,}85776^{20}=\mathbf{0{,}0465}$. Semplificato: $e^{-0{,}25\cdot20/2}=e^{-2{,}5}=0{,}0821$. La coda inferiore è più leggera della superiore (stessa $\delta$) perché la forma ha $\delta^2\mu/2$ invece di $/3$.

3. Bilatero. $P(|X-20|\ge10)=P(|X-\mu|\ge0{,}5\mu)\le2e^{-0{,}25\cdot20/3}=2\cdot0{,}189=0{,}378$: più debole di Chebyshev ($0{,}16$)! Il fattore $2$ e la forma semplificata costano; con le forme esatte si ha $0{,}115+0{,}0465=0{,}1615$, praticamente come Chebyshev.

4. $R\ge6\mu$. $R=60=6\mu$: $P(Y\ge60)\le2^{-60}=8{,}7\times10^{-19}$. Dal limite intermedio $(e\mu/R)^R=(e/6)^{60}=2{,}3\times10^{-21}$ (più stretto). Markov darebbe solo $\frac{10}{60}=0{,}167$.

5. Valori esatti (somme binomiali): $P(X\ge30)=0{,}01125$, $P(X\le10)=0{,}00570$, $P(|X-20|\ge10)=0{,}01695$, $P(Y\ge60)=1{,}8\times10^{-27}$.

Qui $\mu=20$ è piccolo, quindi Chernoff è prudente (10 volte sopra l'esatto): il limite perde il fattore polinomiale $\approx1/\sqrt{\mu}$ della stima fine. Cresce di utilità con $\mu$ grande o $\delta$ grande.

Risultato. $P(X\ge30)\le0{,}115$, $P(X\le10)\le0{,}0465$, $P(Y\ge60)\le2^{-60}$.

Verifica.

import math

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

mu, d = 20, 0.5
sup = (math.exp(d) / (1 + d)**(1 + d))**mu
inf = (math.exp(-d) / (1 - d)**(1 - d))**mu
print(sup, math.exp(-d * d * mu / 3), inf, math.exp(-d * d * mu / 2))
print(ge(100, .2, 30), le(100, .2, 10), ge(100, .2, 30) + le(100, .2, 10))
print(2.0**-60, (math.e / 6)**60, ge(1000, .01, 60))