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}$

L'inégalité de Fano est fréquemment utilisée en statistique bayésienne pour montrer une borne inférieure sur l'erreur de l'estimateur d'un paramètre.

Par exemple, on considère une variable de Bernouilli ${\displaystyle Z\sim {\mathcal {B}}(\theta )}$ pour un paramètre ${\displaystyle \theta \in \{1/3,2/3\}}$, que l'on suppose choisi uniformément parmi ces deux valeurs (c'est la distribution à priori). On veut prouver que l'estimateur ${\displaystyle {\hat {\theta }}(Z)={\begin{cases}1/3\quad {\text{si }}Z=0\\2/3\quad {\text{si }}Z=1\end{cases}}}$ dont la probabilité d'erreur est de ${\displaystyle P_{e}=\mathbb {P(\theta \neq {\hat {\theta }})} =1/3}$ n'est pas améliorable.

On utilise pour cela l'inégalité de Fano, qui donne le résultat suivant ${\displaystyle H(\theta |{\hat {\theta }})\leq H(P_{e})+P_{e}\log 2}$. Or, en explicitant la loi de ${\displaystyle (\theta ,Z)}$ on obtient${\displaystyle H(\theta |{\hat {\theta }})\geq H(\theta |Z)=H(1/3)}$. Cela donne l'inégalité ${\displaystyle H(1/3)\leq H(P_{e})+P_{e}\log 2}$, qui est légèrement plus faible que le résultat attendu. Le résultat exact pourrait en fait être obtenu en utilisant une version plus forte de l'inégalité de Fano[1].