title: Disuguaglianza di Fano
text: # 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.
  
  