Esercizio - Due scatole di caramelle e soglia casuale contro ogni input (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 → (garanzia per ogni input, probabilità sui bit casuali); 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 →. Problema dalle videolezioni di Mathematics for Computer Science, MIT OpenCourseWare.

Testo. Due scatole contengono due numeri diversi di caramelle, interi tra $0$ e $10$, scelti da un avversario che conosce la strategia ma non i bit casuali. Si apre una scatola presa a caso (probabilità $\frac12$ ciascuna), si conta e si decide se tenerla o prendere l'altra. Si vince se si finisce con la scatola più piena.

1. Con la regola fissa «tieni se ci sono almeno $5$ caramelle», qual è la probabilità di vincere sugli input $(3,8)$ e $(6,9)$? Qual è il caso pessimo?
2. Dimostrare che ogni regola deterministica «tieni se il numero aperto sta nell'insieme $K$» ha caso pessimo $\frac12$.
3. Algoritmo randomizzato: si sceglie una soglia $T$ uniforme in $\{1,\dots,10\}$ e si tiene la scatola se contiene almeno $T$ caramelle. Calcolare la probabilità di vincere sull'input con contenuti $s<l$ e il suo minimo su tutti gli input.
4. Eseguire l'algoritmo a mano sull'input $(4,5)$ per tutte le soglie.
5. Con contenuti tra $0$ e $N$, quale garanzia si ottiene? E qual è la media su tutte le $55$ coppie di valori tra $0$ e $10$?

Soluzione

1. Soglia fissa $5$. Con $(3,8)$: se si apre $8$ lo si tiene, se si apre $3$ si cambia e si prende $8$: si vince sempre, probabilità $1$. Con $(6,9)$ entrambi i valori sono $\ge5$: si tiene sempre la prima scatola aperta e si vince solo se è quella da $9$, probabilità $\frac12$. Il caso pessimo è $\frac12$: l'avversario mette entrambi i valori dallo stesso lato della soglia.

2. Nessuna regola deterministica fa meglio di $\frac12$. Una regola deterministica divide gli $11$ valori $0,\dots,10$ in «tengo» ($K$) e «cambio» (il resto). Una delle due classi contiene almeno $6$ valori, quindi almeno due valori distinti $s<l$ con la stessa decisione. Sull'input $(s,l)$:

• se entrambi stanno in $K$ si tiene sempre la prima scatola, che è quella giusta con probabilità $\frac12$;
• se entrambi sono fuori da $K$ si cambia sempre, e si vince solo se si era aperta la scatola sbagliata: ancora $\frac12$.

L'unica casualità di questa strategia è la scelta della scatola, e l'avversario, che conosce $K$, sceglie proprio $(s,l)$.

3. Soglia casuale. Si fissa l'input $s<l$ e si condiziona sul valore di $T$ (probabilità totale). Le soglie si dividono in tre gruppi.

• $s<T\le l$ (la soglia separa i due valori): se si apre $l$ si tiene ($l\ge T$), se si apre $s$ si cambia ($s<T$); si vince sempre. Queste soglie sono $T=s+1,\dots,l$, cioè $k=l-s\ge1$.
• $T\le s$: entrambi i valori sono $\ge T$, si tiene sempre: si vince con probabilità $\frac12$.
• $T>l$: entrambi $<T$, si cambia sempre: probabilità $\frac12$.

Quindi $$P(\text{vittoria})=1\cdot\frac k{10}+\frac12\cdot\frac{10-k}{10}=\frac12+\frac k{20}\ \ge\ \frac12+\frac1{20}=\frac{11}{20}=0{,}55 .$$ Il minimo $0{,}55$ si ha per $k=1$ (valori consecutivi), il massimo $1$ per $(0,10)$ ($k=10$). La garanzia vale per ogni input, perché la probabilità è calcolata sui bit casuali dell'algoritmo ($T$ e la scatola) con l'input fissato: è lo stesso modello degli algoritmi randomizzati, dove non si assume nessuna distribuzione sugli input.

4. A mano, input $(4,5)$. La sola soglia che separa è $T=5$.

Media: $\frac{4\cdot\frac12+1+5\cdot\frac12}{10}=\frac{5{,}5}{10}=0{,}55$, come la formula con $k=1$.

5. Generalizzazioni. Con valori tra $0$ e $N$ e soglia uniforme in $\{1,\dots,N\}$ lo stesso conto dà $\frac12+\frac k{2N}\ge\frac12+\frac1{2N}$: per $N=100$ la garanzia è $0{,}505$. Il vantaggio sul caso pessimo è piccolo ma garantito, mentre nessuna regola deterministica supera $\frac12$. Se invece l'input fosse una coppia uniforme tra le $\binom{11}2=55$ possibili, la media di $\frac12+\frac{l-s}{20}$ è $0{,}7$: ma è un'analisi del caso medio, che vale solo se l'input ha davvero quella distribuzione.

Risultato. Soglia fissa: caso pessimo $\frac12$, e lo stesso per ogni regola deterministica. Soglia casuale: $P(\text{vittoria})=\frac12+\frac{l-s}{20}\ge0{,}55$ per ogni input; con valori fino a $N$, $\ge\frac12+\frac1{2N}$.

from fractions import Fraction as F
def vittoria(s, l, N=10):                      # soglia T uniforme in 1..N, scatola aperta a caso
    p = F(0)
    for T in range(1, N + 1):
        for aperta, altra in ((s, l), (l, s)):
            ottiene = aperta if aperta >= T else altra
            p += F(1, 2 * N) * (ottiene == l)
    return p
v = {(s, l): vittoria(s, l) for s in range(11) for l in range(s + 1, 11)}
print(min(v.values()), v[(4, 5)], v[(3, 8)], v[(0, 10)])         # 11/20 11/20 3/4 1
print(all(p == F(1, 2) + F(l - s, 20) for (s, l), p in v.items()), sum(v.values()) / len(v))   # True 7/10

Verificato con frazioni esatte su tutte le $55$ coppie e con una simulazione sull'input $(4,5)$ ($0{,}552$ su $200\,000$ prove).