Entropía de Shannon de 0.922, 3 valores distintos

14

Dada una cadena de valores UNUNUNUNUNUNUNUNsiC , 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? UN  podría ser  1 , si  podría ser  0 0 ; pero ¿cómo podrías representar a  C ?

Gracias de antemano.

Sean C
fuente

Respuestas:

16

La entropía que ha calculado no es realmente para la cadena específica, sino para una fuente aleatoria de símbolos que genera UN con probabilidad  810 , ysiCcon probabilidad 110 cada uno, sin correlación entre símbolos sucesivos. La entropía calculada para esta distribución,0.922significa que no puede representar cadenas generadas a partir de esta distribución utilizando menos de0.922bits 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 0 , 1011 a UN , siC , 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 UN es más probable s (probabilidad 0,107 ) que una sola  si .


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

David Richerby
fuente
18

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 norte=2 en la respuesta de Yuval. Mayores norte 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

8108101+38101103+1108104 4+4 41101106 6=1,92
es decir1,92/ /2=0,96bits por símbolo, no muy lejos de la entropía de Shannon para una codificación tan simple.

tipo nómada
fuente
13

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

Para cada n podemos construir códigos de prefijo Cn:{A,B,C}n{0,1} tal que

limnEX1,,XnD[Cn(X1,,Xn)]n=H(D).

En palabras, si codificamos una gran cantidad de muestras independientes de D , entonces, en promedio, necesitamos H(re)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 UN .

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

Yuval Filmus
fuente