Esercizio - 1023 bit indipendenti a coppie da dieci bit casuali

Teoria: Momenti e deviazioni - Markov, Chebyshev e mediana randomizzataVar(ΣX_i) = ΣVar + 2ΣCov, e basta l'indipendenza a coppie perché la varianza si sommi. Chebyshev dà code polinomiali (collezionista: P(T ≥ nH_n + cn) ≤ π²/(6c²)); il metodo del secondo momento dà P(X=0) ≤ Var(X)/E[X]². Algoritmo della mediana: campione di n^(3/4) elementi, due estremi d e u a ±√n, ordinamento dei soli elementi tra d e u; fallisce con probabilità ≤ n^(-1/4) ed è Las Vegas con 2n + o(n) confronti.Momenti e deviazioni - Markov, Chebyshev e mediana randomizzata → (indipendenza a coppie) e 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 → (che cosa serve per le code esponenziali).

Testo. Si estraggono $k=10$ bit uniformi indipendenti $Y_1,\dots,Y_{10}$. Per ogni sottoinsieme non vuoto $S\subseteq\{1,\dots,10\}$ si definisce $X_S=\bigoplus_{i\in S}Y_i$ (somma modulo $2$): sono $n=2^{10}-1=1023$ bit. Sia $W=\sum_SX_S$ il numero di bit uguali a $1$.

1. Mostrare che ogni $X_S$ è uniforme e che i bit sono indipendenti a coppie.
2. Calcolare $E[W]$ e $\mathrm{Var}(W)$.
3. Limitare con Chebyshev $P(|W-E[W]|\ge100)$ e $P(W=0)$.
4. Ricavare la vera legge di $W$ e confrontare. Che cosa mostra rispetto a 1023 bit davvero indipendenti?

Soluzione

1. Fissato $S\ne\emptyset$, $X_S$ è la somma modulo $2$ di bit indipendenti uniformi e ne contiene almeno uno: è uniforme (invertire un solo $Y_i$ con $i\in S$ inverte $X_S$). Per $S\ne S'$ esiste un indice $i$ in uno solo dei due insiemi, diciamo $i\in S\setminus S'$. Condizionando a tutti gli $Y_j$ con $j\ne i$ (che fissano $X_{S'}$), $X_S$ rimane uniforme grazie a $Y_i$. Quindi $P(X_S=a,X_{S'}=b)=\frac12\cdot\frac12$ per ogni $(a,b)$: indipendenza a coppie. Ma non c'è indipendenza di tutti: per $S=\{1\}$, $S'=\{2\}$, $S''=\{1,2\}$ si ha $X_{S''}=X_S\oplus X_{S'}$.

2. $E[X_S]=\frac12$, quindi $E[W]=\frac{1023}2=511{,}5$. Per l'indipendenza a coppie le covarianze sono nulle e le varianze si sommano: $\mathrm{Var}(X_S)=\frac14$, quindi $\mathrm{Var}(W)=\frac{1023}{4}=255{,}75$.

3. Chebyshev. $$P(|W-511{,}5|\ge100)\le\frac{255{,}75}{100^2}=0.0256.$$ Per $W=0$ (scostamento $511{,}5$): $P(W=0)\le\frac{255{,}75}{511{,}5^2}=\frac{1}{1023}=0{,}000978$.

4. Legge esatta. $W$ dipende solo dai dieci bit $Y=(Y_1,\dots,Y_{10})$. Se $Y=0$ tutti gli $X_S$ valgono $0$: $W=0$. Se $Y\ne0$, si fissa un $i$ con $Y_i=1$: aggiungere o togliere $i$ a $S$ inverte $\bigoplus_{i\in S}Y_i$, quindi i $2^{10}$ sottoinsiemi si accoppiano a due a due con valori opposti e la metà esatta, $512$, dà $1$ (il sottoinsieme vuoto dà $0$, quindi i $512$ sono tutti non vuoti). Dunque $$W=\begin{cases}0&\text{con probabilità }\frac1{1024}\\512&\text{con probabilità }\frac{1023}{1024}.\end{cases}$$ Controllo: $E[W]=512\cdot\frac{1023}{1024}=511{,}5$ e $E[W^2]=512^2\cdot\frac{1023}{1024}$, quindi $\mathrm{Var}(W)=262144\cdot\frac{1023}{1024}-511{,}5^2=261888-261632{,}25=255{,}75$ ✓. Il valore vero di $P(|W-511{,}5|\ge100)$ è $P(W=0)=\frac1{1024}=0{,}000977$: Chebyshev dà $0{,}0256$ (26 volte di più), ma per $P(W=0)$ dà $\frac1{1023}$, quasi esatto ($\frac1{1024}$).

Confronto con bit indipendenti. Per 1023 bit indipendenti Hoeffding darebbe $P(|W-511{,}5|\ge100)\le2e^{-2\cdot100^2/1023}=2e^{-19{,}55}=6{,}5\times10^{-9}$, e $P(W=0)=2^{-1023}$. Qui $P(W=0)=2^{-10}$: con la sola indipendenza a coppie la coda può restare polinomiale, e Chebyshev è il meglio che si possa dire (il suo caso limite è proprio questo). Chernoff e Hoeffding richiedono l'indipendenza di tutte le variabili (la funzione generatrice si fattorizza solo così). In compenso bastano $10$ bit casuali invece di $1023$.

Risultato. $E[W]=511{,}5$, $\mathrm{Var}(W)=255{,}75$; Chebyshev $0{,}0256$ (vero $\frac1{1024}$); $P(W=0)\le\frac1{1023}$ (vero $\frac1{1024}$).

Verifica.

from collections import Counter
from fractions import Fraction as F

k = 10
pesi = []
for y in range(1 << k):                      # tutti i valori dei dieci bit
    pesi.append(sum(bin(S & y).count("1") % 2 for S in range(1, 1 << k)))
print(Counter(pesi))                          # {512: 1023, 0: 1}
E = F(sum(pesi), len(pesi)); V = F(sum(w * w for w in pesi), len(pesi)) - E * E
print(E, V)                                   # 1023/2 1023/4