Linearità del valore atteso e variabili indicatrici

Il valore atteso di una variabile aleatoria discreta è $E[X]=\sum_x x\,P(X=x)$ (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 →, Variabili aleatorie discrete e densità discretaUna variabile aleatoria discreta è una funzione X da Ω in R che assume un insieme finito o numerabile di valori (l'alfabeto); la sua densità discreta p_X(x) = P(X = x) basta a calcolare la probabilità di ogni evento che riguarda X.Variabili aleatorie discrete e densità discreta →). Per l'analisi degli algoritmi randomizzati serve quasi solo una proprietà, la linearità, perché permette di calcolare il costo medio di un algoritmo senza conoscere la distribuzione del costo.

Linearità

Teorema (linearità). Per ogni coppia di variabili aleatorie $X,Y$ sullo stesso spazio di probabilità e ogni $a,b\in\mathbb R$ (con attese finite) $$E[aX+bY]=aE[X]+bE[Y].$$ Non serve nessuna ipotesi di indipendenza.

Dimostrazione (spazio discreto, $X(\omega),Y(\omega)$ funzioni sugli esiti $\omega$). Si può calcolare l'attesa sommando sugli esiti, $E[X]=\sum_\omega X(\omega)P(\omega)$ (ogni valore $x$ si raccoglie con la probabilità degli esiti che lo producono). Allora $$E[X+Y]=\sum_\omega (X(\omega)+Y(\omega))P(\omega)=\sum_\omega X(\omega)P(\omega)+\sum_\omega Y(\omega)P(\omega)=E[X]+E[Y].$$ La somma sugli esiti è additiva: nessun passaggio usa la probabilità congiunta di $X$ e $Y$. $\square$

Al contrario, $E[XY]=E[X]E[Y]$ richiede l'indipendenza (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 →, 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 →): è la distinzione da non confondere (si vede in Esercizio - massimo e minimo di due dadi, linearità senza indipendenza).

Variabile indicatrice. Per un evento $A$, $I_A=1$ se $A$ accade e $0$ altrimenti. Allora $E[I_A]=1\cdot P(A)+0\cdot(1-P(A))=P(A)$.

Metodo. Per contare quanti oggetti di un certo tipo compaiono in un esperimento casuale:

1. si scrive il conteggio come somma $X=I_1+\dots+I_m$ di indicatrici;
2. si calcola $P(A_k)$ per ciascuna, di solito facile perché riguarda un solo oggetto;
3. $E[X]=\sum_k P(A_k)$, anche se gli eventi sono dipendenti in modo complicato.

Esempio (binomiale). Il numero di teste in $n$ lanci di una moneta con probabilità $p$ è $X=\sum_k I_k$, dove $I_k$ indica "il lancio $k$ è testa". Segue $E[X]=np$ senza sommare $\sum_j j\binom nj p^j(1-p)^{n-j}$ (Bernoulli, binomiale e uniforme discretaBernoulli Be(p): un solo tentativo, vale 1 con probabilità p; binomiale Bin(n, p): numero di successi in n prove indipendenti, P(X = k) = C(n,k) p^k (1−p)^(n−k), media np e varianza np(1−p); uniforme discreta: n valori equiprobabili.Bernoulli, binomiale e uniforme discreta →).

Esempio (grafo casuale). In un grafo su $n$ vertici in cui ogni arco è presente con probabilità $p$, il numero atteso di archi è $\binom n2 p$. Ogni terna di vertici è un triangolo con probabilità $p^3$, quindi i triangoli attesi sono $\binom n3 p^3$ (Esercizio - triangoli, vertici isolati e cricche in un grafo casuale).

Esempio (inversioni). Un'inversione di una sequenza è una coppia di posizioni $i<j$ con $a_i>a_j$. In una permutazione uniforme l'ordine relativo di due elementi è uniforme, quindi ogni coppia è un'inversione con probabilità $\frac12$ e le inversioni attese sono $\binom n2\cdot\frac12=\frac{n(n-1)}4$. Poiché l'insertion sort fa un confronto per ogni inversione (più al più uno per iterazione), il suo costo medio è $\Theta(n^2)$ (Esercizio - inversioni di una permutazione casuale e confronti dell'insertion sort).

Primo successo: la variabile geometrica

Si ripetono prove indipendenti, ciascuna con successo di probabilità $p$; sia $T$ il numero della prova del primo successo (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 →). Si calcola $E[T]$ condizionando sulla prima prova: con probabilità $p$ è finita (costo $1$); con probabilità $1-p$ si è speso $1$ e il processo ricomincia da capo (la situazione è identica, per l'indipendenza): $$E[T]=p\cdot1+(1-p)\,(1+E[T])\;\Longrightarrow\; pE[T]=1\;\Longrightarrow\;E[T]=\frac1p.$$ (Equivale a $\sum_{k\ge1}P(T\ge k)=\sum_{k\ge1}(1-p)^{k-1}=\frac1p$.) Esempio: per ottenere un $6$ con un dado servono in media $6$ lanci.

Algoritmo Las Vegas tipico. Se un tentativo riesce con probabilità $p$ e costa $c$, il costo atteso fino al successo è $c/p$ (vedi Algoritmi randomizzati - Monte Carlo, Las Vegas e amplificazioneUn algoritmo randomizzato usa bit casuali indipendenti; la probabilità è sulle scelte dell'algoritmo, mai sull'input (garanzia per ogni input). Las Vegas: sempre corretto, tempo aleatorio (conta il tempo atteso). Monte Carlo: tempo fisso, risposta sbagliata con probabilità limitata; errore unilaterale (RP: accetta solo se x sta nel linguaggio, accetta con prob almeno 1/2) o bilaterale (BPP: giusto con prob almeno 2/3). ZPP = RP ∩ co-RP = Las Vegas con tempo atteso polinomiale. Amplificazione: unilaterale, k ripetizioni indipendenti, errore (1-p)^k ≤ e^(-pk), serve k ≥ ln(1/ε)/p; bilaterale, voto di maggioranza su k esecuzioni, errore binomiale esatto, esponenziale in k (Chernoff, e^(-k/18) per p=2/3) mentre Chebyshev dà solo 8/k. Las Vegas -> Monte Carlo: interrompere a c volte il tempo atteso (Markov, errore ≤ 1/c). Monte Carlo -> Las Vegas: solo se la risposta si verifica in fretta. Esempio: Miller-Rabin, errore ≤ 1/4 per esecuzione.Algoritmi randomizzati - Monte Carlo, Las Vegas e amplificazione →).

Numeri armonici

Compaiono in quasi ogni analisi. $H_n=1+\tfrac12+\dots+\tfrac1n$ (Serie notevoli - geometrica, telescopica, armonicaLe serie di cui si conosce il carattere e da usare come termine di paragone: geometrica (converge a 1/(1-q) se |q|<1), telescopiche (somma b_1 - lim b_n, come Mengoli), armonica generalizzata (1/n^alpha converge se e solo se alpha>1).Serie notevoli - geometrica, telescopica, armonica →).

Proprietà. $\ln(n+1)\le H_n\le 1+\ln n$; più finemente $H_n=\ln n+\gamma+\tfrac1{2n}-\tfrac1{12n^2}+\dots$, con $\gamma\approx0{,}5772$.

Dimostrazione dei limiti. Poiché $1/x$ è decrescente, $\frac1k\ge\int_k^{k+1}\frac{dx}x$, e sommando per $k=1..n$ si ottiene $H_n\ge\ln(n+1)$. Per $k\ge2$ vale $\frac1k\le\int_{k-1}^k\frac{dx}x$: sommando per $k=2..n$ si ha $H_n-1\le\ln n$. $\square$

Esempio. $H_{10}=\frac{7381}{2520}\approx2{,}929$; la formula fine dà $\ln10+0{,}5772+\frac1{20}=2{,}3026+0{,}5772+0{,}05=2{,}930$.

Collezionista di figurine

Un album ha $n$ figurine distinte; ogni acquisto ne dà una uniforme tra le $n$, indipendentemente. Quanti acquisti $T$ servono per averle tutte?

Teorema. $E[T]=nH_n\approx n\ln n+\gamma n$.

Dimostrazione. Sia $T_i$ il numero di acquisti necessari per passare da $i-1$ figurine distinte alla $i$-esima distinta ($T=\sum_i T_i$). Quando se ne hanno $i-1$, ogni acquisto è "nuovo" con probabilità $p_i=\frac{n-i+1}n$, quindi $T_i$ è geometrica di parametro $p_i$ e $E[T_i]=\frac n{n-i+1}$. Per linearità $$E[T]=\sum_{i=1}^n\frac n{n-i+1}=n\Big(\frac1n+\frac1{n-1}+\dots+1\Big)=nH_n.\ \square$$

Esempio. Un dado ($n=6$): $6H_6=6\cdot\frac{49}{20}=14{,}7$ lanci in media per veder uscire tutte le facce. Con $n=50$: $50H_{50}\approx224{,}96$. L'ultima figurina da sola costa in media $n$ acquisti (per $n=50$, $50$ su $225$): la coda è lunga. Quanto $T$ si discosta da $nH_n$ si studia con 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 →.

Punti fissi di una permutazione

Sia $\pi$ una permutazione uniforme di $\{1..n\}$ e $X$ il numero dei punti fissi ($\pi(k)=k$). Sia $I_k=1$ se $\pi(k)=k$. Allora $P(I_k=1)=\frac{(n-1)!}{n!}=\frac1n$ (le permutazioni con $k$ fisso sono $(n-1)!$) e $$E[X]=n\cdot\frac1n=1\qquad\text{per ogni }n.$$ Gli $I_k$ non sono indipendenti: se $n-1$ elementi sono fissi, lo è anche l'ultimo. La linearità non se ne accorge.

Esempio ($n=3$). Le sei permutazioni hanno $3,1,1,0,0,1$ punti fissi: totale $6$, media $6/6=1$. Si ottiene anche $E[X(X-1)]=\sum_{j\ne k}P(I_jI_k=1)=n(n-1)\frac1{n(n-1)}=1$, quindi $E[X^2]=2$ e $\mathrm{Var}(X)=2-1=1$ (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 →).

Record

Si scorre una sequenza di $n$ valori distinti in ordine casuale (ogni ordine con probabilità $1/n!$) e si conta quante volte il valore corrente supera tutti i precedenti: i record (le assegnazioni di un massimo corrente). Il valore in posizione $i$ è un record se è il massimo dei primi $i$; per simmetria il massimo di $i$ elementi è in ciascuna posizione con probabilità $1/i$. Quindi $$E[R]=\sum_{i=1}^n\frac1i=H_n\approx\ln n.$$ Esempio. $n=3$: i record sono $3,2,2,2,1,1$ sulle sei permutazioni, media $\frac{11}6=H_3$. Per $n=1000$ il massimo corrente viene aggiornato solo $\approx7{,}49$ volte.

import random, math
n, T = 1000, 4000
tot = 0
for _ in range(T):
    p = random.sample(range(n), n); m = -1
    for x in p:
        if x > m: m = x; tot += 1
print(tot / T, sum(1 / k for k in range(1, n + 1)))   # circa 7.49 in entrambi i casi

Valore atteso condizionato e probabilità totale

Definizione. Se $P(A)>0$, $E[X\mid A]=\frac{E[X\,I_A]}{P(A)}=\sum_x x\,P(X=x\mid A)$ (Probabilità condizionataLa probabilità di A sapendo che si è verificato B è P(A ∣ B) = P(A ∩ B) / P(B), con P(B) > 0; è una nuova misura di probabilità, e da essa seguono la regola del prodotto e la regola della catena.Probabilità condizionata →).

Teorema (probabilità totale per l'attesa). Se $A_1,\dots,A_m$ è una partizione dello spazio con $P(A_i)>0$, $$E[X]=\sum_i E[X\mid A_i]\,P(A_i).$$

Segue da $X=\sum_i X I_{A_i}$ e dalla linearità (Formula delle probabilità totali e formula di BayesSe (A_i) è una partizione di Ω, P(B) = Σ P(B ∣ A_i) P(A_i) (probabilità totali); la formula di Bayes inverte il condizionamento: P(A_k ∣ B) = P(B ∣ A_k) P(A_k) / P(B).Formula delle probabilità totali e formula di Bayes →). È lo strumento per le ricorrenze ("si condiziona sul primo passo"), come già per la geometrica. Condizionare su un evento che riguarda tutta la sequenza può cambiare la distribuzione in modo controintuitivo: lanciando un dado fino al primo $6$, sapendo che tutti i lanci sono pari, il numero atteso di lanci è $\frac32$ e non $3$ (Esercizio - Dado lanciato fino al primo sei con tutti i lanci pari (lezioni MIT)).

Esempio (due teste consecutive). Quanti lanci servono in media per vedere $HH$ con una moneta equa? Sia $E_0$ l'attesa a partire da "nessuna testa in fila" ed $E_1$ da "ultima uscita testa". Condizionando sul lancio successivo:

• $E_0=1+\frac12E_1+\frac12E_0$, da cui $E_0=2+E_1$;
• $E_1=1+\frac12\cdot0+\frac12E_0$ (con $H$ si finisce, con $T$ si torna a $E_0$), da cui $E_1=1+\frac{E_0}2$.

Sostituendo: $E_0=3+\frac{E_0}2$, quindi $E_0=6$. Per $HT$ la prima equazione è la stessa, $E_0'=2+E_1'$, ma da "ultima uscita testa" un'altra $H$ lascia nello stesso stato: $E_1'=1+\frac12\cdot0+\frac12E_1'$, cioè $E_1'=2$ e l'attesa è $E_0'=4$. Dopo una $H$ non seguita da $T$ si resta in $H$, non si perde il progresso (Esercizio - tempo atteso per vedere HH, HT e HHH nei lanci di una moneta).

Somme di un numero aleatorio di termini

Teorema (identità di Wald). Siano $X_1,X_2,\dots$ con la stessa media $\mu$ e $N$ un numero aleatorio di termini a valori interi non negativi, con $E[N]<\infty$. Se per ogni $i$ l'evento $\{N\ge i\}$ è indipendente da $X_i$ (vale se $N$ è indipendente dagli $X_i$, oppure se $N$ è un tempo d'arresto: la decisione di fermarsi dopo $i-1$ termini dipende solo da $X_1..X_{i-1}$), allora per $S_N=X_1+\dots+X_N$ $$E[S_N]=\mu\,E[N].$$

Dimostrazione. $S_N=\sum_{i\ge1}X_i I_{\{N\ge i\}}$. Per l'indipendenza $E[X_iI_{\{N\ge i\}}]=\mu\,P(N\ge i)$, e $\sum_{i\ge1}P(N\ge i)=E[N]$ (formula delle code). Lo scambio tra somma e attesa è lecito per termini non negativi, e per il caso generale con $E|X_i|$ limitate. $\square$

Esempio 1 ($N$ indipendente). Si lancia un dado per scegliere $N$ uniforme in $\{1..6\}$, poi si lanciano $N$ dadi e si somma: $E[S]=E[N]\cdot3{,}5=3{,}5\cdot3{,}5=12{,}25$.

Esempio 2 (tempo d'arresto). Si lancia un dado finché non esce $6$ (incluso) e si somma tutto. $N$ è geometrica di parametro $\frac16$, $E[N]=6$, e $\{N\ge i\}$ dipende solo dai primi $i-1$ lanci: $E[S]=6\cdot3{,}5=21$. Verifica diretta: i lanci prima del $6$ sono $5$ in media, ciascuno uniforme in $\{1..5\}$ (media $3$), più il $6$ finale: $5\cdot3+6=21$.

Domande d'esame

1. Dimostra che $E[X+Y]=E[X]+E[Y]$ senza indipendenza. Si somma sugli esiti: $\sum_\omega(X+Y)(\omega)P(\omega)$ si spezza in due somme, nessuna probabilità congiunta compare.
2. $n$ persone riprendono a caso il cappotto: quante in media ritrovano il proprio? $X=\sum_kI_k$ con $P(I_k=1)=\frac1n$: $E[X]=1$ per ogni $n$, anche se gli $I_k$ sono dipendenti.
3. Tempo medio per vedere tutte le facce di un dado? Collezionista con $n=6$: $6H_6=14{,}7$ lanci (somma di geometriche di medie $1,\frac65,\frac32,2,3,6$).
4. Dimostra $E[T]=1/p$ per la geometrica condizionando sulla prima prova: $E[T]=p+(1-p)(1+E[T])$.