Union bound e verifica randomizzata - identità polinomiali e prodotti di matrici

In questa pagina 6

Modello e classi (Monte Carlo a errore unilaterale, amplificazione): Algoritmi randomizzati - Monte Carlo, Las Vegas e amplificazione. Base: Spazi di probabilità discreti e uniformi, Misura di probabilità e sue proprietà, Indipendenza di eventi.

1. Spazi discreti, inclusione-esclusione e union bound

Uno spazio discreto è un insieme finito o numerabile $\Omega$ con pesi $\Pr(\omega)\ge0$ di somma $1$ ; un evento è $A\subseteq\Omega$ e $\Pr(A)=\sum_{\omega\in A}\Pr(\omega)$ . Valgono monotonia ( $A\subseteq B\Rightarrow\Pr(A)\le\Pr(B)$ ), complemento $\Pr(\overline A)=1-\Pr(A)$ e, per eventi disgiunti, $\Pr(\bigcup A_i)=\sum\Pr(A_i)$ .

Inclusione-esclusione. Per tre eventi $\Pr(A\cup B\cup C)=\sum\Pr(A_i)-\sum_{i<j}\Pr(A_i\cap A_j)+\Pr(A\cap B\cap C),$ e in generale la somma alternata sulle intersezioni di $1,2,3,\dots$ eventi. Fermarsi dopo un numero dispari di termini dà un maggiorante, dopo un numero pari un minorante (disuguaglianze di Bonferroni).

Esempio. Si lanciano due dadi. $A$ : il primo dà $6$ ; $B$ : il secondo dà $6$ ; $C$ : la somma è $\ge10$ . Allora $\Pr(A)=\Pr(B)=\Pr(C)=\frac16$ , $\Pr(A\cap B)=\frac1{36}$ , $\Pr(A\cap C)=\Pr(B\cap C)=\frac1{12}$ (per $A\cap C$ servono $(6,4),(6,5),(6,6)$ ), $\Pr(A\cap B\cap C)=\frac1{36}$ . Quindi $\Pr(A\cup B\cup C)=\tfrac12-\tfrac7{36}+\tfrac1{36}=\tfrac{12}{36}=\tfrac13 .$ La somma sola $\frac12$ è un maggiorante, la somma meno le coppie $\frac{11}{36}$ un minorante, e il valore vero $\frac{12}{36}$ sta in mezzo.

Teorema (union bound). Per eventi $A_1,A_2,\dots$ qualunque (finiti o numerabili) $\Pr\Big(\bigcup_i A_i\Big)\le\sum_i\Pr(A_i).$

Dimostrazione. Si pone $B_i=A_i\setminus\bigcup_{j<i}A_j$ . Gli $B_i$ sono disgiunti, $B_i\subseteq A_i$ e $\bigcup B_i=\bigcup A_i$ . Quindi $\Pr(\bigcup A_i)=\sum\Pr(B_i)\le\sum\Pr(A_i)$ per monotonia. $\square$

Non richiede nessuna indipendenza: è lo strumento per dire «nessun evento cattivo accade», sommando le probabilità di ciascuno. È stretto quando gli eventi sono rari e quasi disgiunti, largo quando si sovrappongono molto.

Collisioni in una tabella hash. Si inseriscono $n$ chiavi in $m$ celle, ciascuna scelta uniformemente e in modo indipendente (Tabelle hash). Per ogni coppia $\{i,j\}$ l'evento $E_{ij}$ «le chiavi $i$ e $j$ cadono nella stessa cella» ha probabilità $1/m$ (data la cella di $i$ , $j$ deve coincidere). Le coppie sono $\binom n2$ , quindi $\Pr[\text{c'è una collisione}]\le\binom n2\frac1m .$ Con $n=141$ , $m=10^6$ : bound $0{,}00987$ , valore esatto $1-\prod_{i<n}(1-i/m)=0{,}00982$ (quasi uguali: le collisioni sono rare). Con $n=23$ , $m=365$ : bound $0{,}693$ , esatto $0{,}507$ (largo, perché molte collisioni coincidono; vedi Palline e urne - compleanno, carico massimo e approssimazione di Poisson).

