Metodo probabilistico - valore atteso, alterazioni e derandomizzazione

Il metodo probabilistico dimostra che un oggetto con certe proprietà esiste senza costruirlo: si sceglie un oggetto a caso e si mostra che la proprietà vale con probabilità positiva. La probabilità è solo uno strumento di conteggio (spazio uniforme, Spazi di probabilità discreti e uniformiIn uno spazio discreto la probabilità è determinata dalla densità discreta p(ω) = P({ω}), con somma 1, e P(A) è la somma di p(ω) sugli esiti di A; negli spazi uniformi (esiti equiprobabili) P(A) = |A| / |Ω|, casi favorevoli su casi possibili.Spazi di probabilità discreti e uniformi →); il risultato è deterministico. Con la derandomizzazione si ottiene poi anche un algoritmo. Prerequisiti: Valore attesoIl valore atteso E[X] = Σ x p_X(x) è la media dei valori di X pesata con le loro probabilità (esiste se la serie converge assolutamente); per una funzione g vale E[g(X)] = Σ g(x) p_X(x) senza trovare la legge di g(X), ed E è lineare: E[aX + bY + c] = aE[X] + bE[Y] + c.Valore atteso →, Linearità del valore atteso e variabili indicatriciLa linearità $E[X+Y]=E[X]+E[Y]$ vale sempre, anche senza indipendenza; con le variabili indicatrici ($E[I_A]=P(A)$) trasforma un conteggio in una somma di probabilità. Applicazioni: attesa del primo successo $1/p$, collezionista di figurine $nH_n$, punti fissi di una permutazione (media $1$), record (media $H_n$), inversioni ($n(n-1)/4$), attesa condizionata, identità di Wald $E[S_N]=E[N]E[X]$.Linearità del valore atteso e variabili indicatrici →, 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 →, Grafi - definizioni e proprietàGrafo G=(V,E) diretto e non diretto, grafo semplice e pesato; incidenza, adiacenza, grado; cammini, cicli, sottografi, grafi connessi e componenti connesse; alberi liberi, foreste, spanning tree e spanning forest; proprietà con dimostrazioni (somma dei gradi = 2m, m <= n(n-1)/2, alberi m = n-1, connessi m >= n-1, foreste m <= n-1).Grafi - definizioni e proprietà →.

I due principi

Lemma (principio del valore atteso). Se $X$ è una variabile aleatoria discreta con $E[X]=\mu$, allora $P(X\ge\mu)>0$ e $P(X\le\mu)>0$. Esistono quindi un esito con $X\ge\mu$ e uno con $X\le\mu$.

Dimostrazione. Se fosse $X<\mu$ con probabilità $1$ si avrebbe $E[X]<\mu$; per l'altro verso è lo stesso. $\square$ Se $X$ è intera, esiste un esito con $X\ge\lceil\mu\rceil$.

