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.
Énoncé
[modifier | modifier le code]Pour deux variables aléatoires et prenant valeurs possibles, on a :
où est la probabilité d'erreur et est l'entropie de Shannon de la loi de Bernoulli de paramètre .
Démonstration
[modifier | modifier le code]Considérons où est le symbole de Kronecker. suit une loi de Bernoulli de paramètre . En appliquant deux fois la règle de la chaîne pour l'entropie conditionnelle, on a :
La donnée de permet de calculer donc le terme est nul. On observe ensuite que . Le terme restant est décomposé selon la valeur de :
- Quand , on majore simplement l'entropie (entropie de la variable aléatoire conditionnellement à ) par , puisqu'il n'y a que valeurs disponibles pour une fois la valeur de exclue ;
- Quand , la donnée de détermine dont l'entropie est nulle.
On a donc :
Interprétation en statistique
[modifier | modifier le code]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 pour un paramètre , que l'on suppose choisi uniformément parmi ces deux valeurs (c'est la distribution à priori). On veut prouver que l'estimateur dont la probabilité d'erreur est de n'est pas améliorable.
On utilise pour cela l'inégalité de Fano, qui donne le résultat suivant . Or, en explicitant la loi de on obtient. Cela donne l'inégalité , 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].
Notes et références
[modifier | modifier le code]- Cover, Thomas M. Verfasser, Elements of Information Theory (ISBN 978-1-118-58577-1 et 1-118-58577-1, OCLC 897591118, lire en ligne)
