Salta al contenuto
Note per Studenti Esercizio - Moneta a due teste e regola di Bayes per le risposte di un test randomizzato (lezioni MIT)

Esercizio - Moneta a due teste e regola di Bayes per le risposte di un test randomizzato (lezioni MIT)

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 → (errore unilaterale, Miller-Rabin); base in Formula delle probabilità totali e formula di BayesSe (A_i) è una partizione di Ω, P(B) = Σ P(B ∣ A_i) P(A_i) (probabilità totali); la formula di Bayes inverte il condizionamento: P(A_k ∣ B) = P(B ∣ A_k) P(A_k) / P(B).Formula delle probabilità totali e formula di Bayes →. Esempi dalle videolezioni di Mathematics for Computer Science, MIT OpenCourseWare (probabilità condizionata e indipendenza).

Testo.

  1. Da un sacchetto con una moneta equa (FF) e una con due teste si estrae una moneta a caso e la si lancia: esce testa (HH). Calcolare P(F∣H)P(F\mid H) con la forma a rapporto della regola di Bayes.
  2. Si lancia la stessa moneta 1010 volte ed escono 1010 teste (H10H^{10}). Calcolare P(F∣H10)P(F\mid H^{10}) e la probabilità che l'undicesimo lancio sia testa.
  3. Il test di Miller-Rabin, su un numero composto, risponde PROBABILMENTE PRIMO con probabilità ≤14\le\frac14 per ogni base; su un primo lo risponde sempre. Si sceglie a caso un dispari di 512512 bit (circa uno su 177177 è primo) e il test risponde PROBABILMENTE PRIMO per kk basi indipendenti. Dare un limite superiore a P(composto∣k risposte)P(\text{composto}\mid k\text{ risposte}) per k=1,5,10k=1,5,10.
  4. Quante basi servono perché questa probabilità sia ≤10−6\le10^{-6}? Perché non basta dire «l'errore è 4−k4^{-k}»?

Soluzione

1. Una testa. La forma a rapporto della regola di Bayes divide le due formule di Bayes e cancella P(H)P(H): P(F∣H)P(F‾∣H)=P(H∣F) P(F)P(H∣F‾) P(F‾)=12⋅121⋅12=12.\frac{P(F\mid H)}{P(\overline F\mid H)}=\frac{P(H\mid F)\,P(F)}{P(H\mid\overline F)\,P(\overline F)}=\frac{\frac12\cdot\frac12}{1\cdot\frac12}=\frac12 . Le due probabilità a posteriori sommano a 11 e stanno nel rapporto 1:21:2, quindi P(F∣H)=13P(F\mid H)=\frac13 e P(F‾∣H)=23P(\overline F\mid H)=\frac23. La testa è più probabile con la moneta truccata, quindi la sposta verso quella.

2. Dieci teste. I lanci, data la moneta, sono indipendenti: P(H10∣F)=2−10P(H^{10}\mid F)=2^{-10} e P(H10∣F‾)=1P(H^{10}\mid\overline F)=1. Il rapporto diventa P(F∣H10)P(F‾∣H10)=2−10⋅121⋅12=11024  ⟹  P(F∣H10)=11025.\frac{P(F\mid H^{10})}{P(\overline F\mid H^{10})}=\frac{2^{-10}\cdot\frac12}{1\cdot\frac12}=\frac1{1024}\;\Longrightarrow\;P(F\mid H^{10})=\frac1{1025}. Per l'undicesimo lancio si usa la probabilità totale condizionata a H10H^{10}, separando le due monete: P(H11∣H10)=1⋅10241025+12⋅11025=20492050≈0,9995.P(H_{11}\mid H^{10})=1\cdot\frac{1024}{1025}+\frac12\cdot\frac1{1025}=\frac{2049}{2050}\approx0{,}9995 . Non è una contraddizione con «la moneta non ha memoria»: con la moneta equa nota il lancio successivo vale 12\frac12, ma qui la moneta non è nota e le 1010 teste sono un'informazione su quale moneta si sta usando.

