Esercizio - amplificazione di un algoritmo BPP con il voto di maggioranza

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 all'amplificazione) e 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 →. Calcolo esatto per $k=3,5$ e confronto con Chebyshev (errore iniziale $\frac14$, obiettivo $10^{-3}$, $33$ copie): Esercizio - Voto di maggioranza per un algoritmo a errore bilaterale.

Testo. Un algoritmo randomizzato risponde sì/no e sbaglia con probabilità al più $\frac13$ su ogni input, con casualità indipendente a ogni esecuzione. Si ripete $k$ volte ($k$ dispari) e si risponde con la maggioranza.

1. Dimostrare con Hoeffding e con Chernoff che l'errore finale è $\le e^{-k/18}$ e $\le e^{-k/36}$.
2. Quante ripetizioni garantiscono errore $\le2^{-20}$ con i due limiti? Qual è il minimo vero?
3. Rifare con errore iniziale $\frac14$.
4. Confrontare i limiti con il valore esatto per $k=101$.

Soluzione

1. Limiti. Sia $Y$ il numero di esecuzioni sbagliate: somma di $k$ indicatori indipendenti con probabilità $\le\frac13$, quindi $E[Y]\le\frac k3$. La maggioranza è sbagliata se e solo se $Y\ge\frac k2$ (con $k$ dispari non ci sono pareggi); questo è uno scostamento di almeno $\frac k2-\frac k3=\frac k6$ dalla media.

• Hoeffding ($c=k$, $t=\frac k6$): $P\le e^{-2(k/6)^2/k}=e^{-k/18}$.
• Chernoff con $\mu=\frac k3$ e $(1+\delta)\mu=\frac k2$, cioè $\delta=\frac12$: $P\le e^{-\delta^2\mu/3}=e^{-k/36}$.

(Se la probabilità di errore è minore di $\frac13$ i limiti valgono ancora: l'errore finale può solo diminuire.)

2. Per $2^{-20}$. Hoeffding: $e^{-k/18}\le2^{-20}\iff k\ge18\cdot20\ln2=249{,}5$, quindi $k=251$ (dispari). Chernoff: $k\ge36\cdot20\ln2=499{,}1$, quindi $k=501$. Minimo vero (somma della binomiale $\mathrm{Bin}(k,\frac13)$, $P(Y\ge\frac{k+1}2)$): $k=193$ con errore $9{,}03\times10^{-7}\le9{,}54\times10^{-7}$; $k=191$ dà $1{,}02\times10^{-6}$, troppo. I limiti sono prudenti di un fattore $1{,}3$ (Hoeffding) e $2{,}6$ (Chernoff) sulle ripetizioni, ma hanno la forma giusta: $k=O(\log\frac1\varepsilon)$.

3. Errore iniziale $\frac14$. Ora $E[Y]\le\frac k4$ e lo scostamento fino a $\frac k2$ è $\frac k4$: Hoeffding $e^{-2(k/4)^2/k}=e^{-k/8}$; per $2^{-20}$ servono $k\ge8\cdot20\ln2=110{,}9$, cioè $k=111$. Il minimo vero è $k=79$.

4. $k=101$, errore iniziale $\frac13$.

Il costo dell'amplificazione è lineare in $k$, quindi migliorare l'errore da $\frac13$ a $2^{-20}$ costa circa $200$ volte il tempo, non $2^{20}$ volte.

Risultato. $k=251$ (Hoeffding), $501$ (Chernoff), $193$ (minimo vero) per errore $\le2^{-20}$ partendo da $\frac13$; $111$ e $79$ partendo da $\frac14$.

Verifica.

import math

def errore(k, p):                       # P(piu' della meta' delle k esecuzioni sbagliate)
    return sum(math.comb(k, i) * p**i * (1 - p)**(k - i) for i in range((k + 1) // 2, k + 1))

for p, k0 in ((1 / 3, 1), (1 / 4, 1)):
    k = k0
    while errore(k, p) > 2.0**-20: k += 2
    print(p, k, errore(k, p))                              # 1/3: 193 ; 1/4: 79
print(18 * 20 * math.log(2), 36 * 20 * math.log(2), 8 * 20 * math.log(2))
print(math.exp(-101 / 18), math.exp(-101 / 36), errore(101, 1 / 3))