Principio (conteggio). Se in uno spazio finito $P(\text{l'oggetto ha la proprietà }\mathcal P)>0$ allora esiste un oggetto con $\mathcal P$. In particolare, se $X$ conta i "difetti" e $E[X]<1$, per Markov $P(X\ge1)\le E[X]<1$ e quindi esiste un oggetto con zero difetti.

Taglio grande

Teorema (taglio). Ogni grafo con $|E|$ archi ha un taglio (partizione dei vertici in due insiemi) con almeno $\lceil|E|/2\rceil$ archi tra le due parti.

Dimostrazione. Ogni vertice va in $A$ o in $B$ con probabilità $\frac12$, indipendentemente. Un arco $\{u,v\}$ è tagliato se i suoi estremi cadono in parti diverse: probabilità $\frac12$ (qualunque sia $u$, $v$ va dall'altra parte con $\frac12$). Per la linearità, $E[\text{archi tagliati}]=\frac{|E|}2$, e per il lemma esiste un taglio con almeno $\lceil|E|/2\rceil$ archi. $\square$

Esempi. Per $K_4$: $|E|=6$, media $3$ (anche calcolata su tutte le $2^4$ assegnazioni) e taglio massimo $4$. Per il grafo di Petersen ($10$ vertici, $15$ archi): media $7{,}5$, quindi esiste un taglio $\ge8$; il massimo è $12$ (calcolo esaustivo su $2^9$ tagli).

MAX-SAT e il fattore $7/8$

Una formula in forma normale congiuntiva ha $m$ clausole, ognuna disgiunzione di letterali (una variabile o la sua negazione). Si assegna a ogni variabile $\text{vero}$ o $\text{falso}$ con probabilità $\frac12$ indipendentemente.

Teorema (MAX-SAT). Una clausola con $\ell$ letterali su variabili distinte è soddisfatta con probabilità $1-2^{-\ell}$ (è falsa solo se ogni letterale è falso). Quindi in una formula con $m$ clausole di $3$ letterali esiste un'assegnazione che ne soddisfa almeno $\frac78m$ (arrotondato in su). Se tutte le clausole hanno almeno $k$ letterali e $m<2^k$, la formula è soddisfacibile.

Dimostrazione. $E[\text{soddisfatte}]=m(1-2^{-3})=\frac78m$. Per la seconda parte: $E[\text{insoddisfatte}]\le m2^{-k}<1$ e, per il principio di conteggio, esiste un'assegnazione con $0$ clausole insoddisfatte. $\square$

Il $\frac78$ è ottimo nel caso peggiore: le $8$ clausole che hanno tutte le combinazioni di segni su $x_1,x_2,x_3$ non sono simultaneamente soddisfacibili, e ogni assegnazione ne soddisfa esattamente $7$ (verificato su tutte le $8$ assegnazioni).

Lo stesso schema (indicatori e linearità su tutti gli oggetti possibili) dimostra che esiste un torneo su $n$ giocatori con almeno $n!/2^{n-1}$ cammini hamiltoniani: Esercizio - Cammini hamiltoniani in un torneo casuale (lezioni MIT).

Limite inferiore dei numeri di Ramsey

Il numero di Ramsey $R(k,k)$ è il minimo $n$ tale che in ogni colorazione degli archi di $K_n$ con due colori compare un $K_k$ monocromatico (cioè $k$ vertici con tutti i $\binom k2$ archi dello stesso colore).

Teorema. Se $\binom nk2^{1-\binom k2}<1$ allora $R(k,k)>n$. In particolare $R(k,k)>\lfloor2^{k/2}\rfloor$ per ogni $k\ge3$.

Dimostrazione. Si colora ogni arco di $K_n$ in rosso o blu con probabilità $\frac12$, indipendentemente. Un fissato insieme di $k$ vertici è monocromatico con probabilità $2\cdot2^{-\binom k2}=2^{1-\binom k2}$ (tutto rosso o tutto blu). Sia $X$ il numero di $K_k$ monocromatici: per la linearità $E[X]=\binom nk2^{1-\binom k2}<1$, quindi esiste una colorazione con $X=0$. Con $n=\lfloor2^{k/2}\rfloor$ e $\binom nk\le\frac{n^k}{k!}\le\frac{2^{k^2/2}}{k!}$: $$\binom nk2^{1-k(k-1)/2}\le\frac{2^{k^2/2+1-k^2/2+k/2}}{k!}=\frac{2^{k/2+1}}{k!}<1\quad(k\ge3),$$ perché per $k=3$ vale $\frac{2^{2,5}}6=0{,}943$ e poi il denominatore cresce molto più in fretta. $\square$

Numeri. Il massimo $n$ per cui la condizione vale è $3,6,11,17,27$ per $k=3,\dots,7$. Per $k=5$, $n=11$: il numero atteso di $K_5$ monocromatici è $462\cdot2^{-9}=0{,}902$, e una simulazione su $3000$ colorazioni casuali trova una colorazione senza $K_5$ monocromatici nel $61{,}5\%$ dei casi. Per $k=4$, $n=6$: $\binom64/32=0{,}469$ e tra tutte le $2^{15}$ colorazioni il $68{,}6\%$ ($22\,484$) non ha $K_4$ monocromatici.

È una dimostrazione di esistenza: nessuna costruzione esplicita nota raggiunge una crescita esponenziale paragonabile. Il limite superiore è di forma $4^k$, quindi $R(k,k)$ cresce esponenzialmente in $k$.

Alterazione

Il caso in cui l'oggetto casuale ha pochi difetti: si toglie (altera) ciò che non va.

Teorema (insieme indipendente). Un grafo con $n$ vertici e $m\ge n/2$ archi, grado medio $d=2m/n\ge1$, contiene un insieme indipendente (nessun arco tra i suoi vertici) di almeno $\frac n{2d}=\frac{n^2}{4m}$ vertici.

Dimostrazione. Ogni vertice entra in $S$ con probabilità $p$ indipendentemente. Sia $Y$ il numero di archi con entrambi gli estremi in $S$. $E[|S|]=np$ e $E[Y]=mp^2$ (un arco sta in $S$ con probabilità $p^2$). Si rimuove un estremo per ogni arco rimasto in $S$: restano almeno $|S|-Y$ vertici e sono indipendenti. $E[|S|-Y]=np-mp^2$ è massima in $p=\frac n{2m}=\frac1d$, dove vale $\frac n{2d}$. Per il lemma esiste un esito con $|S|-Y\ge\frac n{2d}$. $\square$

Numeri ($n=1000$, $m=2000$, $d=4$). Il teorema garantisce $125$; il guadagno in funzione di $p$ è $np-mp^2=80;\ 120;\ 125;\ 120;\ 80$ per $p=0{,}1;\ 0{,}2;\ 0{,}25;\ 0{,}3;\ 0{,}4$. Su un grafo casuale con questi parametri la procedura con $p=\frac14$ (togliendo un estremo solo per gli archi ancora presenti) dà $157{,}6$ vertici in media su $2000$ prove (da $130$ a $187$; grafo e codice in Esercizio - Insiemi indipendenti con alterazione e lemma locale di Lovász per k-SAT): il limite è un minimo garantito, non una stima.

Variante più forte. Si ordinano i vertici con una permutazione casuale e si tengono quelli che precedono tutti i loro vicini. Un vertice di grado $d_v$ è il primo tra sé e i suoi $d_v$ vicini con probabilità $\frac1{d_v+1}$, e l'insieme è indipendente (di due adiacenti ne può precedere solo uno). Quindi $E|I|=\sum_v\frac1{d_v+1}\ge\frac n{d+1}$ (disuguaglianza di Jensen). Sul grafo precedente: $\sum\frac1{d_v+1}=243{,}0\ge\frac{1000}5=200>125$. Questo limite (di Caro-Wei), applicato al grafo complementare, dà il teorema di Turán sulle cricche: Esercizio - Teorema di Turán dal limite di Caro-Wei (lezioni MIT).

Alterazione per Ramsey. Dopo la colorazione casuale si toglie un vertice per ogni $K_k$ monocromatico: restano almeno $n-X$ vertici senza monocromatici, quindi $R(k,k)>n-\binom nk2^{1-\binom k2}$ per ogni $n$. Per $k=10$ il valore massimo del secondo membro è $115{,}1$ ($n=127$), contro il $100$ del teorema semplice e contro $2^{k/2}=32$.

Derandomizzazione con le aspettative condizionate

Il metodo probabilistico dimostra l'esistenza; si può anche trovare l'oggetto in tempo polinomiale.

Metodo delle aspettative condizionate. Se $X$ è una funzione di $x_1,\dots,x_n$ scelte a caso e $E[X\mid x_1,\dots,x_i]$ si calcola in tempo polinomiale, si fissano le variabili una alla volta scegliendo il valore che non fa diminuire l'attesa condizionale. Dato che $E[X\mid x_1,\dots,x_i]=\frac12E[X\mid x_1,\dots,x_i,0]+\frac12E[X\mid x_1,\dots,x_i,1]$, il massimo dei due è $\ge$ la media: l'attesa non scende mai e alla fine si ha un esito deterministico con $X\ge E[X]$.

Taglio. Con $v_1,\dots,v_i$ già piazzati, $E[\text{taglio}]=(\text{archi già tagliati})+\frac12(\text{archi non ancora decisi})$. Piazzare $v_{i+1}$ sul lato che taglia più archi verso i vicini già piazzati ($c_0$ o $c_1$ archi) aumenta l'attesa di $\max(c_0,c_1)-\frac{c_0+c_1}2\ge0$. L'algoritmo è l'euristica golosa: ogni vertice dal lato opposto alla maggioranza dei vicini già piazzati, taglio finale $\ge\frac{|E|}2$.

Esempio (Petersen, ordine dei vertici $0,\dots,9$). Numerazione: ciclo esterno $0$-$1$-$2$-$3$-$4$-$0$, raggi da $i$ a $i+5$, e il vertice interno $5+i$ adiacente a $5+((i+2)\bmod 5)$; a parità ($c_0=c_1$) il vertice va nel lato $0$. La tabella passo per passo è in Esercizio - Taglio grande e derandomizzazione sul grafo di Petersen. L'attesa condizionale dopo ogni vertice piazzato è $\frac{15}2,\frac{15}2,8,\frac{17}2,9,9,\frac{19}2,10,10,\frac{21}2,12$ (dal valore iniziale $\frac{15}2$ fino al taglio finale): non decresce mai e il taglio ottenuto è $12$, cioè il massimo.

MAX-SAT. Con variabili già fissate, ogni clausola vale $1$ se ha un letterale vero, altrimenti $1-2^{-\ell}$ con $\ell$ letterali liberi (e $0$ se non ne restano). Esempio. $m=7$ clausole su $x_1,\dots,x_5$:

$C_1=x_1\lor x_2\lor\lnot x_3$, $C_2=\lnot x_1\lor x_3\lor x_4$, $C_3=x_2\lor\lnot x_4\lor x_5$, $C_4=\lnot x_2\lor\lnot x_3\lor\lnot x_5$, $C_5=x_1\lor\lnot x_4\lor\lnot x_5$, $C_6=\lnot x_1\lor\lnot x_2\lor x_5$, $C_7=x_3\lor x_4\lor x_5$.

L'attesa iniziale è $7\cdot\frac78=\frac{49}8=6{,}125$. Poiché $m=7<8=2^3$, la formula è soddisfacibile. Il metodo procede così:

Controllo del passo $x_2=\text{falso}$ dopo $x_1=\text{vero}$: $C_1$, $C_4$, $C_5$, $C_6$ sono già vere ($1$ ciascuna); $C_2$ ha $x_3,x_4$ liberi: $\frac34$; $C_3$ ha $\lnot x_4,x_5$ liberi: $\frac34$; $C_7$ ha tre liberi: $\frac78$. Somma: $4+\frac34+\frac34+\frac78=\frac{51}8$. Alla fine $(x_1,\dots,x_5)=(1,0,1,0,1)$ soddisfa tutte e $7$ le clausole: l'attesa è salita da $6{,}125$ a $7$.

from fractions import Fraction

def attesa(clausole, parziale):
    """Numero atteso di clausole soddisfatte se le variabili libere sono a caso."""
    tot = Fraction(0)
    for c in clausole:                                  # c = lista di (variabile, segno)
        liberi = 0
        for v, s in c:
            if v not in parziale:
                liberi += 1
            elif parziale[v] == (s > 0):                # un letterale vero: clausola soddisfatta
                tot += 1
                break
        else:                                           # nessun letterale vero finora
            tot += 1 - Fraction(1, 2 ** liberi)         # 0 se non resta nessuna variabile libera
    return tot

def derandomizza(clausole, variabili):
    parziale = {}
    for v in variabili:                                 # per ogni variabile sceglie il valore
        e1 = attesa(clausole, {**parziale, v: True})    # che non fa scendere l'attesa condizionale
        e0 = attesa(clausole, {**parziale, v: False})
        parziale[v] = e1 >= e0
    return parziale

Lemma locale di Lovász (solo enunciato)

L'union bound richiede $\sum P(A_i)<1$, quindi funziona solo con pochi eventi cattivi. Se gli eventi sono "quasi indipendenti" se ne possono avere moltissimi.

Lemma locale di Lovász (forma simmetrica). Siano $A_1,\dots,A_N$ eventi "cattivi" con $P(A_i)\le p$ e ognuno indipendente da tutti gli altri tranne al più $d$. Se $e\,p\,(d+1)\le1$ allora $P\bigl(\bigcap_i\overline{A_i}\bigr)>0$: con probabilità positiva nessun evento cattivo accade.

Applicazione. Una formula $k$-CNF in cui ogni clausola ha $k$ variabili distinte e ogni variabile compare in al più $r$ clausole è soddisfacibile se $e\,2^{-k}\bigl(k(r-1)+1\bigr)\le1$: l'evento "la clausola $C$ è falsa" ha probabilità $p=2^{-k}$ e dipende al più dalle $d=k(r-1)$ clausole che condividono una variabile con $C$. Per $k=10$ basta $r\le38$ ($e\cdot2^{-10}\cdot(10\cdot37+1)=0{,}985$); per $k=5$, $r\le3$. Il numero di clausole può essere qualunque, mentre l'union bound vale solo per $m<2^k=1024$.

Domande d'esame

1. Dimostra che ogni grafo ha un taglio con almeno $|E|/2$ archi. Assegnazione casuale uniforme dei vertici; ogni arco è tagliato con probabilità $\frac12$; per la linearità la media è $\frac{|E|}2$ e un esito la raggiunge.
2. Una formula con $m$ clausole da $3$ letterali distinti: quante se ne soddisfano al minimo, e quando è soddisfacibile? Almeno $\lceil\frac78m\rceil$; se $m<8$ è soddisfacibile perché il numero atteso di clausole insoddisfatte è $\frac m8<1$.
3. Dimostra che $R(k,k)>2^{k/2}$ per $k\ge3$. Colorazione casuale di $K_n$ con $n=\lfloor2^{k/2}\rfloor$: $E[\#\text{monocromatici}]=\binom nk2^{1-\binom k2}\le\frac{2^{k/2+1}}{k!}<1$, quindi esiste una colorazione senza $K_k$ monocromatici.
4. Come si derandomizza l'argomento del taglio? Si fissano i vertici in ordine; ognuno va dal lato che taglia più archi verso i già piazzati; l'attesa condizionale $(\text{tagliati})+\frac12(\text{indecisi})$ non scende mai, quindi il taglio finale è $\ge\frac{|E|}2$.