Esercizio - entropia condizionata, Huffman per due sorgenti e informazione mutua (compito del 25 giugno 2024, es. 178)

---

Teoria usata: Entropia congiunta e condizionata e informazione mutuaPer due variabili aleatorie discrete $x,y$ l'entropia congiunta è $H(x,y)=E\left[\log_2\frac1{P_{x,y}(x,y)}\right]$ e vale $\max{H(x),H(y)}\le H(x,y)\le H(x)+H(y)$, con l'uguaglianza a destra se e solo se $x$ e $y$ sono indipendenti e $H(x,y)=H(x)$ se $y=f(x)$. L'entropia condizionata $H(x|y)=E_y[H(x|y=y)]$ soddisfa la regola della catena $H(x,y)=H(x|y)+H(y)=H(y|x)+H(x)$. L'informazione mutua $I(x;y)=H(x)+H(y)-H(x,y)=H(x)-H(x|y)=H(y)-H(y|x)$ è simmetrica, $0\le I\le\min{H(x),H(y)}$, nulla per variabili indipendenti.Entropia congiunta e condizionata e informazione mutua → (punti 1, 2, 5), Codici di Shannon, Huffman ed Elias e codifica aritmeticaIl codice di Shannon(-Fano) assegna alla parola $i$ lunghezza $l_i=\lceil-\log_{M_y}p_i\rceil$, soddisfa Kraft-McMillan e ha $H\le L_y<H+1$; è ottimo solo se le probabilità sono potenze di $\frac1{M_y}$. Il codice ottimo (lunghezza media minima) dà parole più lunghe ai simboli meno probabili e ha almeno due parole di lunghezza massima che differiscono solo nell'ultimo simbolo: lo costruisce la procedura di Huffman, che unisce a ogni passo i due nodi meno probabili. Il codice di Elias prende le prime $l_i=\lceil-\log_2p_i\rceil+1$ cifre del punto medio dell'intervallo di ampiezza $p_i$ in $[0,1)$: è a prefisso ma subottimo ($H+1\le L_y<H+2$), e si adatta alla codifica aritmetica adattativa.Codici di Shannon, Huffman ed Elias e codifica aritmetica → (punti 3, 4, 6), Codici a prefisso - Kraft-McMillan e limiti di Shannon sulla lunghezza mediaLa codifica di sorgente senza perdite associa a ogni parola emessa dalla sorgente una parola di codice binaria (o $M_y$-aria) di lunghezza variabile, in modo invertibile; la qualità si misura con la lunghezza media $L_y=\sum p_{\underline x}(\underline a),l(\underline a)$. In un codice a prefisso nessuna parola è l'inizio di un'altra, quindi la decodifica è istantanea. Kraft-McMillan: ogni codice decodificabile ha $\sum M_y^{-l_i}\le1$, e se interi $l_i$ la soddisfano esiste un codice a prefisso con quelle lunghezze. Shannon: $\frac{H(\underline x)}{\log_2M_y}\le L_y<\frac{H(\underline x)}{\log_2M_y}+1$ per il codice a prefisso ottimo, con $L_y=\frac{H}{\log_2M_y}$ solo se le probabilità sono potenze di $\frac1{M_y}$.Codici a prefisso - Kraft-McMillan e limiti di Shannon sulla lunghezza media →, 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 → (punto 2). Un esercizio analogo su una densità congiunta discreta: Esercizio - densità congiunta discreta, marginali, condizionate e informazione (esercizi del corso, cap. 2, es. 7).

(1) Entropie condizionate ai valori di $y$

