Momenti e deviazioni - Markov, Chebyshev e mediana randomizzata

Il valore atteso dice dove sta una variabile aleatoria, non quanto se ne allontana. Qui si usano il secondo momento e la varianza per limitare le code, cioè la probabilità di scostarsi dalla media, e si applicano a un algoritmo (la mediana). Prerequisiti: 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 →, 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 →, Varianza e momentiI momenti E[X^k] e i momenti centrati E[(X − μ)^k] descrivono la forma di una legge; la varianza Var(X) = E[(X − μ)²] = E[X²] − E[X]² misura quanto X si disperde attorno alla media, vale Var(aX + b) = a² Var(X) e Var(X) = 0 solo se X è costante.Varianza e momenti →, Indipendenza di eventiA e B sono indipendenti se P(A ∩ B) = P(A) P(B), cioè se sapere che uno si è verificato non cambia la probabilità dell'altro; l'indipendenza passa ai complementari, non va confusa con l'incompatibilità, e per più eventi va richiesta su ogni sottofamiglia.Indipendenza di eventi →. Il passo successivo, con code esponenziali, è 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 →.

Markov e Chebyshev con i numeri

Si richiamano soltanto gli enunciati; la dimostrazione è in Disuguaglianze di Markov, Chebyshev e JensenMarkov: per X ≥ 0, P(X ≥ a) ≤ E[X]/a; Chebyshev: P(|X − μ| ≥ ε) ≤ Var(X)/ε²; Jensen: per φ convessa, φ(E[X]) ≤ E[φ(X)]. Stimano probabilità e medie conoscendo solo media e varianza.Disuguaglianze di Markov, Chebyshev e Jensen →.

Markov. Se $X \ge 0$ e $a > 0$: $P(X \ge a) \le E[X]/a$. Chebyshev. Se $\mathrm{Var}(X)$ è finita e $a > 0$: $P(|X - E[X]| \ge a) \le \mathrm{Var}(X)/a^2$.

Chebyshev è Markov applicato alla variabile non negativa $(X - E[X])^2$ con soglia $a^2$. Il prezzo di usare solo i primi due momenti è che la coda decresce come $1/a^2$, non in modo esponenziale: nei limiti sotto lo si vede con i numeri. Se la variabile ha un minimo noto diverso da $0$, o si vuole la coda inferiore, Markov si applica alla variabile traslata o ribaltata: Esercizio - Markov traslato e ribaltato sui punteggi di un esame (lezioni MIT).

Varianza di una somma

Per $X = X_1 + \dots + X_n$ con medie finite:

$$\mathrm{Var}(X) = \sum_i \mathrm{Var}(X_i) + 2\sum_{i<j} \mathrm{Cov}(X_i, X_j), \qquad \mathrm{Cov}(X_i,X_j) = E[X_iX_j] - E[X_i]E[X_j].$$

Dimostrazione. $\mathrm{Var}(X) = E[(X - E[X])^2] = E\big[\big(\sum_i (X_i - E[X_i])\big)^2\big]$. Sviluppando il quadrato compaiono i termini $(X_i - E[X_i])^2$, di media $\mathrm{Var}(X_i)$, e per ogni coppia $i \neq j$ il prodotto $(X_i - E[X_i])(X_j - E[X_j])$, di media $\mathrm{Cov}(X_i,X_j)$; ogni coppia non ordinata compare due volte. $\blacksquare$ (La covarianza è trattata in Covarianza e coefficiente di correlazioneCov(X, Y) = E[(X − E X)(Y − E Y)] = E[XY] − E[X]E[Y] misura quanto X e Y variano insieme; è bilineare, Cov(X, X) = Var(X), Var(X + Y) = Var X + Var Y + 2Cov(X, Y); ρ = Cov / (σ_X σ_Y) sta in [−1, 1] e vale ±1 solo per legami lineari. Indipendenti ⇒ non correlate, ma non viceversa (tranne per i vettori gaussiani).Covarianza e coefficiente di correlazione →.)

Indipendenza a coppie. Le variabili $X_1,\dots,X_n$ sono indipendenti a coppie se ogni coppia $(X_i,X_j)$ con $i\neq j$ è indipendente. Allora $\mathrm{Cov}(X_i,X_j)=0$ e la varianza si somma: $\mathrm{Var}(X)=\sum_i \mathrm{Var}(X_i)$. È più debole dell'indipendenza di tutte insieme, e per Chebyshev basta.