2. Principio delle decisioni differite

Se le scelte casuali $r_1,\dots,r_n$ sono indipendenti, si può immaginare di fissare tutte tranne una e di estrarre l'ultima soltanto alla fine. Formalmente, per ogni evento $E$ $\Pr[E]=\sum_{r_{-j}}\Pr[r_{-j}]\cdot\Pr[E\mid r_{-j}] ,$ con $r_{-j}$ le scelte diverse da $r_j$ (Formula delle probabilità totali e formula di Bayes). Se per ogni valore fissato di $r_{-j}$ si prova $\Pr[E\mid r_{-j}]\le q$ , allora $\Pr[E]\le q$ . È la tecnica di tutte le dimostrazioni di questa nota.

3. Lemma di Schwartz-Zippel e identità polinomiali

Teorema (Schwartz-Zippel). Sia $P(x_1,\dots,x_n)$ un polinomio non nullo di grado totale $d$ su un campo $\mathbb F$ (Campi) e sia $S\subseteq\mathbb F$ finito. Se $r_1,\dots,r_n$ sono scelti uniformemente e indipendentemente in $S$ , allora $\Pr[P(r_1,\dots,r_n)=0]\le\frac d{|S|}.$

Dimostrazione. Per induzione sul numero $n$ di variabili.

$n=1$ . Un polinomio non nullo di grado $d$ in un campo ha al più $d$ radici, quindi si annulla in al più $d$ punti di $S$ : probabilità $\le d/|S|$ .

Passo. Si scrive $P=\sum_{i=0}^{k}x_1^{\,i}P_i(x_2,\dots,x_n)$ , con $k$ la massima potenza di $x_1$ presente, cioè $P_k\not\equiv0$ . Il grado totale di $P_k$ è $\le d-k$ . Sia $E_1$ l'evento $P_k(r_2,\dots,r_n)=0$ : per ipotesi induttiva $\Pr[E_1]\le(d-k)/|S|$ . Se $E_1$ non accade, il polinomio in una variabile $Q(x_1)=P(x_1,r_2,\dots,r_n)$ ha coefficiente direttivo $P_k(r_2,\dots,r_n)\ne0$ : è non nullo di grado $k$ . Per decisioni differite, $r_1$ è indipendente da $r_2,\dots,r_n$ , quindi $\Pr[Q(r_1)=0\mid\overline{E_1}]\le k/|S|$ . Allora $\Pr[P(r)=0]\le\Pr[E_1]+\Pr[P(r)=0\mid\overline{E_1}]\le\frac{d-k}{|S|}+\frac k{|S|}=\frac d{|S|}.\ \square$ (Se $k=0$ la variabile $x_1$ non compare e basta l'ipotesi induttiva.)

Il bound è ottimo: $P=\prod_{i=1}^d(x-s_i)$ con $s_i\in S$ distinti si annulla in $d$ punti di $S$ , probabilità esatta $d/|S|$ .

Test di identità polinomiale

Dato $P$ come «scatola nera» (o come formula/circuito, magari di grado esponenziale se espanso), si vuole sapere se $P\equiv0$ . Algoritmo: scegliere $r\in S^n$ a caso, calcolare $P(r)$ ; se $P(r)\ne0$ rispondere NON NULLO (certo), altrimenti rispondere NULLO. L'errore è unilaterale: sbaglia solo se $P\not\equiv0$ e $P(r)=0$ , con probabilità $\le d/|S|$ . Con $|S|\ge2d$ l'errore è $\le1/2$ ; con $k$ prove indipendenti $\le(d/|S|)^k$ (Algoritmi randomizzati - Monte Carlo, Las Vegas e amplificazione).

Esempio. Si lavora in $\mathbb F_{101}$ (numeri modulo $101$ , primo) con $S=\mathbb F_{101}$ e il punto $(x,y)=(37,58)$ .

