Linearità del valore atteso e variabili indicatrici

In questa pagina 9

Il valore atteso di una variabile aleatoria discreta è $E[X]=\sum_x x\,P(X=x)$ (Valore atteso, 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 eventi, 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:

si scrive il conteggio come somma $X=I_1+\dots+I_m$ di indicatrici;
si calcola $P(A_k)$ per ciascuna, di solito facile perché riguarda un solo oggetto;
$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 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 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 amplificazione).

Numeri armonici

Compaiono in quasi ogni analisi. $H_n=1+\tfrac12+\dots+\tfrac1n$ (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 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 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.

python

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à 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 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

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.
$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.
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$ ).
Dimostra $E[T]=1/p$ per la geometrica condizionando sulla prima prova: $E[T]=p+(1-p)(1+E[T])$ .

Versione ripasso

Linearità: $E[aX+bY]=aE[X]+bE[Y]$ sempre, senza indipendenza (si somma sugli esiti: $E[X]=\sum_\omega X(\omega)P(\omega)$ , nessuna probabilità congiunta). Invece $E[XY]=E[X]E[Y]$ richiede indipendenza (Indipendenza di eventi, Covarianza e coefficiente di correlazione).
Indicatrice: $E[I_A]=P(A)$ . Metodo: conteggio $=\sum_kI_k$ , attesa $=\sum_kP(A_k)$ , anche con eventi dipendenti. Es.: $np$ per la binomiale (Bernoulli, binomiale e uniforme discreta), $\binom n3p^3$ triangoli di un grafo casuale, $\binom n2\cdot\frac12=\frac{n(n-1)}4$ inversioni di una permutazione uniforme (costo medio $\Theta(n^2)$ dell'insertion sort).
Geometrica: condizionando sulla prima prova $E[T]=p+(1-p)(1+E[T])\Rightarrow E[T]=1/p$ (Distribuzione geometrica); un dado: $6$ lanci per il primo $6$ . Un tentativo da costo $c$ e successo $p$ costa $c/p$ .
Armonici: $\ln(n+1)\le H_n\le1+\ln n$ (confronto di $\frac1k$ con $\int dx/x$ ), $H_n=\ln n+\gamma+\frac1{2n}-\dots$ , $\gamma\approx0{,}5772$ ; $H_{10}=\frac{7381}{2520}\approx2{,}929$ .
Collezionista: passando da $i-1$ a $i$ figurine distinte $T_i$ è geometrica di parametro $\frac{n-i+1}n$ , $E[T_i]=\frac n{n-i+1}$ , $E[T]=\sum_iE[T_i]=nH_n$ . Dado: $6H_6=14{,}7$ ; $n=50$ : $\approx224{,}96$ ; l'ultima figurina da sola costa $n$ .
Punti fissi: $P(I_k=1)=\frac{(n-1)!}{n!}=\frac1n$ , $E[X]=n\cdot\frac1n=1$ per ogni $n$ (indicatrici dipendenti). $E[X(X-1)]=n(n-1)\frac1{n(n-1)}=1$ , $E[X^2]=2$ , $\mathrm{Var}(X)=1$ . Per $n=3$ : $3,1,1,0,0,1$ punti fissi, media $1$ .
Record: il valore in posizione $i$ è il massimo dei primi $i$ con probabilità $\frac1i$ (simmetria), $E[R]=H_n$ ( $n=3$ : $\frac{11}6$ ; $n=1000$ : $\approx7{,}49$ aggiornamenti del massimo).
Attesa condizionata: $E[X\mid A]=E[XI_A]/P(A)$ ; $E[X]=\sum_iE[X\mid A_i]P(A_i)$ (Formula delle probabilità totali e formula di Bayes, Probabilità condizionata). Esempio: $HH$ in media $6$ lanci ( $E_0=2+E_1$ , $E_1=1+\frac{E_0}2$ , quindi $E_0=3+\frac{E_0}2$ ); $HT$ in media $4$ ( $E_1'=2$ ).
Wald: $E[S_N]=\mu E[N]$ se $\{N\ge i\}$ è indipendente da $X_i$ ( $N$ indipendente, oppure tempo d'arresto). Dimostrazione: $S_N=\sum_iX_iI_{\{N\ge i\}}$ , $E=\mu\sum_iP(N\ge i)=\mu E[N]$ . Dado fino al primo $6$ : $6\cdot3{,}5=21$ (diretto: $5\cdot3+6$ ); $N$ uniforme in $\{1..6\}$ : $3{,}5\cdot3{,}5=12{,}25$ .
Passaggi da saper riscrivere all'orale: (1) linearità sugli esiti; (2) $E[T]=1/p$ per condizionamento sulla prima prova; (3) $nH_n$ come somma di geometriche di medie $\frac n{n-i+1}$ ; (4) $H_n\le1+\ln n$ per confronto con l'integrale; (5) Wald con $S_N=\sum X_iI_{\{N\ge i\}}$ . Esempio numerico da ricordare: in un grafo con $n=10$ e $p=0{,}3$ ci sono in media $\binom{10}3p^3=120\cdot0{,}027=3{,}24$ triangoli.
Errori tipici: chiedere l'indipendenza per la linearità; applicare Wald quando $N$ dipende da $X_i$ (non solo dai precedenti); dimenticare il fattore $n$ in $nH_n$ ; confondere $E[X^2]$ con $E[X]^2$ .