Entropia congiunta e condizionata e informazione mutua

L'entropia di una sola variabile (Entropia - informazione di un evento, disuguaglianza di Jensen e valore massimoL'informazione di un evento di probabilità $P$ è $i=\log_2\frac1P$ bit (zero per l'evento certo, additiva per eventi indipendenti). L'entropia di una variabile aleatoria discreta è l'informazione media, $H(x)=E[i_x(x)]=\sum_aP_x(a)\log_2\frac1{P_x(a)}$; vale $0\le H(x)\le\log_2M$ con $M$ cardinalità dell'alfabeto, e il massimo $\log_2M$ si raggiunge se e solo se i simboli sono equiprobabili (dimostrazione con la disuguaglianza di Jensen, perché il logaritmo è strettamente concavo).Entropia - informazione di un evento, disuguaglianza di Jensen e valore massimo →) non basta per un sistema di comunicazione: si vuole sapere quanta informazione sull'ingresso $x$ di un canale rimane nell'uscita $y$. Servono l'entropia di una coppia di variabili, quella di una variabile dato il valore dell'altra, e la loro differenza, l'informazione mutua.

Versione per Ing. Elettronica: Informazione ed entropiaL'informazione di un evento di probabilità $p$ è $\log_2\frac1p$ bit; l'entropia $H(x)=\sum p\log_2\frac1p$ è l'informazione media e misura l'incertezza della sorgente: $0\le H\le\log_2M$, con il massimo quando i simboli sono equiprobabili. Per più simboli: $H(x,y)\le H(x)+H(y)$ (uguaglianza se indipendenti), $H(x|y)=H(x,y)-H(y)$. Per una sorgente con $F_s$ simboli al secondo il rate di informazione è $F_sH_s$, il rate nominale $F_s\log_2M$ e l'efficienza $\eta=\frac{H_s}{\log_2M}$.Informazione ed entropia →. Versione per Ing. delle Telecomunicazioni: Informazione, entropia e informazione mutuaL'informazione di un evento di probabilità $P$ è $i=\log_2\frac1P$ bit; l'entropia $H(x)=\sum p\log_2\frac1p$ è l'informazione media e misura l'incertezza: $0\le H\le\log_2M$, massimo se i simboli sono equiprobabili. Per due variabili: $\max{H(x),H(y)}\le H(x,y)\le H(x)+H(y)$, $H(x|y)=H(x,y)-H(y)$ e l'informazione mutua $I(x;y)=H(x)-H(x|y)=H(x)+H(y)-H(x,y)\ge0$ (zero se e solo se indipendenti). Per una sorgente di $F_s$ simboli/s: rate di informazione $F_sH_s$, rate nominale $F_s\log_2M$, efficienza $\eta=\frac{H_s}{\log_2M}$.Informazione, entropia e informazione mutua →. Per la base di probabilità: Vettori aleatori discretiUn vettore aleatorio discreto (X, Y) è descritto dalla densità congiunta p(x, y) = P(X = x, Y = y); le marginali si ottengono sommando sull'altra variabile, X e Y sono indipendenti se p(x, y) = p_X(x) p_Y(y) per ogni coppia, e E[g(X, Y)] = Σ g(x, y) p(x, y).Vettori aleatori discreti →, 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 →.

Entropia congiunta

Per un vettore aleatorio discreto $\underline x=[x_1,\dots,x_N]$ la funzione informazione è $i_{\underline x}(\underline a)=\log_2\frac1{P_{\underline x}(\underline a)}$ e l'entropia è la sua media. Per una coppia $(x,y)$:

Definizione (entropia congiunta). $$H(x,y)=E\left[i_{x,y}(x,y)\right]=\sum_{a,b}P_{x,y}(a,b)\log_2\frac1{P_{x,y}(a,b)}.$$

È l'entropia della variabile aleatoria "coppia" $[x,y]$: la probabilità $P_{x,y}(a,b)=P[x=a,\,y=b]$ è la congiunta (Vettori aleatori discretiUn vettore aleatorio discreto (X, Y) è descritto dalla densità congiunta p(x, y) = P(X = x, Y = y); le marginali si ottengono sommando sull'altra variabile, X e Y sono indipendenti se p(x, y) = p_X(x) p_Y(y) per ogni coppia, e E[g(X, Y)] = Σ g(x, y) p(x, y).Vettori aleatori discreti →), e la formula è identica a quella di una variabile singola.

Una variabile è funzione deterministica dell'altra

