Disuguaglianza di Fano

Nella teoria dell'informazione, la Disuguaglianza di Fano mette in relazione l'equivocazione di un canale rumoroso con la probabilità d'errore nella decodifica di un simbolo ricevuto. È stata scoperta e dimostrata dallo scienziato Robert Fano.

Disuguaglianza di Fano

Se le variabili aleatorie $X=x_i$ e $Y=y_j$ rappresentano i simboli (estratti da un alfabeto di M possibili simboli) in ingresso ed in uscita ad un canale rumoroso ed hanno una densità di probabilità congiunta $P(x,y)$, il canale è affetto da una probabilità di errore

$P(e)=\sum _{i=0}^{M-1}\sum _{j=i}P(y_j,x_i)$

e la disuguaglianza di Fano si esprime allora come

$H(X|Y)\le H(e)+P(e)\log (M-1),$

in cui

$H(X|Y)=-\sum _{i,j}P(x_i,y_j)\log P(x_i|y_j)$

è l'entropia condizionata, detta equivocazione in quanto rappresenta la quantità d'informazione media persa nel canale; e

$H\left(e\right)=-P(e)\log P(e)-(1-P(e))\log (1-P(e))$

è l'entropia binaria corrispondente ad una sorgente binaria stazionaria e senza memoria che emette il simbolo 1 con probabilità $P(e)$ ed il simbolo 0 con probabilità $1-P(e)$.

La disuguaglianza di Fano fornisce quindi un limite inferiore alla probabilità d'errore; si mostra infatti che se l'entropia di X eccede la capacità del canale è impossibile che l'informazione trasmessa attraverso il canale sia ricevuta con probabilità d'errore arbitrariamente piccola.

Dimostrazione

Siano $X$ e $Y$ due variabili casuali e $\tilde{X}=f(Y)$ un estimatore di $X$ ottenuto dall'osservazione di $Y$. Sia $P(e)=P[X\ne \tilde{X}]$ la probabilità di errore.

Si consideri la variabile casuale binaria $E$ tale che:

$E=\{\begin{array}{cc}1& \text{se }X\ne \tilde{X}\\ 0& \text{se }X=\tilde{X}\end{array}$

che ha quindi una distribuzione del tipo $p_E=(1-P(e),P(e))$.

Si consideri ora l'entropia:

$H(X,E|Y)=H(X|Y)+H(E|X,Y)=H(E|Y)+H(X|E,Y)$

$E$ è funzione di $X$ e $\tilde{X}$ e di conseguenza di $X$ e $Y$, da cui $H(E|X,Y)=0$.
Si ottiene quindi

$H(X|Y)=H(E|Y)+H(X|E,Y)\le H(e)+H(X|E,Y)\text{ (1)}$

sfruttando la disuguaglianza $H(E|Y)\le H(E)=H(e)$.

A questo punto è possibile riscrivere $H(X|E,Y)$ come segue:

$H(X|E,Y)=p_E(0)H(X|Y,E=0)+p_E(1)H(X|Y,E=1)\text{ (2)}$

per il quale il primo termine del membro di destra si annulla perché dato $E=0$ l'incertezza sulla conoscenza di $X$ è nulla, mentre per il secondo, sapendo a priori di avere un errore, vale la disuguaglianza

$H(X|Y,E=1)\le \log (|𝒳|-1)$

dove $|𝒳|$ è il numero di valori possibili che la variabile $X$ può assumere. Sostituendo $\text{(2)}$ in $\text{(1)}$ si ottiene:

$H(X|Y)\le H(e)+p(e)\log (|𝒳|-1)$

dimostrando quindi l'asserto.

Bibliografia

• R. Fano, Transmission of information; a statistical theory of communications. Cambridge, Mass., M.I.T. Press, 1961.

Voci correlate

• Secondo teorema di Shannon
• Teoria dell'informazione
• Teoria dei codici