Entropie de Shannon de 0,922, 3 valeurs distinctes

Étant donné une chaîne de valeurs $AAAAAAAABC$ , l'entropie de Shannon dans la base de log  $2$ s'élève à $0.922$ . D'après ce que je comprends, dans la base  $2$ l'entropie de Shannon arrondie est le nombre minimum de bits en binaire pour représenter une seule des valeurs.

Tiré de l'introduction sur cette page wikipedia:

https://en.wikipedia.org/wiki/Entropy_%28information_theory%29

Alors, comment trois valeurs peuvent-elles être représentées par un bit? $A$  pourrait être  $1$ , $B$  pourrait être  $0$ ; mais comment pourriez-vous représenter  $C$ ?

Merci d'avance.

L'entropie que vous avez calculée n'est pas vraiment pour la chaîne spécifique, mais plutôt pour une source aléatoire de symboles qui génère $A$ avec une probabilité  $\tfrac{8}{10}$ , et$B$et $C$avec probabilité $\tfrac1{10}$ chacun, sans corrélation entre symboles successifs. L'entropie calculée pour cette distribution,$0.922$signifie que vous ne pouvez pas représenter les chaînes générées à partir de cette distribution en utilisant moins de$0.922$ bits par caractère, en moyenne.

Il pourrait être assez difficile de développer un code qui atteindra ce taux. ^* Par exemple, le codage Huffman attribuerait les codes $0$ , $10$ et  $11$ à $A$ , $B$ et  $C$ , respectivement, pour une moyenne de $1.2$  bits par caractère. C'est assez loin de l'entropie, bien que toujours beaucoup mieux que le codage naïf de deux bits par caractère. Toute tentative d'un meilleur codage exploitera probablement le fait que même une série de dix consécutifs $A$ s est plus probable (probabilité $0.107$ ) qu'un seul  $B$ .

---

^* Il s'avère qu'il n'est pas difficile de se rapprocher autant que vous le souhaitez - voir les autres réponses!

Voici un encodage concret qui peut représenter chaque symbole en moins de 1 bit en moyenne:

Tout d'abord, divisez la chaîne d'entrée en paires de caractères successifs (par exemple AAAAAAAABC devient AA | AA | AA | AA | BC). Ensuite, encodez AA comme 0, AB comme 100, AC comme 101, BA comme 110, CA comme 1110, BB comme 111100, BC comme 111101, CB comme 111110, CC comme 111111. _{Je n'ai pas dit ce qui se passe s'il y a un impair nombre de symboles, mais vous pouvez simplement encoder le dernier symbole en utilisant un encodage arbitraire, peu importe quand l'entrée est longue.}

Il s'agit d'un code de Huffman pour la distribution de paires indépendantes de symboles, et correspond au choix de $n = 2$ dans la réponse de Yuval. Plus grand $n$ conduirait à des codes encore meilleurs (approchant l'entropie de Shannon dans la limite, comme il l'a mentionné).

Le nombre moyen de bits par paire de symboles pour le codage ci-dessus est de

$$\frac{8}{10} \cdot \frac{8}{10} \cdot 1 + 3 \cdot \frac{8}{10} \cdot \frac{1}{10} \cdot 3 + \frac{1}{10} \cdot \frac{8}{10} \cdot 4 + 4 \cdot \frac{1}{10} \cdot \frac{1}{10} \cdot 6 = 1.92$$ $1.92/2 = 0.96$

$\mathcal{D}$$\{A,B,C\}$$X \sim \mathcal{D}$ then $\Pr[X=A] = 4/5$ and $\Pr[X=B]=\Pr[X=C]=1/10$.

For each $n$ we can construct prefix codes $C_n\colon \{A,B,C\}^n \to \{0,1\}^*$ such that

$$\lim_{n\to\infty} \frac{\operatorname*{\mathbb{E}}_{X_1,\ldots,X_n \sim \mathcal{D}}[C_n(X_1,\ldots,X_n)]}{n} = H(\mathcal{D}).$$

In words, if we encode a large number of independent samples from $\mathcal{D}$, then on average we need $H(\mathcal{D}) \approx 0.922$ bits per sample. Intuitively, the reason we can do with less than one bit is that each individual sample is quite likely to be $A$.

This is the real meaning of entropy, and it shows that computing the "entropy" of a string $A^8BC$ is a rather pointless exercise.