Fissato $y$, $x$ ha una densità condizionata e una sua entropia (Entropia congiunta e condizionata e informazione mutuaPer due variabili aleatorie discrete $x,y$ l'entropia congiunta è $H(x,y)=E\left[\log_2\frac1{P_{x,y}(x,y)}\right]$ e vale $\max{H(x),H(y)}\le H(x,y)\le H(x)+H(y)$, con l'uguaglianza a destra se e solo se $x$ e $y$ sono indipendenti e $H(x,y)=H(x)$ se $y=f(x)$. L'entropia condizionata $H(x|y)=E_y[H(x|y=y)]$ soddisfa la regola della catena $H(x,y)=H(x|y)+H(y)=H(y|x)+H(x)$. L'informazione mutua $I(x;y)=H(x)+H(y)-H(x,y)=H(x)-H(x|y)=H(y)-H(y|x)$ è simmetrica, $0\le I\le\min{H(x),H(y)}$, nulla per variabili indipendenti.Entropia congiunta e condizionata e informazione mutua →):

• $y=0$, probabilità $(0{,}1;\ 0{,}2;\ 0{,}3;\ 0{,}4)$: $$H(x|y=0)=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}=0{,}3322+0{,}4644+0{,}5211+0{,}5288=1{,}846\ \text{bit}.$$
• $y=1$, $4$ simboli equiprobabili: $$H(x|y=1)=\log_24=2\ \text{bit}\quad(\text{massimo per }4\text{ simboli}).$$

(2) Entropia di $x$

La densità di $x$ senza condizionare si ricava con la formula delle probabilità totali, pesando le due densità con $P(y=0)=0{,}6$ e $P(y=1)=0{,}4$: $$P(x=i)=0{,}6\,P(x=i|y=0)+0{,}4\,P(x=i|y=1),$$ $$P(x=1)=0{,}06+0{,}10=0{,}16,\quad P(x=2)=0{,}12+0{,}10=0{,}22,\quad P(x=3)=0{,}18+0{,}10=0{,}28,\quad P(x=4)=0{,}24+0{,}10=0{,}34$$ (somma $1$ ✓). L'entropia è $$H(x)=0{,}16\log_2\tfrac1{0{,}16}+0{,}22\log_2\tfrac1{0{,}22}+0{,}28\log_2\tfrac1{0{,}28}+0{,}34\log_2\tfrac1{0{,}34}=0{,}4230+0{,}4806+0{,}5142+0{,}5292=1{,}947\ \text{bit}.$$ È maggiore della media delle due entropie condizionate ($0{,}6\cdot1{,}846+0{,}4\cdot2=1{,}908$): la differenza è proprio l'informazione mutua (punto 5).

(3) Codici ottimi per $x$ dato $y$

• Per $y=0$: Huffman per $(0{,}1;0{,}2;0{,}3;0{,}4)$: si uniscono $0{,}1+0{,}2=0{,}3$, poi $0{,}3+0{,}3=0{,}6$, poi $0{,}6+0{,}4=1$. Codice: $x=4\to1$, $x=3\to01$, $x=2\to000$, $x=1\to001$ (lunghezze $1,2,3,3$ per i valori $0{,}4;0{,}3;0{,}2;0{,}1$). Lunghezza media (anche con i nodi interni $0{,}3+0{,}6+1$): $$L_0=0{,}4\cdot1+0{,}3\cdot2+0{,}2\cdot3+0{,}1\cdot3=0{,}4+0{,}6+0{,}6+0{,}3=1{,}9\ \text{bit}.$$
• Per $y=1$: i $4$ simboli equiprobabili si uniscono a coppie ($0{,}25+0{,}25=0{,}5$, poi $0{,}5+0{,}5=1$): codice a lunghezza fissa $x=1\to00$, $x=2\to01$, $x=3\to10$, $x=4\to11$ e $$L_1=2\ \text{bit}\ (=H(x|y=1)\text{: le probabilità sono potenze di }\tfrac12).$$

(4) Lunghezza media della parola completa

La parola trasmessa ha un bit per $y$ più la parola per $x$, con il codice scelto in base a $y$. Mediando sulle due possibilità: $$L=\sum_yP(y)\left[1+L_y\right]=0{,}6\,(1+1{,}9)+0{,}4\,(1+2)=0{,}6\cdot2{,}9+0{,}4\cdot3=1{,}74+1{,}2=2{,}94\ \text{bit}.$$ Equivalente: $L=1+0{,}6\cdot1{,}9+0{,}4\cdot2=1+1{,}14+0{,}8=2{,}94$.

