Esercizio - Voto di maggioranza per un algoritmo a errore bilaterale

Testo. Un algoritmo randomizzato risponde correttamente con probabilità $p=3/4$ per ogni input (errore bilaterale: sbaglia sia i SI sia i NO). Si eseguono $k$ copie indipendenti ($k$ dispari) e si risponde come la maggioranza.

1. Calcolare esattamente la probabilità di errore per $k=3$ e $k=5$.
2. Trovare il minimo $k$ dispari con errore $\le10^{-3}$ (valore esatto) e confrontarlo con quelli garantiti dalla disuguaglianza di Chebyshev e da quella di Hoeffding $e^{-2k(p-1/2)^2}$.
3. Perché non basta ripetere e rispondere SI se almeno una copia dice SI?

Teoria: 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 → (amplificazione, voto di maggioranza); 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 →.

Soluzione

Il numero $X$ di copie giuste è $\text{Bin}(k,3/4)$ e la maggioranza sbaglia se $X\le(k-1)/2$.

Punto 1.

• $k=3$: sbaglia se $X\le1$: $\binom30(1/4)^3+\binom31(3/4)(1/4)^2=\frac1{64}+\frac9{64}=\frac{10}{64}=\frac5{32}=0{,}15625$.
• $k=5$: sbaglia se $X\le2$: $\binom50(1/4)^5+\binom51(3/4)(1/4)^4+\binom52(3/4)^2(1/4)^3=\frac{1+15+90}{1024}=\frac{106}{1024}=0{,}1035$.

Risultato: $0{,}15625$ per $k=3$ e $0{,}1035$ per $k=5$.

Punto 2. Si calcola la somma binomiale per $k$ dispari crescenti: $k=31$ dà $0{,}001302$ (troppo), $k=33$ dà $0{,}000951\le10^{-3}$. Quindi $k=33$ è il minimo esatto.

• Chebyshev (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 →): $E[X]=3k/4$, $\text{Var}[X]=3k/16$; per avere $X\le k/2$ servono $k/4$ di scarto, quindi $\Pr\le\frac{3k/16}{(k/4)^2}=\frac3k$. Per $3/k\le10^{-3}$ serve $k\ge3000$.
• Hoeffding (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^{-2k/16}=e^{-k/8}\le10^{-3}$ dà $k\ge8\ln1000=55{,}3$, quindi $k=57$ (il primo dispari $\ge55{,}3$).

Risultato: esatto $33$, Hoeffding $57$, Chebyshev $3000$. Chebyshev dà solo decadimento $1/k$, Hoeffding esponenziale; entrambi sono pessimistici rispetto al valore esatto.

Punto 3. Perché con errore bilaterale anche un NO corretto può essere dichiarato SI: una sola copia sbagliata su $k$ farebbe rispondere SI a un'istanza NO. Se la risposta giusta è NO, ogni copia dice SI (sbagliando) con probabilità $1/4$, e almeno una la dice con probabilità $1-(3/4)^k$, che tende a $1$ al crescere di $k$: si sbaglierebbe quasi sempre. L'asimmetria «un SI è certo» vale solo per l'errore unilaterale.

from math import comb, exp, log
p = 0.75
err = lambda k: sum(comb(k, j) * p**j * (1 - p)**(k - j) for j in range((k + 1) // 2))
print(err(3), err(5))
k = 1
while err(k) > 1e-3: k += 2
print(k, err(k), err(k - 2))                    # 33  0.00095  0.0013
print(8 * log(1000), 3 / 1e-3)                  # 55.3  3000

Risultati verificati con Python: $0{,}15625$, $0{,}1035$, $k=33$.

Seguito: Esercizio - amplificazione di un algoritmo BPP con il voto di maggioranza ricava i limiti $e^{-k/18}$ (Hoeffding) ed $e^{-k/36}$ (Chernoff) per errore iniziale $1/3$ e, con lo stesso errore iniziale $1/4$ di qui (stesso limite $e^{-k/8}$), trova che per scendere a $2^{-20}$ servono $79$ copie esatte contro le $33$ che bastano per $10^{-3}$.