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)\le H(P_e)+P_e\log r$

où $P_e=\mathbb{P}(X\ne 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)-\underset{0}{\underbrace{H(E|XY)}}=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)\le 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)\le H(P_e)+P_e\log r$

Interprétation en statistique

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 $Z\sim ℬ(\theta )$ pour un paramètre $\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 $\hat{\theta }(Z)=\{\begin{array}{c}1/3\text{si }Z=0\\ 2/3\text{si }Z=1\end{array}$ dont la probabilité d'erreur est de $P_e=\mathbb{P}\mathbb{(}\mathbb{\theta }\mathbb{\ne }\hat{\mathbb{\theta }}\mathbb{)}=1/3$ n'est pas améliorable.

On utilise pour cela l'inégalité de Fano, qui donne le résultat suivant $H(\theta |\hat{\theta })\le H(P_e)+P_e\log 2$. Or, en explicitant la loi de $(\theta ,Z)$ on obtient$H(\theta |\hat{\theta })\ge H(\theta |Z)=H(1/3)$. Cela donne l'inégalité $H(1/3)\le 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.