Esercizio - Da Las Vegas a Monte Carlo con Markov e da Monte Carlo a Las Vegas

Testo. Un array di $n$ celle contiene esattamente $n/2$ uni. L'algoritmo Las Vegas «estrai un indice a caso finché la cella vale $1$» ha $T$ = numero di estrazioni.

1. Calcolare $E[T]$ e $\Pr[T>10]$.
2. Si trasforma l'algoritmo in un Monte Carlo che si ferma dopo $c\cdot E[T]$ estrazioni. Quale errore garantisce Markov per $c=5$? E quale è l'errore vero?
3. Si eseguono $k$ blocchi indipendenti da $c\,E[T]$ estrazioni e si tiene la prima risposta trovata. Quante estrazioni in totale servono per un errore garantito $\le10^{-6}$ con $c=2$ e con $c=5$? Quante ne servirebbero conoscendo la distribuzione vera?
4. Un Monte Carlo risponde con un indice sbagliato con probabilità $1/4$, e la risposta si verifica in una lettura. Quanti tentativi servono in media per ottenere una risposta certa?

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 sulle conversioni); Distribuzione geometricaGeo(p) è il numero della prova in cui arriva il primo successo in prove indipendenti: P(X = n) = (1−p)^(n−1) p per n ≥ 1, P(X > n) = (1−p)^n (lunga attesa), media 1/p, varianza (1−p)/p², ed è senza memoria.Distribuzione geometrica →, 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 →.

Soluzione

Punto 1. Ogni estrazione riesce con probabilità $p=1/2$, indipendente dalle altre: $T$ è geometrica di parametro $1/2$. Quindi $E[T]=1/p=2$ e $\Pr[T>10]=(1-p)^{10}=2^{-10}=0{,}000977$ (le prime $10$ estrazioni falliscono).

Punto 2. Con $c=5$: si ferma a $c\,E[T]=10$ estrazioni. Per Markov $$\Pr[T\ge10]\le\frac{E[T]}{10}=\frac15=0{,}2 .$$ L'algoritmo troncato sbaglia solo se nessuna delle $10$ estrazioni trova un $1$, cioè se $T>10$; poiché $\{T>10\}\subseteq\{T\ge10\}$, anche l'errore è $\le0{,}2$. L'errore vero è $\Pr[T>10]=2^{-10}=0{,}000977$ (punto 1), e perfino $\Pr[T\ge10]=2^{-9}=0{,}00195$ è cento volte sotto il limite: Markov usa solo la media e perde molto.

Punto 3. Un blocco da $c\,E[T]$ estrazioni fallisce con probabilità $\le1/c$ (Markov); $k$ blocchi indipendenti falliscono tutti con probabilità $\le c^{-k}$.

• $c=2$: blocchi da $4$ estrazioni, errore per blocco $\le1/2$. Serve $2^{-k}\le10^{-6}$, $k=20$ ($2^{-20}=9{,}5\cdot10^{-7}$): $80$ estrazioni.
• $c=5$: blocchi da $10$, errore $\le0{,}2$. Serve $0{,}2^k\le10^{-6}$: $k=9$ ($0{,}2^9=5{,}1\cdot10^{-7}$; $0{,}2^8=2{,}6\cdot10^{-6}$ non basta): $90$ estrazioni.
• Con la distribuzione vera: $(1/2)^m\le10^{-6}$ dà $m=20$ estrazioni ($2^{-20}$), cioè $20$. Markov costa 4-4,5 volte tanto, ma non richiede di conoscere la distribuzione di $T$.

Punto 4. Un tentativo riesce (risposta giusta, verificata) con probabilità $3/4$. I tentativi sono indipendenti, quindi il loro numero è geometrico di parametro $3/4$ e in media $\frac1{3/4}=\frac43=1{,}33$. Si ottiene così un Las Vegas: risposta sempre giusta, ma tempo aleatorio. Se non esistesse il verificatore (per esempio un errore bilaterale su un problema di decisione) la conversione non sarebbe possibile in generale.

Risultati: $E[T]=2$, $\Pr[T>10]=2^{-10}$; Markov $0{,}2$ contro errore vero $2^{-10}=0{,}000977$; $80$ o $90$ estrazioni contro $20$; $4/3$ tentativi.

import random
N = 10**6
def T():
    t = 1
    while random.random() >= 0.5: t += 1
    return t
s = [T() for _ in range(N)]
print(sum(s) / N, sum(t > 10 for t in s) / N, sum(t >= 10 for t in s) / N)   # 2.0  0.00098  0.00195
print(0.2**8, 0.2**9, 2.0**-20)                                              # 2.6e-06  5.1e-07  9.5e-07