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 ${\displaystyle X=x_{i}}$ e ${\displaystyle 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 ${\displaystyle P(x,y)}$, il canale è affetto da una probabilità di errore

${\displaystyle 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

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

in cui

${\displaystyle 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

${\displaystyle 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à ${\displaystyle P(e)}$ ed il simbolo 0 con probabilità ${\displaystyle 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 ${\displaystyle X}$ e ${\displaystyle Y}$ due variabili casuali e ${\displaystyle {\tilde {X}}=f(Y)}$ un estimatore di ${\displaystyle X}$ ottenuto dall'osservazione di ${\displaystyle Y}$. Sia ${\displaystyle P(e)=P[X\neq {\tilde {X}}]}$ la probabilità di errore.

Si consideri la variabile casuale binaria ${\displaystyle E}$ tale che:

${\displaystyle 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 ${\displaystyle p_{E}=(1-P(e),P(e))}$.

Si consideri ora l'entropia:

${\displaystyle H(X,E|Y)=H(X|Y)+H(E|X,Y)=H(E|Y)+H(X|E,Y)}$

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

${\displaystyle H(X|Y)=H(E|Y)+H(X|E,Y)\leq H(e)+H(X|E,Y)\ \ \ \ {\mbox{ (1)}}}$

sfruttando la disuguaglianza ${\displaystyle H(E|Y)\leq H(E)=H(e)}$.

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

${\displaystyle 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 ${\displaystyle E=0}$ l'incertezza sulla conoscenza di ${\displaystyle X}$ è nulla, mentre per il secondo, sapendo a priori di avere un errore, vale la disuguaglianza

${\displaystyle H(X|Y,E=1)\leq \log(|{\mathcal {X}}|-1)}$

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

${\displaystyle 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