Esempio (a coppie ma non insieme). $X_1, X_2$ bit uniformi indipendenti e $X_3 = X_1 \oplus X_2$ (somma modulo 2). Le quattro coppie di esiti $(X_1,X_2)$ danno $X_3$ = $0,1,1,0$. Ogni coppia, per esempio $(X_1,X_3)$, assume ciascuno dei 4 valori con probabilità $1/4$: indipendenza a coppie. Ma $P(X_1=X_2=X_3=1)=0\neq 1/8$: non sono indipendenti insieme.

Costruzione. Da $k$ bit uniformi indipendenti $Y_1,\dots,Y_k$ si ottengono $2^k - 1$ bit uniformi indipendenti a coppie: per ogni sottoinsieme non vuoto $S\subseteq\{1,\dots,k\}$, $X_S = \bigoplus_{i\in S} Y_i$. Se $S \neq S'$, un $i$ che sta in uno solo dei due (diciamo in $S$) cambia $X_S$ e non $X_{S'}$ quando si inverte $Y_i$: quindi $X_S$ è uniforme anche dato $X_{S'}$, e ogni coppia di valori ha probabilità $1/4$. Con $k=3$ si hanno 7 bit. Il loro numero di uni $N$ vale $0$ se $Y=000$ e $4$ negli altri 7 casi su 8 (fissato $Y\neq 000$, esattamente metà degli 8 sottoinsiemi $S$, vuoto compreso, dà $X_S=1$, e il vuoto dà sempre $0$), quindi $E[N]=\frac78\cdot 4=\frac72$, $E[N^2]=\frac78\cdot 16=14$ e $\mathrm{Var}(N)=14-\frac{49}{4}=\frac74$, come per sette bit davvero indipendenti ($7\cdot\frac14$). Chebyshev con soglia $E[N]$: $P(N=0)\le P(|N-\frac72|\ge\frac72)\le \frac{7/4}{(7/2)^2}=\frac17$, contro il valore vero $\frac18$. Si risparmiano bit casuali: servono $\log_2(n+1)$ bit per $n$ bit a coppie.

Chebyshev sul collezionista di figurine

Si sceglie a caso, con reinserimento, tra $n$ tipi. $T$ è il numero di estrazioni per averli tutti. Come in 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 →, $T = T_1 + \dots + T_n$, dove $T_i$ è il numero di estrazioni dopo il $(i-1)$-esimo tipo nuovo fino all'$i$-esimo. Le $T_i$ sono geometriche indipendenti (Distribuzione geometricaGeo(p) è il numero della prova in cui arriva il primo successo in prove indipendenti: P(X = n) = (1−p)^(n−1) p per n ≥ 1, P(X > n) = (1−p)^n (lunga attesa), media 1/p, varianza (1−p)/p², ed è senza memoria.Distribuzione geometrica →) di parametro $p_i = \frac{n - i + 1}{n}$ (i tipi ancora mancanti sono $n-i+1$). Sono indipendenti perché riguardano estrazioni disgiunte.

• $E[T_i] = 1/p_i$, quindi $E[T] = \sum_{k=1}^{n}\frac nk = nH_n$ (con $H_n = \sum_{k\le n} 1/k$).
• $\mathrm{Var}(T_i) = \frac{1 - p_i}{p_i^2} \le \frac{1}{p_i^2} = \frac{n^2}{(n-i+1)^2}$, e per l'indipendenza $$\mathrm{Var}(T) \le n^2 \sum_{k=1}^{n} \frac{1}{k^2} < n^2\,\frac{\pi^2}{6}.$$

Chebyshev con scostamento $cn$ ($c>0$): $$P(T \ge nH_n + cn) \le P(|T - E[T]| \ge cn) \le \frac{n^2\pi^2/6}{c^2n^2} = \frac{\pi^2}{6c^2}.$$

Numeri, $n = 50$. $E[T] = 50\,H_{50} = 224{,}96$; la varianza esatta è $3837{,}87$ (il limite $n^2\pi^2/6$ dà $4112{,}3$), deviazione standard $61{,}95$. Per $T \ge 375$, cioè scostamento $c\,n = 150$ da $E[T]$ ($c=3$): Chebyshev dà $\le 3837{,}87/150^2 = 0{,}171$. La probabilità esatta (programma dinamico sul numero di tipi già visti) è $0{,}0259$.

La stima è corretta ma lontana. La coda vera è esponenziale, come dice anche il union bound: dopo $t$ estrazioni il tipo $j$ manca con probabilità $(1-1/n)^t \le e^{-t/n}$, quindi $P(T > t) \le n e^{-t/n}$; per $n = 50$ e $t=374$ vale $50\cdot 0{,}98^{374} = 0{,}0262$, quasi l'esatto. Con soli due momenti non si va oltre $1/c^2$.

Metodo del secondo momento

Serve a dimostrare che una quantità non vale zero, cioè che un oggetto esiste.

Teorema. Se $X$ è a valori interi non negativi con $E[X] > 0$: $$P(X = 0) \le \frac{\mathrm{Var}(X)}{E[X]^2}, \qquad P(X > 0) \ge \frac{E[X]^2}{E[X^2]}.$$

Dimostrazione. Se $X = 0$ allora $|X - E[X]| = E[X]$, e Chebyshev dà $P(X=0) \le \mathrm{Var}(X)/E[X]^2$. Per la seconda: $E[X] = E[X\cdot \mathbf 1_{\{X>0\}}] \le \sqrt{E[X^2]\,P(X>0)}$ (Cauchy-Schwarz), e si eleva al quadrato. $\blacksquare$

Se $E[X]\to 0$ basta Markov: $P(X \ge 1)\le E[X]$. Se $\mathrm{Var}(X)/E[X]^2 \to 0$ allora $X>0$ con probabilità che tende a 1.

Esempio: triangoli in $G(n,p)$. Nel grafo casuale ogni arco compare con probabilità $p$, indipendenti. $X$ = numero di triangoli $=\sum_T I_T$ sui $\binom n3$ triangoli possibili; $E[I_T]=p^3$, quindi $E[X] = \binom n3 p^3$.

Varianza. $\mathrm{Var}(I_T) = p^3 - p^6$. Due triangoli distinti hanno in comune al più due vertici, quindi al più un arco. Se non condividono archi $I_T, I_{T'}$ sono indipendenti (covarianza 0). Se ne condividono uno, insieme usano $5$ archi: $\mathrm{Cov} = p^5 - p^3p^3 = p^5 - p^6$. Le coppie ordinate $(T,T')$ con un arco in comune sono $\binom n2 (n-2)(n-3)$ (arco comune, poi i due terzi vertici distinti). Quindi $$\mathrm{Var}(X) = \binom n3 (p^3 - p^6) + \binom n2 (n-2)(n-3)(p^5 - p^6).$$ Controllo per enumerazione di tutti i grafi: per $n=5,\,p=\frac12$ si ha $E[X]=\frac54$, $\mathrm{Var}(X)=\frac{65}{32}$; per $n=6,\,p=\frac13$, $\frac{20}{27}$ e $\frac{880}{729}$: coincidono.

Soglia. Per $n$ grande $\mathrm{Var}(X)/E[X]^2 \approx \frac{6}{(np)^3} + \frac{18}{n^2 p}$. Se $np \to \infty$ tende a $0$: ci sono triangoli con probabilità $\to 1$. Se $np\to 0$ allora $E[X]\to 0$ e per Markov non ce ne sono. Quindi la soglia è $p \approx 1/n$. Con $n=100$, $p=0{,}1$: $E[X]=161{,}7$, $\mathrm{Var}(X)/E[X]^2=0{,}022$, $P(X>0)\ge 0{,}978$. Con $p=0{,}02$: $E[X]=1{,}29$, rapporto $0{,}86$, $P(X>0) \ge 0{,}537$; la simulazione dà $P(X>0)\approx 0{,}70$ (il limite è corretto ma prudente).

Mediana con un algoritmo randomizzato

Trovare la mediana di $n$ numeri con ordinamento costa $\Theta(n\log n)$ (Algoritmi di ordinamentoSelection sort e insertion sort (quadratici, con invarianti), merge sort (divide et impera, Theta(n log n)), quick sort (caso pessimo quadratico, medio n log n), heap sort (in loco, Theta(n log n)), ordinamento senza confronti per chiavi intere in un intervallo piccolo, limite inferiore Omega(n log n) per gli algoritmi basati su confronti.Algoritmi di ordinamento →). L'idea del campionamento: un campione piccolo ordinato dà due elementi $d \le u$ che con alta probabilità racchiudono la mediana e lasciano in mezzo pochi elementi, che si ordinano da soli. Per semplicità $n$ dispari, elementi distinti, mediana di rango $k = (n+1)/2$.

Algoritmo (mediana per campionamento).

1. Si estraggono $m = \lceil n^{3/4}\rceil$ elementi con reinserimento e si ordinano, ottenendo $R$.
2. $d$ = elemento di $R$ di rango $m/2 - \sqrt n$, $u$ = elemento di rango $m/2 + \sqrt n$.
3. Con un solo passaggio sull'input si calcolano $\ell_d = \#\{x<d\}$, $\ell_u = \#\{x>u\}$ e $C = \{x: d\le x\le u\}$.
4. Se $\ell_d \ge k$ o $\ell_u \ge k$ (la mediana non è in $C$) oppure $|C| > 4m$, si ricomincia.
5. Si ordina $C$ e si restituisce l'elemento di rango $k - \ell_d$ in $C$.

import random, math

def mediana(a, rng=random):
    n = len(a); m = math.ceil(n ** 0.75); r = math.isqrt(n)
    k = (n + 1) // 2                                   # rango della mediana
    while True:
        R = sorted(rng.choice(a) for _ in range(m))    # campione con reinserimento
        d = R[max(0, m // 2 - r - 1)]
        u = R[min(m - 1, m // 2 + r)]
        sotto = sum(1 for x in a if x < d)
        sopra = sum(1 for x in a if x > u)
        C = [x for x in a if d <= x <= u]
        if sotto < k and sopra < k and len(C) <= 4 * m:
            C.sort()
            return C[k - sotto - 1]

Esempio piccolo. $a=\{0,\dots,10\}$ rimescolato ($n=11$): $k=6$, $m=\lceil 11^{3/4}\rceil = 7$, $\sqrt n\approx 3$. Un campione ordinato è $R=(1,2,4,5,5,8,9)$. I ranghi $m/2-\sqrt n\approx 0{,}2$ e $m/2+\sqrt n\approx 6{,}8$ si portano ai bordi, cioè $1$ e $7$: $d=1$, $u=9$. Allora $\ell_d=1$ (solo lo $0$), $\ell_u=1$ (solo il $10$), $C=\{1,\dots,9\}$ e $|C|=9\le 28$. Le condizioni $\ell_d=1<6$ e $\ell_u=1<6$ valgono, quindi si ordina $C$ e si prende il rango $k-\ell_d=5$: il quinto elemento di $C$ è $5$, la mediana. (Per $n$ piccolo $C$ è quasi tutto l'insieme: il vantaggio si vede solo per $n$ grande.)

Il risultato è sempre corretto (Las Vegas): la condizione al passo 4 garantisce che la mediana è in $C$ e il rango di $C$ si conosce. Resta da limitare il tempo, cioè la probabilità di dover ricominciare.

Teorema. Un giro dell'algoritmo fallisce con probabilità al più $n^{-1/4}$ (a meno di arrotondamenti di $\pm1$ nei ranghi). Il costo di un giro è $2n + O(n^{3/4}\log n)$ confronti, quindi il costo atteso totale è $2n + o(n)$.

Dimostrazione. Siano $x_{\mathrm{med}}$ la mediana e $m = n^{3/4}$. Il fallimento è l'unione di quattro eventi, ciascuno di probabilità $\le \frac{1}{4}n^{-1/4}$.

1. $E_1$: $d > x_{\mathrm{med}}$. Significa che meno di $m/2 - \sqrt n$ elementi del campione sono $\le x_{\mathrm{med}}$. Il numero $Y_1$ di campioni $\le x_{\mathrm{med}}$ è binomiale $\mathrm{Bin}(m, q)$ con $q = k/n \ge 1/2$, quindi $E[Y_1]\ge m/2$ e $\mathrm{Var}(Y_1) = mq(1-q)\le m/4$. Il fallimento richiede uno scostamento verso il basso di almeno $\sqrt n$: per Chebyshev $P(E_1)\le \frac{m/4}{n} = \frac{1}{4}n^{-1/4}$.
2. $E_2$: $u < x_{\mathrm{med}}$, simmetrico: stessa limitazione.
3. $E_3$: il rango di $u$ in $S$ supera $k + 2m$. Allora più di $m/2 - \sqrt n$ campioni hanno rango $\ge k+2m$. Il loro numero $Y_3\sim\mathrm{Bin}(m, q_3)$ con $q_3 \approx \frac12 - \frac{2m}{n} = \frac12 - 2n^{-1/4}$, quindi $E[Y_3] \approx m/2 - 2\sqrt n$ e l'evento richiede uno scostamento $\ge \sqrt n$ sopra la media. Chebyshev: $P(E_3)\le \frac{m/4}{n}$.
4. $E_4$: il rango di $d$ è sotto $k - 2m$: simmetrico.

Se nessuno dei quattro accade, la mediana è in $C$ (non $E_1,E_2$) e $|C| \le 4m$ (non $E_3,E_4$). Per l'unione, $P(\text{fallimento})\le n^{-1/4}$. Il numero di giri è geometrico, quindi in media meno di $1/(1-n^{-1/4})$. Il costo di un giro: ordinare $R$ costa $O(m\log m)$, i due confronti per elemento nel passo 3 costano $2n$, ordinare $C$ costa $O(m\log m)$. $\blacksquare$

Verifica numerica. Con $n = 10001$ ($m=\lceil 10001^{3/4}\rceil=1001$, $\sqrt n=100$), il limite teorico di fallimento è $n^{-1/4}=0{,}10$; in $3000$ prove non si è mai fallito e la mediana restituita è sempre quella giusta. Con $n=10^6+1$ ($m=31623$): 0 fallimenti su 100 (limite $0{,}032$). In media $|C|\approx 2000$ per $n=10001$: tra $d$ e $u$ ci sono $2\sqrt n=200$ posizioni del campione su $m\approx 1000$, cioè circa il $20\%$ dell'input. Il costo per $n=10001$ è quindi $2n=20002$ confronti per il passaggio sull'input più circa $m\log_2 m + |C|\log_2|C| \approx 10^4 + 2{,}2\cdot 10^4$ per i due ordinamenti: il termine $O(n^{3/4}\log n)$ diventa trascurabile rispetto a $2n$ solo per $n$ molto grande. Il limite di Chebyshev è prudente: la vera probabilità di fallire è molto più bassa, perché le code della binomiale sono esponenziali (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 →), e con quelle si può prendere un campione più piccolo.

Lo stesso schema (campione per scegliere un pivot buono) è alla base della selezione lineare di Analisi probabilistica di quicksort e quickselectCon pivot casuale due elementi di rango $i<j$ vengono confrontati con probabilità $2/(j-i+1)$; sommando sulle coppie il numero atteso di confronti di quicksort è esattamente $2(n+1)H_n-4n\approx2n\ln n-2{,}85,n$ (stessa formula dalla ricorrenza $C_n=n-1+\frac2n\sum_{k<n}C_k$). Quickselect trova il $k$-esimo elemento con attesa lineare, al più $4n$ confronti (mediana $\approx3{,}39,n$). Pivot fisso su input casuale equivale a pivot casuale su input qualunque.Analisi probabilistica di quicksort e quickselect →.

Domande d'esame

1. Dimostra che $\mathrm{Var}(\sum X_i)=\sum \mathrm{Var}(X_i)$ se le $X_i$ sono indipendenti a coppie. Nella formula della varianza di una somma ogni $\mathrm{Cov}(X_i,X_j)$ con $i\neq j$ è nulla perché $E[X_iX_j]=E[X_i]E[X_j]$ per due variabili indipendenti.
2. Varianza del numero di punti fissi di una permutazione casuale di $n\ge 2$ elementi. $X=\sum I_i$ con $E[I_i]=1/n$, $E[I_iI_j]=\frac{1}{n(n-1)}$ per $i\ne j$. Quindi $E[X]=1$, $E[X^2]=n\cdot\frac1n+n(n-1)\frac{1}{n(n-1)}=2$ e $\mathrm{Var}(X)=2-1=1$ (verificato per $n=6$ con tutte le $720$ permutazioni).
3. Dimostra che $P(X=0)\le \mathrm{Var}(X)/E[X]^2$. Se $X=0$ allora $|X-E[X]|=E[X]$, e si applica Chebyshev con soglia $E[X]$.
4. Nell'algoritmo della mediana, perché $m=n^{3/4}$ e scarto $\sqrt n$? La varianza del conteggio nel campione è $\le m/4$; con scarto $\sqrt n$ Chebyshev dà $\frac{m/4}{n}=\frac14 n^{-1/4}$, che tende a $0$. Il campione deve essere abbastanza grande per questo, ma abbastanza piccolo perché ordinarlo e ordinare $C$ (di circa $4m$ elementi) costi $o(n)$.