Inégalité de Fano

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

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

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

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

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

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

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

On a donc :

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

• Portail de l’informatique
• Portail des probabilités et de la statistique