(5) Informazione mutua $I(x;y)$

$$I(x;y)=H(x)-H(x|y),\qquad H(x|y)=\sum_yP(y)\,H(x|y)=0{,}6\cdot1{,}846+0{,}4\cdot2=1{,}1079+0{,}8=1{,}908\ \text{bit}.$$ $$I(x;y)=1{,}947-1{,}908=0{,}039\ \text{bit}.$$ Controllo con la formula simmetrica: $H(y)=h(0{,}6)=0{,}971$ bit, $H(x,y)=H(y)+H(x|y)=0{,}971+1{,}908=2{,}879$ bit, e $H(x)+H(y)-H(x,y)=1{,}947+0{,}971-2{,}879=0{,}039$ ✓. L'informazione mutua è piccola: le due densità di $x$ (a seconda di $y$) sono abbastanza vicine, quindi sapere $y$ dice poco su $x$.

Differenza con la soluzione del corso. La soluzione riporta $I(x;y)=1{,}947-1{,}598=0{,}05$ bit: il termine $1{,}598$ non coincide con $H(x|y)$ calcolato dalla stessa soluzione ($1{,}9$) e va corretto; il valore giusto è $1{,}947-1{,}908=0{,}039$ bit. (Si noti anche che con $1{,}598$ si avrebbe $0{,}349$, non $0{,}05$.)

(6) Un solo codice Huffman per le coppie $(x,y)$

Le coppie hanno probabilità $P(x,y)=P(y)P(x|y)$:

(somma $0{,}60+0{,}40=1$ ✓). Si indicano con $(x,y)$ le $8$ coppie. Huffman:

Un codice che ne risulta ha lunghezze $(1,0):4$, $(2,0):3$, $(3,0):3$, $(4,0):2$, $(1,1):4$, $(2,1):3$, $(3,1):3$, $(4,1):3$ (per esempio $1100,\ 011,\ 111,\ 10,\ 1101,\ 000,\ 001,\ 010$). Lunghezza media, con controllo dei nodi interni: $$L=0{,}06\cdot4+0{,}12\cdot3+0{,}18\cdot3+0{,}24\cdot2+0{,}10\cdot(4+3+3+3)=0{,}24+0{,}36+0{,}54+0{,}48+1{,}30=2{,}92\ \text{bit},$$ $$0{,}16+0{,}20+0{,}22+0{,}34+0{,}42+0{,}58+1=2{,}92\ \checkmark.$$ Il confronto con il punto 4 ($2{,}94$ bit): il codice congiunto è migliore di soli $0{,}02$ bit. La differenza viene dal bit di $y$, che nello schema separato costa sempre $1$ bit mentre $H(y)=0{,}971$ bit. Il limite inferiore per un codice delle coppie è $H(x,y)=2{,}879$ bit, e $2{,}879\le2{,}92<3{,}879$ ✓; il codice separato ($2{,}94$) è anch'esso entro il limite ma più lontano.

(Verificato con Python: $H(x|y=0)=1{,}84644$, $H(x|y=1)=2$, $H(x)=1{,}94698$, $L_0=1{,}9$, $L_1=2$, $L=2{,}94$, $I=0{,}03912$, Huffman delle $8$ coppie $L=2{,}92$ con somma dei nodi uguale, $H(x,y)=2{,}87881$.)

Errori comuni

• Per il punto 2 usare la media delle due entropie condizionate invece di calcolare la densità marginale di $x$: $H(x)\ne\sum_yP(y)H(x|y)$.
• Al punto 4 dimenticare il bit che identifica $y$ (la parola è $1+L_y$).
• Al punto 5 scrivere $H(x|y)=H(x|y=0)$ o $H(x|y=1)$: serve la media pesata con $P(y)$.
• Pensare che il codice congiunto sia sempre molto migliore: qui $2{,}92$ contro $2{,}94$, perché $H(y)$ è vicina a $1$ bit.
• Calcolare male le probabilità delle coppie: sono $P(y)P(x|y)$, non $P(x|y)$.