Esercizio - bilanciamento di insiemi con un colore casuale

Teoria: 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 → (bilanciamento di insiemi) e, per l'unione sugli eventi, Union bound e verifica randomizzata - identità polinomiali e prodotti di matriciSpazi discreti richiamati; inclusione-esclusione (con le troncate di Bonferroni) e union bound Pr[unione] ≤ somma, valido senza indipendenza e stretto quando gli eventi sono rari (collisioni: C(n,2)/m). Principio delle decisioni differite: si fissa tutto tranne una scelta casuale e si limita la probabilità su quella. Lemma di Schwartz-Zippel: un polinomio non nullo di grado totale d, valutato in un punto di S^n scelto uniformemente, si annulla con prob ≤ d/|S| (induzione sul numero di variabili); test di identità polinomiale con errore unilaterale, ripetuto (d/|S|)^k. Freivalds: per verificare AB=C si controlla A(Br)=Cr con r in {0,1}^n in tempo O(n^2), errore ≤ 1/2 (stretto), 2^-k con k prove. Fingerprint: due stringhe di n bit si confrontano con a mod p per un primo casuale p ≤ M, errore ≤ n/π(M).Union bound e verifica randomizzata - identità polinomiali e prodotti di matrici →.

Testo. Sono dati $m$ elementi e $n$ sottoinsiemi; $A$ è la matrice $n\times m$ con $A_{ij}=1$ se l'elemento $j$ sta nel sottoinsieme $i$. Si vuole colorare ogni elemento con $+1$ o $-1$ (vettore $b$) in modo che per ogni sottoinsieme $|(Ab)_i|=|\sum_jA_{ij}b_j|$ sia piccolo.

1. Dimostrare che esiste $b$ con $\max_i|(Ab)_i|\le\sqrt{4m\ln n}$ e calcolare il limite per $n=m=100$ e $n=m=1000$.
2. Con quale probabilità un colore casuale è buono? Quante prove servono in media?
3. Se la riga $i$ ha $w_i$ elementi, trovare un limite per riga: $|(Ab)_i|\le\sqrt{2w_i\ln(4n)}$ con probabilità $\ge\frac12$ per tutte le righe insieme. Calcolarlo per $w_i=50$, $n=100$.
4. Confrontare con una simulazione su una matrice casuale $100\times100$.

Soluzione

1. Esistenza. Si sceglie ogni $b_j\in\{-1,+1\}$ con probabilità $\frac12$, indipendentemente. La riga $i$ è $R_i=\sum_jA_{ij}b_j$, somma di $m$ termini indipendenti, il termine $j$ in $[-A_{ij},A_{ij}]\subseteq[-1,1]$ (ampiezza $\le2$), media $0$. Quindi $c=\sum(b_j-a_j)^2\le4m$ e Hoeffding dà, per $t>0$, $$P(|R_i|\ge t)\le2e^{-2t^2/(4m)}=2e^{-t^2/(2m)}.$$ Con $t=\sqrt{4m\ln n}$: $t^2/(2m)=2\ln n$, quindi $P(|R_i|\ge t)\le2e^{-2\ln n}=\frac2{n^2}$. Per l'unione sulle $n$ righe, la probabilità che almeno una superi $t$ è $\le n\cdot\frac2{n^2}=\frac2n<1$ per $n\ge3$. Dunque con probabilità positiva nessuna riga supera $t$: esiste un buon $b$. Numeri: $n=m=100$: $t=\sqrt{400\ln100}=\sqrt{1842{,}1}=42{,}9$; $n=m=1000$: $t=\sqrt{4000\ln1000}=166{,}2$. Sono molto meno del massimo banale $m$ ($100$ e $1000$).

2. Probabilità e prove. La probabilità che un colore casuale sia buono è $\ge1-\frac2n$: $0{,}98$ per $n=100$, $0{,}998$ per $n=1000$. Le prove sono indipendenti, quindi il numero di tentativi fino al successo è geometrico con media $\le\frac1{1-2/n}=1{,}020$ per $n=100$: un algoritmo Las Vegas (si verifica $\max_i|(Ab)_i|$ in tempo $O(nm)$).

3. Limite per riga. Con $w_i$ elementi nella riga, $c\le4w_i$ e $P(|R_i|\ge t_i)\le2e^{-t_i^2/(2w_i)}$. Con $t_i=\sqrt{2w_i\ln(4n)}$ questo vale $2e^{-\ln(4n)}=\frac1{2n}$ e per l'unione su $n$ righe $\le\frac12$. Per $w_i=50$, $n=100$: $t=\sqrt{100\ln400}=\sqrt{599{,}1}=24{,}5$. È quasi la metà del limite globale ($42{,}9$) perché le righe hanno $50$ elementi e non $100$.

4. Simulazione. Matrice casuale $100\times100$ con entrate $0/1$ equiprobabili (pesi di riga da $39$ a $64$, media $50{,}3$); $5000$ colori casuali:

• $\max_i|(Ab)_i|$ medio $16{,}65$, massimo osservato $35$: sempre sotto $42{,}9$ (il $100\%$ dei colori è buono, contro il $98\%$ garantito);
• il limite per riga (da $21{,}6$ a $27{,}7$ secondo il peso) è rispettato da tutte le righe nel $97{,}5\%$ dei colori, contro il $50\%$ garantito. Per $n=m=1000$: limite $166{,}2$, valore medio osservato $63{,}2$ (massimo $104$ su $200$ prove). I limiti sono molto prudenti, dello stesso ordine di grandezza $\sqrt{m\ln n}$ ma con costante circa doppia o tripla.

Risultato. Esiste $b$ con scarto $\le\sqrt{4m\ln n}$ ($42{,}9$ per $n=m=100$); un colore casuale va bene con probabilità $\ge1-\frac2n$.

Verifica.

import math
import numpy as np

rng = np.random.default_rng(3)
n = m = 100
A = (rng.random((n, m)) < 0.5).astype(int)
t = math.sqrt(4 * m * math.log(n)); w = A.sum(1); tr = np.sqrt(2 * w * math.log(4 * n))
mx, ok, ok_r = [], [], []
for _ in range(5000):
    v = np.abs(A @ rng.choice([-1, 1], size=m))
    mx.append(v.max()); ok.append(v.max() <= t); ok_r.append(bool(np.all(v <= tr)))
print(t, np.mean(mx), max(mx), np.mean(ok), np.mean(ok_r))   # 42.9 ~16.6 ~35 1.0 ~0.97