Esercizio - Ripetizioni di un Monte Carlo a errore unilaterale per un errore prefissato

Testo. Un algoritmo randomizzato per un problema di decisione non sbaglia mai quando risponde SI, e quando la risposta giusta è SI risponde SI con probabilità $p=0{,}3$ (errore unilaterale). Le esecuzioni usano bit casuali indipendenti e ciascuna costa $n^2$ operazioni.

1. Qual è la probabilità di errore ripetendo l'algoritmo $k=10$ volte e rispondendo SI se almeno una esecuzione dice SI?
2. Quante ripetizioni servono per un errore $\le10^{-6}$? Calcolare il valore esatto e quello che dà la formula $k\ge\ln(1/\varepsilon)/p$.
3. Se invece fosse $p=1/2$, quante ripetizioni per un errore $\le2^{-20}$?
4. Qual è il costo totale in operazioni per $n=1000$ nel caso 2?

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 → (sezione sull'amplificazione).

Soluzione

Punto 1. Se la risposta giusta è NO l'algoritmo non dice mai SI: errore $0$. Se è SI, l'algoritmo risponde NO solo se tutte le $10$ esecuzioni indipendenti sbagliano: ognuna con probabilità $1-p=0{,}7$. Quindi $$\Pr[\text{errore}]=0{,}7^{10}=0{,}02825 .$$

Punto 2. Serve $0{,}7^k\le10^{-6}$, cioè $k\ln0{,}7\le\ln10^{-6}$, ovvero (dividendo per $\ln0{,}7<0$ si inverte il verso) $$k\ge\frac{\ln10^{-6}}{\ln0{,}7}=\frac{-13{,}8155}{-0{,}35667}=38{,}73 .$$ Risultato: $k=39$ ripetizioni. Controllo: $0{,}7^{39}=9{,}1\cdot10^{-7}\le10^{-6}$ e $0{,}7^{38}=1{,}3\cdot10^{-6}>10^{-6}$. La formula semplificata, che usa $1-p\le e^{-p}$ e quindi $(1-p)^k\le e^{-pk}$, dà $k\ge\ln(10^6)/0{,}3=46{,}05$, cioè $47$ ripetizioni: valida ma più larga di $8$.

Punto 3. $(1/2)^k\le2^{-20}$ dà esattamente $k=20$; la formula con $e$ darebbe $\lceil20\ln2/0{,}5\rceil=\lceil27{,}7\rceil=28$.

Punto 4. Con $k=39$ esecuzioni da $n^2=10^6$ operazioni: $39\cdot10^6=3{,}9\cdot10^7$ operazioni, cioè il costo cresce di un fattore $39$ (lineare in $k$) mentre l'errore scende da $0{,}7$ a $10^{-6}$ (esponenziale in $k$).

import math, random
p, eps = 0.3, 1e-6
print(0.7**10, math.ceil(math.log(eps)/math.log(1-p)), math.ceil(math.log(1/eps)/p), 0.7**39, 0.7**38)
N = 10**6                                              # simulazione dell'errore con k = 10
err = sum(all(random.random() >= p for _ in range(10)) for _ in range(N)) / N
print(err)                                             # circa 0.0282

Risultati verificati: $0{,}02825$; $38{,}73$ e $46{,}05$; simulazione $\approx0{,}0282$.