Inégalité de Fano

L'inégalité de Fano est un résultat de théorie de l'information.

Énoncé

Pour deux variables aléatoires $X$ et $Y$ prenant $r+1$ valeurs possibles, on a :

$H(X|Y)\leq H(P_{e})+P_{e}\log r$

où $P_{e}=\mathbb {P} (X\neq Y)$ est la probabilité d'erreur et $H(P_{e})$ est l'entropie de Shannon de la loi de Bernoulli de paramètre $P_{e}$.

Démonstration

Considérons $E=\delta _{XY}$ où $\delta$ est le symbole de Kronecker. $E$ suit une loi de Bernoulli de paramètre $1-P_{e}$. En appliquant deux fois la règle de la chaîne pour l'entropie conditionnelle, on a :

$H(X|Y)=H(XE|Y)-\underbrace {H(E|XY)} _{0}=H(E|Y)+H(X|EY)$

La donnée de $X,Y$ permet de calculer $E$ donc le terme $H(E|XY)$ est nul. On observe ensuite que $H(E|Y)\leq H(E)=H(P_{e})$. Le terme restant est décomposé selon la valeur de $E$ :

• Quand $E=0$, on majore simplement l'entropie $H((X|E=0)|Y)$ (entropie de la variable aléatoire $X|E=0$ conditionnellement à $Y$) par $\log r$, puisqu'il n'y a que $r$ valeurs disponibles pour $X$ une fois la valeur de $Y$ exclue ;
• Quand $E=1$, la donnée de $Y$ détermine $X$ dont l'entropie est nulle.

On a donc :

$H(X|Y)=H(E|Y)+H(X|EY)\leq H(P_{e})+P_{e}\log r$