Résumé
L’entropie d’une distribution de probabilité sur un ensemble fini X est en gros le nombre moyen de questions oui/non qu’il faut poser pour déterminer quel élément de X a été choisi lorsqu’il a été choisi au hasard selon cette distribution. Par exemple, l’entropie de la distribution uniforme sur un ensemble de taille 1 024 est de 10, puisque chaque question permet de diviser le nombre de possibilités par 2. L’entropie permet d’estimer la taille de certains ensembles, puisque si l’on peut trouver une distribution de probabilité sur un ensemble X et montrer que son entropie est au moins égale à n, alors X doit avoir une taille au moins égale à 2n. Cela ne semble pas, à première vue, être une observation utile, puisque, si toute distribution sur X a une entropie d’au moins n, alors il en est de même pour la distribution uniforme. Cependant, il arrive parfois qu’il existe d’autres distributions pour lesquelles il est beaucoup plus facile d’obtenir des bornes inférieures pour leur entropie. J’ai donné plusieurs exemples d’applications surprenantes de l’entropie pour résoudre des problèmes combinatoires.