Identità vera: $(x+y)^3=x^3+3x^2y+3xy^2+y^3$ . Il lato sinistro è $95^3\equiv87$ e il destro è $87$ : coincidono (per ogni punto, perché la differenza è il polinomio nullo).
Identità falsa: $(x+y)^3=x^3+y^3$ . La differenza è $3xy(x+y)$ , di grado $3$ . In $(37,58)$ si ha $x^3+y^3\equiv32\ne87$ : il test la smaschera. Gli zeri della differenza in $\mathbb F_{101}^2$ sono i punti con $x=0$ , $y=0$ oppure $x+y\equiv0$ : $3\cdot101-2=301$ su $101^2=10201$ , cioè $0{,}0295$ , quasi uguale al bound $3/101=0{,}0297$ .

Applicazione: accoppiamento perfetto. Dato un grafo bipartito con $n+n$ vertici (Grafi - definizioni e proprietà), si costruisce la matrice $M$ $n\times n$ con $M_{ij}=x_{ij}$ (variabile) se $i$ - $j$ è un arco e $0$ altrimenti. Il determinante (Permutazioni e definizione di determinante) è la somma, con segni, dei prodotti delle permutazioni, e ogni accoppiamento perfetto dà un monomio diverso: $\det M\not\equiv0$ se e solo se esiste un accoppiamento perfetto. $\det M$ ha grado $n$ : si valuta in un punto casuale modulo un primo grande con l'eliminazione di Gauss (Eliminazione di Gauss), in $O(n^3)$ . Per $n=2$ : archi $1\text{-}1,1\text{-}2,2\text{-}2$ danno $\det\begin{pmatrix}x_{11}&x_{12}\\0&x_{22}\end{pmatrix}=x_{11}x_{22}\ne0$ (accoppiamento $\{11,22\}$ ); archi $1\text{-}1,2\text{-}1$ danno $\det\begin{pmatrix}x_{11}&0\\x_{21}&0\end{pmatrix}=0$ (nessun accoppiamento).

python

import random

P = 101                                           # campo F_101

def vero(x, y):  return pow(x + y, 3, P) == (x**3 + 3*x*x*y + 3*x*y*y + y**3) % P
def falso(x, y): return pow(x + y, 3, P) == (x**3 + y**3) % P

def pit(identita, prove=1):                       # True = "identita' valida" (errore unilaterale)
    return all(identita(random.randrange(P), random.randrange(P)) for _ in range(prove))

print(pit(vero, 10), pit(falso, 10))              # True False (il secondo sbaglia con prob <= (3/101)^10)

4. Algoritmo di Freivalds: verificare un prodotto di matrici

Problema. Date $A,B,C$ matrici $n\times n$ , è vero che $AB=C$ (Operazioni tra matrici)? Calcolare $AB$ costa $O(n^3)$ con l'algoritmo ovvio (e circa $n^{2{,}37}$ con i migliori noti, Prodotto di matrici - algoritmo iterativo e ricorsivo a blocchi). Freivalds lo verifica in $O(n^2)$ .

Algoritmo (Freivalds). Si sceglie $r\in\{0,1\}^n$ uniformemente (ogni componente $0$ o $1$ con probabilità $1/2$ , indipendenti). Si calcola $y=A(Br)$ (due prodotti matrice-vettore, $2n^2$ operazioni) e $z=Cr$ ( $n^2$ ). Si risponde $AB=C$ se $y=z$ , altrimenti $AB\ne C$ .

Teorema. Se $AB=C$ risponde sempre giusto. Se $AB\ne C$ risponde $AB=C$ (errore) con probabilità $\le1/2$ .

Dimostrazione. Se $AB=C$ allora $A(Br)=(AB)r=Cr$ per ogni $r$ . Se $AB\ne C$ la matrice $D=AB-C$ ha un elemento $D_{ij}\ne0$ . L'algoritmo sbaglia solo se $Dr=0$ , e in particolare solo se $(Dr)_i=\sum_lD_{il}r_l=0$ . Per decisioni differite si fissano tutte le componenti $r_l$ con $l\ne j$ : la somma diventa $D_{ij}r_j+c$ con $c$ numero fisso. Poiché $r_j\in\{0,1\}$ , i due valori $c$ e $c+D_{ij}$ sono diversi, quindi al più uno annulla la somma: $\Pr[(Dr)_i=0\mid r_{-j}]\le1/2$ per ogni $r_{-j}$ , e perciò $\Pr[Dr=0]\le1/2$ . $\square$

