Esercizio - quanti campioni per stimare una probabilità con una data confidenza

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 → (applicazione alla stima); metodo in 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 →.

Testo. Si vuole stimare la probabilità $p$ che un programma randomizzato produca un risultato sbagliato, eseguendolo $n$ volte in modo indipendente e prendendo la frazione $\hat p$ di errori.

1. Quante esecuzioni garantiscono $P(|\hat p-p|\ge0{,}01)\le0{,}05$? Confrontare con Chebyshev.
2. Con $n=2000$ esecuzioni: quale errore $\varepsilon$ si garantisce con confidenza $95\%$, e quale confidenza con $\varepsilon=0{,}03$?
3. Si sa che $p\approx0{,}01$ e si vuole un errore relativo del $10\%$, con probabilità di sbagliare $\le0{,}05$. Quante esecuzioni con Chernoff? E con Hoeffding?
4. Su $18445$ esecuzioni si osservano $5432$ errori: dare l'intervallo di confidenza.

Soluzione

1. Hoeffding. $\hat p=\frac1n\sum X_i$ con $X_i\in[0,1]$ indipendenti: $P(|\hat p-p|\ge\varepsilon)=P(|S-E[S]|\ge n\varepsilon)\le2e^{-2(n\varepsilon)^2/n}=2e^{-2n\varepsilon^2}$. Si impone $\le\delta=0{,}05$: $$n\ge\frac{\ln(2/\delta)}{2\varepsilon^2}=\frac{\ln40}{2\cdot10^{-4}}=\frac{3{,}6889}{0{,}0002}=18444{,}4\ \Rightarrow\ n=\mathbf{18445}.$$ Chebyshev: $\mathrm{Var}(\hat p)=\frac{p(1-p)}{n}\le\frac1{4n}$, quindi $P(|\hat p-p|\ge\varepsilon)\le\frac{1}{4n\varepsilon^2}\le\delta$ se $n\ge\frac1{4\varepsilon^2\delta}=\frac{1}{4\cdot10^{-4}\cdot0{,}05}=50000$. Hoeffding richiede $2{,}7$ volte meno esecuzioni, e la differenza cresce al diminuire di $\delta$: $\ln(1/\delta)$ contro $1/\delta$ (per $\delta=10^{-6}$ si hanno $72\,543$ esecuzioni contro $2{,}5\times10^{9}$).

2. $n=2000$. Errore garantito: $2e^{-2n\varepsilon^2}=0{,}05\Rightarrow\varepsilon=\sqrt{\frac{\ln40}{2n}}=\sqrt{\frac{3{,}6889}{4000}}=\mathbf{0{,}0304}$. Confidenza con $\varepsilon=0{,}03$: $\delta=2e^{-2\cdot2000\cdot0{,}0009}=2e^{-3{,}6}=0{,}0546$, cioè confidenza $94{,}5\%$.

3. Errore relativo. $\mu=np$, errore $\varepsilon=0{,}1$ su $\mu$: Chernoff bilatero semplificato $P(|X-\mu|\ge\varepsilon\mu)\le2e^{-\varepsilon^2np/3}\le0{,}05$ dà $$n\ge\frac{3\ln(2/\delta)}{\varepsilon^2p}=\frac{3\cdot3{,}689}{0{,}01\cdot0{,}01}=110\,666\ \Rightarrow\ n=110\,667.$$ Hoeffding garantisce un errore assoluto; l'errore relativo del $10\%$ su $p=0{,}01$ è $0{,}001$ assoluto: $n\ge\frac{3{,}689}{2\cdot10^{-6}}=1\,844\,440$, $16{,}7$ volte di più. Per $p$ piccolo Chernoff (che usa la media) è molto più efficiente, perché la varianza $p(1-p)$ è molto minore di $\frac14$.

4. Intervallo. $\hat p=\frac{5432}{18445}=0{,}2945$; con $\varepsilon=0{,}01$ e confidenza $95\%$: $p\in[0{,}2845,\,0{,}3045]$.

Controllo per simulazione. Con $p=0{,}3$ ed $n=18445$, su $3000$ ripetizioni $|\hat p-p|>0{,}01$ accade nello $0{,}4\%$ dei casi (approssimazione normale: $0{,}3\%$), molto sotto il $5\%$ garantito: Hoeffding è prudente.

Risultato. $n=18445$ (Hoeffding) contro $50000$ (Chebyshev); $\varepsilon=0{,}0304$ con $n=2000$; $n=110667$ per l'errore relativo con Chernoff, $1\,844\,440$ con Hoeffding.

Verifica.

import math
import numpy as np

eps, dl = 0.01, 0.05
n = math.ceil(math.log(2 / dl) / (2 * eps**2))
print(n, 1 / (4 * eps**2 * dl))                        # 18445 50000
print(math.sqrt(math.log(40) / 4000), 2 * math.exp(-2 * 2000 * 0.03**2))
print(3 * math.log(2 / dl) / (0.1**2 * 0.01), math.log(2 / dl) / (2 * 0.001**2))
rng = np.random.default_rng(5)
ph = rng.binomial(n, 0.3, size=3000) / n
print(np.mean(np.abs(ph - 0.3) > eps), 5432 / n)       # ~0.004 0.2945