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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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