È un caso particolare di Schwartz-Zippel con $S=\{0,1\}$ e grado $1$ . Il bound $1/2$ è stretto: se $D$ ha un solo elemento non nullo $D_{ij}$ , $Dr=0$ equivale a $r_j=0$ , probabilità esatta $1/2$ . Con $k$ prove indipendenti l'errore è $\le2^{-k}$ e il costo $O(kn^2)$ ; usando $r\in S^n$ con $|S|$ elementi l'errore scende a $1/|S|$ .

A mano, $n=3$ . Siano $A=\begin{pmatrix}1&2&0\\3&1&2\\0&1&1\end{pmatrix},\ B=\begin{pmatrix}2&0&1\\1&1&0\\1&3&2\end{pmatrix},\ AB=\begin{pmatrix}4&2&1\\9&7&7\\2&4&2\end{pmatrix},$ e sia $C$ uguale a $AB$ tranne $C_{12}=3$ (invece di $2$ ), quindi $D_{12}=-1$ . Si provano tutti gli $8$ vettori $r$ (colonna $Br$ , poi $A(Br)$ confrontato con $Cr$ ):

$r$	$Br$	$A(Br)$	$Cr$	esito
$(0,0,0)$	$(0,0,0)$	$(0,0,0)$	$(0,0,0)$	passa (errore)
$(0,0,1)$	$(1,0,2)$	$(1,7,2)$	$(1,7,2)$	passa (errore)
$(0,1,0)$	$(0,1,3)$	$(2,7,4)$	$(3,7,4)$	scoperto
$(0,1,1)$	$(1,1,5)$	$(3,14,6)$	$(4,14,6)$	scoperto
$(1,0,0)$	$(2,1,1)$	$(4,9,2)$	$(4,9,2)$	passa (errore)
$(1,0,1)$	$(3,1,3)$	$(5,16,4)$	$(5,16,4)$	passa (errore)
$(1,1,0)$	$(2,2,4)$	$(6,16,6)$	$(7,16,6)$	scoperto
$(1,1,1)$	$(3,2,6)$	$(7,23,8)$	$(8,23,8)$	scoperto

L'errore avviene per i $4$ vettori con $r_2=0$ : probabilità esatta $4/8=1/2$ , come previsto dal caso a un solo elemento sbagliato.

python

import random

def freivalds(A, B, C, k=20):                     # False => AB != C (certo); True => AB == C con errore <= 2^-k
    n = len(A)
    mv = lambda M, v: [sum(M[i][j] * v[j] for j in range(n)) for i in range(n)]
    for _ in range(k):
        r = [random.randint(0, 1) for _ in range(n)]
        if mv(A, mv(B, r)) != mv(C, r):
            return False
    return True

A = [[1, 2, 0], [3, 1, 2], [0, 1, 1]]; B = [[2, 0, 1], [1, 1, 0], [1, 3, 2]]
AB = [[4, 2, 1], [9, 7, 7], [2, 4, 2]]; C = [row[:] for row in AB]; C[0][1] = 3
print(freivalds(A, B, AB), freivalds(A, B, C))   # True False

5. Fingerprint: confrontare stringhe con poca comunicazione

Alice ha una stringa $a$ di $n$ bit, Bob una stringa $b$ ; vogliono sapere se $a=b$ scambiando pochi bit. Deterministicamente servono $n$ bit. Con la randomizzazione: Alice sceglie un primo casuale $p\le M$ e manda $(p,\ a\bmod p)$ , interpretando $a$ come intero; Bob risponde che sono uguali se $a\bmod p=b\bmod p$ .

Teorema. Se $a=b$ l'esito è sempre giusto. Se $a\ne b$ l'errore ha probabilità $\le n/\pi(M)$ , dove $\pi(M)\approx M/\ln M$ è il numero di primi $\le M$ .

