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\not =i}P(y_{j},x_{i})$

e la disuguaglianza di Fano si esprime allora come

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

in cui

$H\left(X|Y\right)=-\sum _{i,j}P(x_{i},y_{j})\log P\left(x_{i}|y_{j}\right)$

è 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\neq {\tilde {X}}]$ la probabilità di errore.

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

$E={\begin{cases}1&{\mbox{se }}X\neq {\tilde {X}}\\0&{\mbox{se }}X={\tilde {X}}\end{cases}}$

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)\leq H(e)+H(X|E,Y)\ \ \ \ {\mbox{ (1)}}$

sfruttando la disuguaglianza $H(E|Y)\leq 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)\ \ \ \ {\mbox{ (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)\leq \log(|{\mathcal {X}}|-1)$

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

$H(X|Y)\leq H(e)+p(e)\log(|{\mathcal {X}}|-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