Entropía de Shannon de 0.922, 3 valores distintos

Dada una cadena de valores $AAAAAAAABC$ , la entropía de Shannon en la base de registro  $2$ llega a $0.922$ . Por lo que entiendo, en la base  $2$ la entropía de Shannon redondeada es el número mínimo de bits en binario para representar uno solo de los valores.

Tomado de la introducción en esta página de Wikipedia:

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

Entonces, ¿cómo pueden representarse tres valores por un bit? $A$  podría ser  $1$ , $B$  podría ser  $0$ ; pero ¿cómo podrías representar a  $C$ ?

Gracias de antemano.

La entropía que ha calculado no es realmente para la cadena específica, sino para una fuente aleatoria de símbolos que genera $A$ con probabilidad  $\tfrac{8}{10}$ , y$B$y $C$con probabilidad $\tfrac1{10}$ cada uno, sin correlación entre símbolos sucesivos. La entropía calculada para esta distribución,$0.922$significa que no puede representar cadenas generadas a partir de esta distribución utilizando menos de$0.922$bits por carácter, en promedio.

Puede ser bastante difícil desarrollar un código que logre esta velocidad. ^* Por ejemplo, la codificación Huffman asignaría los códigos $0$ , $10$ y  $11$ a $A$ , $B$ y  $C$ , respectivamente, para un promedio de $1.2$  bits por carácter. Eso está bastante lejos de la entropía, aunque sigue siendo mucho mejor que la ingenua codificación de dos bits por carácter. Cualquier intento de una mejor codificación probablemente explotar el hecho de que incluso una racha de diez consecutiva $A$ es más probable s (probabilidad $0.107$ ) que una sola  $B$ .

---

^* Resulta que no es difícil acercarse tanto como quieras: ¡mira las otras respuestas!

Aquí hay una codificación concreta que puede representar cada símbolo en menos de 1 bit en promedio:

Primero, divida la cadena de entrada en pares de caracteres sucesivos (por ejemplo, AAAAAAAABC se convierte en AA | AA | AA | AA | BC). Luego codifique AA como 0, AB como 100, AC como 101, BA como 110, CA como 1110, BB como 111100, BC como 111101, CB como 111110, CC como 111111. _{No he dicho qué sucede si hay un extraño número de símbolos, pero puede codificar el último símbolo usando alguna codificación arbitraria, realmente no importa cuando la entrada es larga.}

Este es un código de Huffman para la distribución de pares de símbolos independientes, y corresponde a elegir $n = 2$ en la respuesta de Yuval. Mayores $n$ conducirían a códigos aún mejores (acercándose a la entropía de Shannon en el límite, como él mencionó).

El número promedio de bits por par de símbolos para la codificación anterior es

$$\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$$ es decir$1.92/2 = 0.96$bits por símbolo, no muy lejos de la entropía de Shannon para una codificación tan simple.

Deje que $\mathcal{D}$ sea la siguiente distribución sobre $\{A,B,C\}$ : si $X \sim \mathcal{D}$ entonces $\Pr[X=A] = 4/5$ y $\Pr[X=B]=\Pr[X=C]=1/10$ .

Para cada $n$ podemos construir códigos de prefijo $C_n\colon \{A,B,C\}^n \to \{0,1\}^*$ tal que

$$\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}).$$

En palabras, si codificamos una gran cantidad de muestras independientes de $\mathcal{D}$ , entonces, en promedio, necesitamos $H(\mathcal{D}) \approx 0.922$ bits por muestra. Intuitivamente, la razón por la que podemos hacer con menos de un bit es que cada muestra individual es bastante probable que sea $A$ .

Este es el verdadero significado de la entropía, y muestra que calcular la "entropía" de una cadena $A^8BC$ es un ejercicio bastante inútil.