Dimostrazione. L'errore avviene se $p$ divide $d=|a-b|$ , con $1\le d<2^n$ . Ogni primo divisore è $\ge2$ , quindi $d$ ha al più $n$ divisori primi distinti (il loro prodotto è $\le d<2^n$ ). Scegliendo $p$ uniforme tra i $\pi(M)$ primi, la probabilità di cadere in uno di quegli $\le n$ è $\le n/\pi(M)$ . $\square$

Numeri. Con $n=1000$ bit e $M=10^6$ : $\pi(M)=78498$ , errore $\le1000/78498=0{,}0127$ (più finemente: il prodotto dei $130$ primi più piccoli supera già $2^{1000}$ , quindi $d$ ha al più $129$ divisori primi e l'errore è $\le129/78498=0{,}0016$ ). Si comunicano circa $2\log_2M\approx40$ bit invece di $1000$ . Con $M=n^2$ l'errore è circa $2\ln n/n$ e tende a $0$ . Un tipico uso è il confronto di una finestra di testo con un pattern (Rabin-Karp): si confrontano le impronte e solo in caso di uguaglianza si verifica carattere per carattere. Altre impronte (famiglie universali, Bloom): Hashing randomizzato - famiglie universali, filtri di Bloom e fingerprint.

Esempio piccolo. $a=181=10110101_2$ , $b=165=10100101_2$ , $d=16=2^4$ (unico primo: $2$ ). Con $p$ scelto tra $\{2,3,5,7,11,13\}$ i resti di $a$ sono $1,1,1,6,5,12$ e quelli di $b$ sono $1,0,0,4,0,9$ : coincidono solo per $p=2$ , errore $1/6$ . Con $b'=151$ , $d=30=2\cdot3\cdot5$ : coincidono per $p=2,3,5$ , errore $3/6$ .

Domande d'esame

Dimostra l'union bound. Si disgiunge: $B_i=A_i\setminus\bigcup_{j<i}A_j$ , $\bigcup B_i=\bigcup A_i$ , $\Pr(B_i)\le\Pr(A_i)$ .
Enuncia Schwartz-Zippel e dimostra il caso $n=1$ . Vedi la sezione 3: un polinomio non nullo di grado $d$ ha al più $d$ radici, probabilità $\le d/|S|$ .
Perché Freivalds ha errore $\le1/2$ ? Con $D=AB-C\ne0$ e $D_{ij}\ne0$ si fissano le $r_l$ , $l\ne j$ : i due valori di $r_j$ danno due valori diversi di $(Dr)_i$ , e al più uno è $0$ .
Quanti primi casuali $\le10^6$ servono per far scendere l'errore del fingerprint di stringhe da $1000$ bit sotto $10^{-6}$ ? Una prova ha errore $\le0{,}0127$ ; con $k$ prove indipendenti $0{,}0127^k\le10^{-6}$ dà $k=4$ (con il bound più fine $0{,}0016$ ne bastano $3$ ).

Versione ripasso

Spazi discreti: $\Pr(A)=\sum_{\omega\in A}\Pr(\omega)$ ; monotonia, complemento, somma per disgiunti (Misura di probabilità e sue proprietà). Inclusione-esclusione per tre eventi: somme alternate; fermarsi a un numero dispari di termini dà un maggiorante, pari un minorante. Dadi con $A,B,C$ sopra: $\frac12-\frac7{36}+\frac1{36}=\frac13$ , minorante $\frac{11}{36}$ .
Union bound: $\Pr(\bigcup A_i)\le\sum\Pr(A_i)$ , senza indipendenza. Prova: $B_i=A_i\setminus\bigcup_{j<i}A_j$ disgiunti, $B_i\subseteq A_i$ . Collisioni: $\binom n2/m$ ; $n=141$ , $m=10^6$ : $0{,}00987$ contro esatto $0{,}00982$ ; $n=23$ , $m=365$ : $0{,}693$ contro $0{,}507$ .
Decisioni differite: fissare tutte le scelte tranne una e limitare la probabilità condizionata su quella; se vale $\le q$ per ogni valore fissato, vale $\le q$ in totale (Formula delle probabilità totali e formula di Bayes).
Schwartz-Zippel: $P\not\equiv0$ di grado totale $d$ , $r\in S^n$ uniforme: $\Pr[P(r)=0]\le d/|S|$ . Prova per induzione su $n$ : $P=\sum x_1^iP_i$ , $P_k\not\equiv0$ con $\deg P_k\le d-k$ ; $\Pr[P_k(r_2..r_n)=0]\le(d-k)/|S|$ , altrimenti polinomio in $x_1$ di grado $k$ con $\le k$ radici; somma $d/|S|$ . Ottimo per $\prod(x-s_i)$ .
Test di identità: valutare in un punto casuale, errore unilaterale $\le d/|S|$ , con $k$ prove $(d/|S|)^k$ . Esempio in $\mathbb F_{101}$ : $(x+y)^3-(x^3+y^3)=3xy(x+y)$ ha $301/10201=0{,}0295$ zeri contro il bound $3/101$ . Accoppiamento perfetto: $\det$ della matrice di Edmonds $\not\equiv0$ sse esiste, grado $n$ , $O(n^3)$ modulo un primo.
Freivalds: $r\in\{0,1\}^n$ , confrontare $A(Br)$ con $Cr$ in $O(n^2)$ ; se $AB\ne C$ errore $\le1/2$ (prova con $D_{ij}\ne0$ e decisioni differite, stretto con un solo elemento sbagliato), $2^{-k}$ con $k$ prove. Esempio $3\times3$ con $C_{12}=3$ : errore per i $4$ vettori con $r_2=0$ su $8$ .
Fingerprint: $a\bmod p$ con $p\le M$ primo casuale, errore $\le n/\pi(M)$ (ogni $d<2^n$ ha $\le n$ primi divisori). $n=1000$ , $M=10^6$ : $0{,}0127$ (più fine $0{,}0016$ ), circa $40$ bit comunicati.
Dadi, dettaglio: $\Pr(A\cap C)=\Pr(B\cap C)=3/36$ (per $A\cap C$ : $(6,4),(6,5),(6,6)$ ), $\Pr(A\cap B\cap C)=1/36$ .
Collisioni: $\Pr[E_{ij}]=1/m$ perché, data la cella di $i$ , la cella di $j$ deve coincidere; le coppie sono $\binom n2$ .
Esempio $\mathbb F_{101}$ , punto $(37,58)$ : $(x+y)^3\equiv87$ coincide con lo sviluppo, mentre $x^3+y^3\equiv32\ne87$ smaschera l'identità falsa; zeri della differenza: $x=0$ , $y=0$ o $x+y\equiv0$ , cioè $3\cdot101-2=301$ punti.
Edmonds, $n=2$ : archi $1\text{-}1,1\text{-}2,2\text{-}2$ danno $\det=x_{11}x_{22}\ne0$ (accoppiamento); archi $1\text{-}1,2\text{-}1$ danno $\det=0$ (nessun accoppiamento).
Freivalds, $3\times3$ : con $C_{12}=3$ invece di $2$ (quindi $D_{12}=-1$ ) si scoprono gli $r$ con $r_2=1$ : $(0,1,0)$ dà $A(Br)=(2,7,4)\ne Cr=(3,7,4)$ ; $(1,0,1)$ non scopre nulla, $A(Br)=Cr=(5,16,4)$ . Costo di una prova: $3$ prodotti matrice-vettore, $O(n^2)$ , contro $O(n^3)$ del prodotto.
Fingerprint, esempio piccolo: $a=181$ , $b=165$ , $d=16=2^4$ : con primi in $\{2,3,5,7,11,13\}$ i resti coincidono solo per $p=2$ (errore $1/6$ ); con $b'=151$ , $d=30=2\cdot3\cdot5$ , coincidono per $p=2,3,5$ ( $3/6$ ). Con $k$ prove indipendenti sotto $10^{-6}$ da $0{,}0127$ : $k=4$ .
Errori tipici: usare l'union bound con ripetizioni e dimenticare che è solo un maggiorante; confondere grado totale e grado in una variabile; scegliere $S$ troppo piccolo ( $|S|<d$ il bound è vuoto); usare lo stesso $r$ per tutte le prove di Freivalds; scrivere $\Pr[A\cup B]=\Pr[A]+\Pr[B]$ senza disgiunzione.