Inégalité de Fano

Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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

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].

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