Proprietà. Se $y=f(x)$ con $f$ funzione ordinaria (a ogni $a$ corrisponde un solo $b=f(a)$), allora $H(x,y)=H(x)$.

Perché. Le sole coppie con probabilità positiva sono $(a,f(a))$, e per queste $P_{x,y}(a,f(a))=P_x(a)$. Nella somma restano quindi solo quei termini: $$H(x,y)=\sum_aP_{x,y}(a,f(a))\log_2\frac1{P_{x,y}(a,f(a))}=\sum_aP_x(a)\log_2\frac1{P_x(a)}=H(x).$$ Conoscere $y$ quando si conosce $x$ non aggiunge incertezza. Il canale AWGN $r=s+w$ non è di questo tipo, perché $r$ dipende anche da $w$.

Esempio. $x\in\{0,1,2,3\}$ con probabilità $0{,}1;\ 0{,}2;\ 0{,}3;\ 0{,}4$ e $y=x^2\in\{0,1,4,9\}$. Le coppie $(0,0),(1,1),(2,4),(3,9)$ hanno le stesse probabilità, quindi $$H(x,y)=0{,}1\log_2\tfrac1{0{,}1}+0{,}2\log_2\tfrac1{0{,}2}+0{,}3\log_2\tfrac1{0{,}3}+0{,}4\log_2\tfrac1{0{,}4}=1{,}8464\ \text{bit}=H(x).$$ Al contrario $x$ non è funzione di $y$ se $x$ può valere anche $-2$ e $2$ ($x=\pm\sqrt y$): vedere $y=4$ lascia due valori possibili per $x$.

Variabili indipendenti

Proprietà. Se $x$ e $y$ sono indipendenti, $H(x,y)=H(x)+H(y)$.

Perché. Per indipendenza $P_{x,y}=P_xP_y$, quindi $i_{x,y}(x,y)=-\log_2\left[P_x(x)P_y(y)\right]=i_x(x)+i_y(y)$ e, per la linearità del valore atteso, $$H(x,y)=E\left[-\log_2P_x(x)\right]+E\left[-\log_2P_y(y)\right]=H(x)+H(y).$$

Variabili non indipendenti

Teorema. In generale $H(x,y)\le H(x)+H(y)$, con disuguaglianza stretta se $x$ e $y$ non sono indipendenti. Inoltre $$\boxed{\max\{H(x),H(y)\}\le H(x,y)\le H(x)+H(y)\le\log_2M_x+\log_2M_y,}$$ dove $M_x,M_y$ sono le cardinalità degli alfabeti.

Dimostrazione. Si studia la differenza $H(x,y)-H(x)-H(y)$ e si porta tutto in un solo valore atteso (considerando solo le coppie con $P_{x,y}>0$): $$H(x,y)-H(x)-H(y)=E\left[\log_2\frac1{P_{x,y}(x,y)}+\log_2P_x(x)+\log_2P_y(y)\right]=E\left[\log_2\frac{P_x(x)P_y(y)}{P_{x,y}(x,y)}\right].$$ Jensen (Entropia - informazione di un evento, disuguaglianza di Jensen e valore massimoL'informazione di un evento di probabilità $P$ è $i=\log_2\frac1P$ bit (zero per l'evento certo, additiva per eventi indipendenti). L'entropia di una variabile aleatoria discreta è l'informazione media, $H(x)=E[i_x(x)]=\sum_aP_x(a)\log_2\frac1{P_x(a)}$; vale $0\le H(x)\le\log_2M$ con $M$ cardinalità dell'alfabeto, e il massimo $\log_2M$ si raggiunge se e solo se i simboli sono equiprobabili (dimostrazione con la disuguaglianza di Jensen, perché il logaritmo è strettamente concavo).Entropia - informazione di un evento, disuguaglianza di Jensen e valore massimo →) dà $E[\log_2(\cdot)]\le\log_2E[\cdot]$, e il valore atteso del rapporto si calcola con la congiunta: $$E\left[\frac{P_x(x)P_y(y)}{P_{x,y}(x,y)}\right]=\sum_{a,b}\cancel{P_{x,y}(a,b)}\frac{P_x(a)P_y(b)}{\cancel{P_{x,y}(a,b)}}\le\sum_aP_x(a)\sum_bP_y(b)=1\cdot1,$$ quindi la differenza è $\le\log_21=0$. Il rapporto $\frac{P_xP_y}{P_{x,y}}$ è costante (e vale $1$) se e solo se $P_{x,y}=P_xP_y$ per tutte le coppie, cioè con indipendenza. Se esiste anche una sola coppia $(a,b)$ con $P_x(a)P_y(b)\ne P_{x,y}(a,b)$, il rapporto non è costante e Jensen è stretta. $\blacksquare$