3. Lo stesso schema per Miller-Rabin. Il ruolo della moneta a due teste lo gioca il numero primo (risponde sempre PROBABILMENTE PRIMO), quello della moneta equa il composto (risponde PROBABILMENTE PRIMO con probabilità ≤14\le\frac14 per base). La probabilità a priori di un primo è circa 2512ln⁡2=1177\frac2{512\ln2}=\frac1{177} (teorema dei numeri primi, ristretto ai dispari), quindi il rapporto a priori composto/primo è 176176. Con kk risposte indipendenti, P(risposte∣composto)≤4−kP(\text{risposte}\mid\text{composto})\le4^{-k} e P(composto∣risposte)P(primo∣risposte)≤4−k⋅1761⋅1  ⟹  P(composto∣risposte)≤176⋅4−k176⋅4−k+1.\frac{P(\text{composto}\mid\text{risposte})}{P(\text{primo}\mid\text{risposte})}\le\frac{4^{-k}\cdot176}{1\cdot1}\;\Longrightarrow\;P(\text{composto}\mid\text{risposte})\le\frac{176\cdot4^{-k}}{176\cdot4^{-k}+1}.

  • k=1k=1: 4445=0,978\frac{44}{45}=0{,}978: una sola risposta non dice quasi nulla, perché i composti sono molti di più dei primi.
  • k=5k=5: 176/1024176/1024+1=0,147\frac{176/1024}{176/1024+1}=0{,}147.
  • k=10k=10: 176⋅4−10176⋅4−10+1=1,68⋅10−4\frac{176\cdot4^{-10}}{176\cdot4^{-10}+1}=1{,}68\cdot10^{-4}.

4. Basi per 10−610^{-6}. Serve 176⋅4−k176⋅4−k+1≤10−6\frac{176\cdot4^{-k}}{176\cdot4^{-k}+1}\le10^{-6}, cioè circa 4k≥1,76⋅1084^k\ge1{,}76\cdot10^8: k≥log⁡4(1,76⋅108)=13,7k\ge\log_4(1{,}76\cdot10^8)=13{,}7, quindi k=14k=14 (6,6⋅10−76{,}6\cdot10^{-7}). Il valore 4−k4^{-k} della nota è P(risposte∣composto)P(\text{risposte}\mid\text{composto}), cioè la probabilità che un composto fissato passi kk basi: è la garanzia per ogni input. La domanda «quanto è probabile che il numero restituito sia composto» è invece P(composto∣risposte)P(\text{composto}\mid\text{risposte}), e dipende dal rapporto a priori: con k=10k=10 vale 1,7⋅10−41{,}7\cdot10^{-4}, 176176 volte più di 4−10=9,5⋅10−74^{-10}=9{,}5\cdot10^{-7}. È lo stesso errore dei test medici delle lezioni: un test accurato, applicato dove la condizione è rara, dà molti falsi positivi. In pratica il limite è pessimistico (i bugiardi sono di solito molto meno di un quarto, vedi Esercizio - Test di Miller-Rabin su 221 e 561 e confronto con il test di Fermat), ma il ragionamento corretto passa per Bayes.

Risultato. P(F∣H)=13P(F\mid H)=\frac13; P(F∣H10)=11025P(F\mid H^{10})=\frac1{1025}, P(H11∣H10)=20492050P(H_{11}\mid H^{10})=\frac{2049}{2050}. Miller-Rabin su un dispari casuale di 512512 bit: P(composto∣k risposte)≤0,978, 0,147, 1,68⋅10−4P(\text{composto}\mid k\text{ risposte})\le0{,}978,\ 0{,}147,\ 1{,}68\cdot10^{-4} per k=1,5,10k=1,5,10; servono 1414 basi per 10−610^{-6}.

python
from fractions import Fraction as F
import math, random
post = lambda k: F(1, 2) * F(1, 2**k) / (F(1, 2) * F(1, 2**k) + F(1, 2))      # P(equa | k teste)
print(post(1), post(10), 1 - post(10) + F(1, 2) * post(10))                     # 1/3  1/1025  2049/2050
pc = lambda k: 176 * F(1, 4**k) / (176 * F(1, 4**k) + 1)                        # P(composto | k risposte), limite
print([float(pc(k)) for k in (1, 5, 10, 14)], math.log(1.76e8, 4))              # 0.978 0.147 1.68e-4 6.6e-7; 13.7
c = h = 0
for _ in range(400000):                                                          # simulazione della moneta
    equa = random.random() < 0.5
    l = [random.random() < 0.5 if equa else True for _ in range(11)]
    if all(l[:10]): h += 1; c += l[10]
print(c / h)                                                                     # circa 0.9995

Verificato con frazioni esatte e con la simulazione (0,999590{,}99959); 2512ln⁡2=1177,4\frac2{512\ln2}=\frac1{177{,}4}.

Versione ripasso

Teoria collegata