On se place dans le cadre de variables aléatoires à valeur dans un espace fini $\mathcal X$. Certains résultats sont valables dans des cadres plus généraux mais on ne s'en préoccupera pas. On note ici par $\log$ le logarithme en base 2.
Définition : L'entropie d'une variable $X$ est $H(X)=-\sum_{x \in \mathcal X} \mathbb P(X=x)\log\left(\mathbb P(X=x)\right)$
Comme propriétés élémentaires, on a les inégalités suivantes (grâce à la stricte concavité de $\log$):
$H(X) \leq \log\vert \mathcal X\vert$ avec égalité si et seulement si $X$ suit la loi uniforme sur $\mathcal X$.
$H((X_1,X_2)) \leq H(X_1)+H(X_2)$ avec égalité si et seulement si $X_1$ et $X_2$ sont indépendantes.
Par exemple, l'entropie d'une $\text{Ber}(p)$ est $h(p)=-p\log p -(1-p)\log(1-p)$ et celle d'une $\text{Bin}(n,p)$ est $nh(p)$.
Note : Théo nous a présenté un résultat préliminaire sur l'entropie des binomiales, mais n'a finalement pas eu le temps de nous présenter sa 3ème partie où il l'utilisait. Il s'agit de :
lemme : Pour $n$ entier et $q$ rationnel tel que $nq$ est entier, on a $$ \frac{2^{nh(q)}}{n+1} \leq \binom{n}{nq} \leq 2^{nh(q)}$$
Ici $\mathcal X$ est un grand alphabet, et on va récupérer un "texte", c'est-à-dire une suite de lettre $(X_i)_{1\leq i\leq n}$ avec $n$ grand. Ici, on suppose les $X_i$ i.i.d. L'objectif est d'encoder (en binaire) chaque symbole de $\mathcal X$ de sorte à garder un texte déchiffrable mais très compressé.
Formellement,
Un code est une fonction $c:\mathcal X \mapsto \bigcup_{k\in \mathbb N}\{0,1\}^k$.
Compresser le code signifie minimiser $\sum_{i=1}^{n} |c(X_i)|$, dans notre cadre i.i.d. (avec $n$ grand) cela revient à minimiser $\mathbb E(|c(X)|)$. Mais il y a la contrainte d'avoir un code déchiffrable pour tout texte.
Un code $c$ est uniquement déchiffrable lorsque $\forall x_1,\ldots,x_k,y_1,\ldots,y_l \in \mathcal X$, $c(x_1)\ldots c(x_k)=c(y_1)\ldots c(y_l)$ entraîne $k=l$ et $x_i=y_i\ \forall i$.
Comme il n'est pas toujours aisé de vérifier qu'un code est uniquement déchiffrable, on va en fait travailler avec la notion suivante :
Un code $c$ est prefix-free si $\forall x,y \in \mathcal X, c(x)$ est un préfixe de $c(y)$ entraîne $x=y$.
La propriété "être prefix-free" se vérifie simplement en énumérant les paires de lettres et comparant leur code, et elle entraîne la propriété "être uniquement déchiffrable". Notons qu'il y a cependant des codes uniqement déchiffrables qui ne sont pas prefix-free (par exemple, des codes suffix-free).
Le résultat suivant traduit cette propriété du code $c$ en une contrainte analytique sur $c$ :
Inégalité de Kraft : Si $c$ est uniquement déchiffrable alors $$\sum_{x\in \mathcal X} 2^{-|c(x)|} \leq 1$$ "Presque inversement", si on a $(\alpha_x)_{x\in\mathcal X}$ des entiers positifs tels que $\sum_{x\in \mathcal X} 2^{-\alpha_x} \leq 1$ alors il existe un code prefix-free $c$ tel que $|c(x)|=\alpha_x\ \forall x\in \mathcal X$
C'est le résultat "réciproque" qui est le plus intéressant ici. Il se base sur un algorithme simple pour construire un code prefix-free à partir des $\alpha_x$ : On range les $x$ de sorte que $\alpha_{x_1}\leq \ldots \leq \alpha_{x_K}$ et on considère l'abre binaire infini (qui représente l'ensemble des codes possibles), qu'on va colorier au fur et à mesure. À l'étape $k$, on choisit un sommet parmi ceux à hauteur $\alpha_{x_k}$ parmi ceux qui n'ont pas été coloriés, puis on le colorie lui et tout ses enfants, ce qui permet d'éviter les préfixes. La condition $\sum_{x\in \mathcal X} 2^{-\alpha_x} \leq 1$ garantit qu'on trouve à chaque étape un sommet non-colorié.
Une conséquence de ce résultat est que l'entropie quantifie la "meilleure compression qui reste déchiffrable" :
Théorème : D'une part, pour tout code $c$ uniquement déchiffrable, on a $$\mathbb E(|c(X)|) \geq H(X)$$ et d'autre part il existe un code $\tilde c$ uniquement déchiffrable tel que $$\mathbb E(|\tilde c(X)|) \leq H(X)+1$$
Mitzenmacher;Upfal. Probability and computing (2017).
Brémaud. Discrete Probability Models and Methods (2017).