Le altre disuguaglianze: $H(x,y)\ge\max\{H(x),H(y)\}$ perché la coppia ha almeno l'incertezza di ciascuna componente (si vedrà dalla regola della catena, con $H(y|x)\ge0$); l'ultima segue da $H\le\log_2M$.

Entropia condizionata

Se $x$ è condizionata a $y$ (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 →) la densità è $P_{x|y}(a|b)=P[x=a\mid y=b]=\frac{P_{x,y}(a,b)}{P_y(b)}$ e la funzione informazione condizionata è $i_{x|y}(a|b)=\log_2\frac1{P_{x|y}(a|b)}$.

Entropia di $x$ dato il valore $y=b$

Fissato $b$, $x$ ha densità $P_{x|y}(\cdot|b)$ e una sua entropia: $$H(x|y=b)=\sum_aP_{x|y}(a|b)\log_2\frac1{P_{x|y}(a|b)}.$$ Se $x$ e $y$ sono indipendenti $P_{x|y}=P_x$, quindi $H(x|y=b)=H(x)$ per ogni $b$.

Entropia condizionata $H(x|y)$

Definizione. $H(x|y)$ è la media di $H(x|y=b)$ sui valori di $y$: $$\boxed{H(x|y)=E_y\left[H(x|y=y)\right]=\sum_bP_y(b)\,H(x|y=b)=\sum_{a,b}P_{x,y}(a,b)\log_2\frac1{P_{x|y}(a|b)}.}$$

È l'incertezza che resta su $x$ dopo aver osservato $y$, in media. Il terzo passaggio usa $P_{x|y}(a|b)P_y(b)=P_{x,y}(a,b)$.

Regola della catena

Scrivendo $\frac1{P_{x|y}}=\frac{P_y}{P_{x,y}}$: $$H(x|y)=\sum_{a,b}P_{x,y}(a,b)\left[\log_2\frac1{P_{x,y}(a,b)}+\log_2P_y(b)\right]=H(x,y)-H(y),$$ perché nel secondo addendo $\sum_aP_{x,y}(a,b)=P_y(b)$ e quindi $\sum_bP_y(b)\log_2P_y(b)=-H(y)$. Per simmetria:

Regola della catena. $$\boxed{H(x,y)=H(x|y)+H(y)=H(y|x)+H(x).}$$

In parole: l'incertezza della coppia è quella di una variabile più quella che resta sull'altra una volta nota la prima. Da qui $H(x|y)\ge0$ implica $H(x,y)\ge H(y)$ e $H(x,y)\ge H(x)$, completando le disuguaglianze di sopra; e $H(x|y)=H(x)$ se e solo se $x$ e $y$ sono indipendenti.

Esempio completo. Il vettore $[x_1,x_2]$ binario ha $P(00)=0{,}1$, $P(01)=0{,}2$, $P(10)=0{,}3$, $P(11)=0{,}4$ (sommano a $1$).

1. Marginali: $H(x_1)=h(0{,}3)=0{,}8813$ bit, $H(x_2)=h(0{,}4)=0{,}9710$ bit.
2. Congiunta: $H(x_1,x_2)=1{,}8464$ bit (stessi numeri dell'esempio a quattro simboli). Si controlla $\max\{0{,}8813;\ 0{,}9710\}\le1{,}8464\le0{,}8813+0{,}9710=1{,}8523$: la congiunta è appena sotto la somma, perché $x_1$ e $x_2$ sono quasi indipendenti ($P(00)=0{,}1$ contro $P_{x_1}(0)P_{x_2}(0)=0{,}12$).
3. Condizionate ai valori: $P_{x_1|x_2}(\cdot|0)=\left(\frac{0{,}1}{0{,}4},\frac{0{,}3}{0{,}4}\right)=(0{,}25;\ 0{,}75)$, quindi $H(x_1|x_2=0)=h(0{,}25)=0{,}8113$ bit; $P_{x_1|x_2}(\cdot|1)=\left(\frac{0{,}2}{0{,}6},\frac{0{,}4}{0{,}6}\right)=\left(\frac13,\frac23\right)$, quindi $H(x_1|x_2=1)=0{,}9183$ bit.
4. Condizionata media: $H(x_1|x_2)=0{,}4\cdot0{,}8113+0{,}6\cdot0{,}9183=0{,}8755$ bit. Controllo con la catena: $H(x_1,x_2)-H(x_2)=1{,}8464-0{,}9710=0{,}8755$ ✓.

Informazione mutua

Definizione (informazione mutua). $$\boxed{I(x;y)=H(x)+H(y)-H(x,y)=H(x)-H(x|y)=H(y)-H(y|x)=I(y;x).}$$

Le tre espressioni coincidono per la regola della catena: $H(x)+H(y)-\left[H(x|y)+H(y)\right]=H(x)-H(x|y)$. Si legge così: $H(x)$ è l'incertezza su $x$ prima di osservare $y$, $H(x|y)$ quella dopo, e $I(x;y)$ è l'incertezza che l'osservazione di $y$ ha tolto, cioè l'informazione che $y$ porta su $x$ (e viceversa, è simmetrica). Equivalentemente $$H(x)=I(x;y)+H(x|y),\qquad H(y)=I(x;y)+H(y|x).$$

Valori che può assumere $I(x;y)$

• $I(x;y)\ge0$, perché $H(x)+H(y)\ge H(x,y)$.
• $I(x;y)\le\min\{H(x),H(y)\}$, perché $H(x|y)\ge0$ e $H(y|x)\ge0$ nelle due forme $I=H(x)-H(x|y)=H(y)-H(y|x)$.
• $I(x;y)=0$ se e solo se $x$ e $y$ sono indipendenti: l'osservazione di $y$ non dice nulla su $x$ ($H(x|y)=H(x)$).
• $I(x;y)=H(x)$ se $x$ è funzione deterministica di $y$ (per esempio $x=y$): $H(x|y)=0$, l'osservazione risolve ogni dubbio.

Esempio (canale con uscita costante). Un canale ha ingresso $x\in\{0,1\}$ con $P_x(0)=0{,}8$, $P_x(1)=0{,}2$, e l'uscita vale sempre $0$. Allora $y$ è deterministica, $H(y)=0$ e $H(x,y)=H(x)$ ($y$ è funzione di $x$). Si ha $I(x;y)=H(x)+0-H(x)=0=\min\{H(x),H(y)\}$: un canale che dà sempre la stessa uscita non trasporta informazione.

Esempio (canale binario con errore). $x$ uniforme su $\{0,1\}$, e $y=x$ con probabilità $0{,}9$, $y=1-x$ con probabilità $0{,}1$. Allora $P_{x,y}$ vale $0{,}45$ per le coppie uguali e $0{,}05$ per quelle diverse, e $y$ è uniforme. Si ha $H(x)=H(y)=1$ bit e $$H(x,y)=2\cdot0{,}45\log_2\tfrac1{0{,}45}+2\cdot0{,}05\log_2\tfrac1{0{,}05}=1{,}469\ \text{bit}=1+h(0{,}1),$$ $$I(x;y)=1+1-1{,}469=0{,}531\ \text{bit}=1-h(0{,}1).$$ È l'informazione che un canale binario simmetrico con errore $0{,}1$ lascia passare per ogni bit, quando l'ingresso è uniforme: la capacità di quel canale (Tasso d'informazione, capacità di canale e teorema di ShannonUna sorgente che emette un simbolo ogni $T$ secondi ha tasso d'informazione $R=\frac{H_s}T$ [bit/s] ($H_s$ entropia per simbolo); un canale ha tasso $R(g)=\frac{I_s(x;y)}T\le R(x)$. La capacità è il massimo del tasso del canale su tutte le statistiche d'ingresso, $C=\max_{p_x}\frac{I(x;y)}T$ per un canale senza memoria. Teorema di Shannon: se il tasso nominale della sorgente è $R\le C$ esiste un codice di canale con probabilità d'errore piccola a piacere, se $R>C$ no. Capacità: BSC $C=\frac1T[1-h(P_{bit})]$, canale a cancellazione $C=\frac{1-\alpha}T$, AWGN reale $C=\frac1{2T}\log_2\left(1+\frac{E_s}{\sigma^2}\right)$; canali in parallelo sommano le capacità.Tasso d'informazione, capacità di canale e teorema di Shannon →).

Esempio (perdita con una funzione non iniettiva). $x\in\{-1,0,1\}$ con probabilità $\frac14,\frac12,\frac14$ e $y=x^2\in\{0,1\}$ ($P_y(0)=\frac12$, $P_y(1)=\frac12$). Si ha $H(x)=1{,}5$ bit, $H(y)=1$ bit, $H(x,y)=H(x)=1{,}5$ bit ($y$ è funzione di $x$) e $H(x|y)=H(x,y)-H(y)=0{,}5$ bit: restano da distinguere $x=\pm1$ quando $y=1$. Quindi $I(x;y)=1{,}5-0{,}5=1=H(y)=\min\{H(x),H(y)\}$.

Errori comuni

• Scrivere $H(x,y)=H(x)+H(y)$ senza controllare l'indipendenza; in generale è solo un limite superiore.
• Confondere $H(x|y=b)$ (numero per ogni $b$) con $H(x|y)$ (la media pesata con $P_y(b)$).
• Mediare le entropie condizionate con le probabilità sbagliate: si pesano con $P_y(b)$ (la variabile condizionante), non con $P_x(a)$.
• Pensare che $H(x|y)\le H(y|x)$ oppure che siano uguali: sono in generale diverse, mentre $I(x;y)$ è simmetrica.
• Scrivere $H(x,y)=H(x)$ per una $y$ che dipende anche da un rumore: vale solo se $y$ è funzione deterministica di $x$.

Domande d'esame

1. Si dimostri che $H(x,y)\le H(x)+H(y)$ e si dica quando vale l'uguaglianza. $H(x,y)-H(x)-H(y)=E\left[\log_2\frac{P_xP_y}{P_{x,y}}\right]\le\log_2E\left[\frac{P_xP_y}{P_{x,y}}\right]=\log_2\left(\sum_aP_x\sum_bP_y\right)=0$ per Jensen; uguaglianza se e solo se $P_{x,y}=P_xP_y$ (indipendenza).
2. Si definisca l'informazione mutua e se ne indichino i valori estremi. $I(x;y)=H(x)-H(x|y)=H(y)-H(y|x)=H(x)+H(y)-H(x,y)$; $0\le I\le\min\{H(x),H(y)\}$; $I=0$ se e solo se $x,y$ indipendenti; $I=H(x)$ se $x$ è funzione deterministica di $y$.
3. Dato $y=x^2$ con $x\in\{0,1,2,3\}$ e probabilità $0{,}1;\ 0{,}2;\ 0{,}3;\ 0{,}4$, quanto vale $H(x,y)$? Poiché $y$ è funzione deterministica di $x$, $H(x,y)=H(x)=1{,}846$ bit.

Esercizi svolti

• Esercizio - entropia condizionata, Huffman per due sorgenti e informazione mutua (compito del 25 giugno 2024, es. 178): $H(x|y)$, $H(x)$ e $I(x;y)=0{,}039$ bit con densità dipendente da $y$.
• Esercizio - due sorgenti indipendenti, codice di Shannon, Huffman e informazione mutua con un prodotto (compito del 24 gennaio 2025, es. 189): informazione mutua tra $Y$ e $W=ZY$, entropia di $[X,Y,Z]$ e di $[Y,Z,W]$.
• Esercizio - codice di Elias, Huffman sulla coppia di sorgenti e informazione mutua (compito del 22 gennaio 2019, es. 92): coppia $[X,Y]$, $H(Y|X)$ e informazione mutua $0{,}67$ bit.
• Esercizio - Huffman, codice di Shannon, funzione deterministica di una sorgente e informazione mutua di un canale (secondo compitino del 9 gennaio 2026, es. 196): $H(z|s)=0$ per una funzione deterministica e informazione mutua di un canale a sei simboli.
• Esercizio - sensori di temperatura, codice di Huffman, porta seriale e informazione mutua (esercizi del corso, cap. 5, es. 56): entropia congiunta di due sensori e informazione mutua con $X_1=f(X_2)$.
• Esercizio - canale binario con rumore aleatorio, capacità e Huffman sulle triplette (secondo compitino dell'11 gennaio 2019, es. 90): confronto tra $H(Y|X)$, $H(Y)$ e $H(X,Y)$ senza nuovi calcoli.
• Esercizio - canale binario non simmetrico, informazione mutua, Huffman ed Elias sulle coppie e canale a cancellazione (compito del 10 febbraio 2021, es. 123): informazione mutua di un canale binario non simmetrico.
• Esercizio - densità congiunta discreta, marginali, condizionate e informazione (esercizi del corso, cap. 2, es. 7): tabella congiunta discreta, marginali e condizionate.