La entropía de Shannon de un dado justo

Question

La fórmula de la entropía de Shannon es la siguiente,

$$ \text {Entropy}(S) = - \sum_i p_i \log_2 p_i $$

Por lo tanto, un buen dado de seis caras debería tener la entropía,

$$- \sum_ {i=1}^6 \dfrac {1}{6} \log_2 \dfrac {1}{6} = \log_2 (6) = 2.5849...$$

Sin embargo, la entropía también debe corresponder al número medio de preguntas que hay que hacer para conocer el resultado (como se examina en esta guía bajo el título Teoría de la Información ).

Ahora, tratando de construir un árbol de decisiones para describir el número promedio de preguntas que tenemos que hacer para saber el resultado de un dado, y este parece ser el óptimo:

Si se observa el promedio de preguntas de la imagen, hay 3 preguntas en 4/6 casos en 2 preguntas en 2/6 casos. Por lo tanto, la entropía debería ser:

$$ \dfrac {4}{6} \times 3 + \dfrac {2}{6} \times 2 = 2.6666...$$

Así que, obviamente el resultado de la entropía no es el mismo en los dos cálculos. ¿Cómo es eso?

Answer 1

Para recuperar la entropía, hay que considerar una secuencia de tirar los dados, y preguntar cuántas preguntas por rollo que necesitas en una estrategia óptima, en el límite de que el número de tiradas va al infinito. Nótese que cada pregunta puede cubrir todas las tiradas, por ejemplo para dos tiradas, podrías preguntar en algún momento: "¿Los resultados están en $\{16,21,22,23\}$ ?” (donde el primer dígito denota el primer lanzamiento, y el segundo dígito denota el segundo lanzamiento).

Soy demasiado perezoso para hacerlo por 36 posibilidades, por lo tanto aquí un ejemplo más simple: Considere un dado para el cual cada tirada da sólo uno de tres resultados con igual probabilidad. Entonces la entropía es aproximadamente $1.58496$ .

Para un lanzamiento, la estrategia óptima es simplemente preguntarse "¿fue $1$ ?" seguido de "¿fue $2$ ?", que en promedio da $5/3 = 1.66$ preguntas.

Para dos lanzamientos, una estrategia óptima sería preguntar primero "¿fue uno de $\{11,12,13,21\}$ ?” (donde el primer dígito da el resultado del primer lanzamiento, y el segundo dígito el resultado del segundo lanzamiento). Si la respuesta es "sí", entonces use dos preguntas para señalar uno de los cuatro resultados. De lo contrario, pregunte "¿fue el primer lanzamiento un $2$ ?", si es así, entonces fue uno de $22$ o $23$ y una pregunta es suficiente para determinar eso. En el caso restante sabes que el primer lanzamiento fue $3$ y no saber nada del segundo, así que empleas la estrategia de uno a uno para determinar el segundo lanzamiento.

Esta estrategia necesita en promedio $29/9=3.2222$ preguntas, o $1.61111$ preguntas por lanzamiento. Lo cual ya es mucho mejor, y de hecho sólo $1.65\,\%$ peor que el valor dado por la entropía.

Nótese que el número promedio de preguntas de la estrategia óptima de lanzamiento único puede diferir dramáticamente de la entropía. Para ello, considere el lanzamiento de una moneda sesgada. La entropía de esto puede hacerse arbitrariamente baja haciendo que la moneda esté suficientemente sesgada. Pero obviamente no hay manera de que puedas obtener el resultado del lanzamiento de una moneda con menos de una pregunta.

Answer 2

En su entorno, la entropía de Shannon es "sólo" un límite inferior para una entropía de cualquier árbol de decisión (incluyendo los óptimos). Estos no tienen que coincidir. Para acercarse a lo que es la entropía de Shannon, imagina un árbol de decisión óptimo que identifique los resultados de lanzar un dado $N$ veces con algunos grandes $N$ (asumiendo la independencia). Cuanto más grande $N$ es, la más pequeña (aunque no negativa) es la diferencia entre el "promedio" (es decir, dividido por $N$ ) de este árbol de decisión "compuesto" y la entropía Shannon de los dados. (Se asemeja a un fondo de codificación aritmética ).

Answer 3

Si tienes $1$ mueren, hay $6$ posibles resultados. Etiquételos de 0 a 5 y expréselos como un número binario. Esto toma $\lceil\log_2{6}\rceil = 3$ trozos. Siempre se puede determinar el dado 1 con 3 preguntas, sólo hay que preguntar sobre cada bit por turno.

Si tienes $10$ dados, entonces hay $6^{10}$ posibles resultados. Etiquétenlos de 0 a $6^{10}-1$ y se expresan como un número binario. Esto toma $\lceil\log_2{6^{10}}\rceil = \lceil10\log_2{6}\rceil = 26$ trozos. Siempre puedes determinar los 10 dados con 26 preguntas, sólo tienes que preguntar sobre cada bit en el turno. El promedio es de 26 preguntas / 10 dados = 2.6.

Si tienes $100$ dados, entonces hay $6^{100}$ posibles resultados. Etiquétenlos de 0 a $6^{100}-1$ y se expresan como un número binario. Esto toma $\lceil\log_2{6^{100}}\rceil = \lceil100\log_2{6}\rceil = 259$ trozos. Siempre puedes determinar los 100 dados con 259 preguntas, sólo pregunta por cada bit en el turno. El promedio es de 259 preguntas / 100 dados = 2.59.

Si tienes $1000$ dados, entonces hay $6^{1000}$ posibles resultados. Etiquétenlos de 0 a $6^{1000}-1$ y se expresan como un número binario. Esto toma $\lceil\log_2{6^{1000}}\rceil = \lceil1000\log_2{6}\rceil = 2585$ trozos. Siempre puedes determinar los 1000 dados con 2585 preguntas, sólo pregunta por cada bit en el turno. El promedio es de 2585 preguntas / 1000 dados = 2.585.

Cada orden de magnitud te da un dígito más, convergiendo hacia la entropía Shannon.

Por otra parte, con el árbol de decisiones en su ejemplo, no convergería hacia la división del espacio de resultados por la mitad con cada pregunta. La primera pregunta $d_1 \in \{1,2,3\}$ lo hace, pero luego hay desperdicio si tienes que hacer dos preguntas para determinar los 3 resultados restantes. La segunda pregunta (dando un sí a la primera), podría ser $d_1 = 1$ o $d_1 = 2$ y $d_2 \in \{1,2,3\}$ que divide el espacio de los resultados en la mitad para los múltiples dados. Ahora está obligado a hacer 3 preguntas para obtener el primer dado, pero ha obtenido información sobre los siguientes dados. La estrategia de enumerar y codificar los resultados como arriba es sólo una extensión de esta idea. No vale la pena para un número bajo de dados, pero sí para muchos.

Answer 4

No hay nada malo en lo que hiciste. En el libro "Elementos de la Teoría de la Información", hay una prueba de que el número promedio de preguntas necesarias se encuentra entre $H(X)$ y $H(X)+1$ que está de acuerdo con lo que hiciste . Así que, en términos de "preguntas", la entropía te da una precisión dentro de $1$ pregunta. El siguiente argumento es de "Elementos de la teoría de la información":

Prueba de que $H(X) \leq L < H(X) + 1$

Si $L$ es el número medio de preguntas (en el libro es lo que se denomina la longitud de descripción esperada), podría escribirse como $$L = \sum p_i l_i$$ con sujeción a las limitaciones que cada $l_i$ es un número entero, porque $l_i$ refleja el número de preguntas que se hacen para llegar a la respuesta de la $i^{th}$ resultado. Además, tienes $$\sum D ^{-l_i} \leq 1$$ donde $D$ es el tamaño de sus alfabetos. Además, el número óptimo de preguntas se puede encontrar minimizando el $D-$ distribución de probabilidad adic más cercana a la distribución de $X$ en la entropía relativa, es decir, encontrando la $D-$ adic $r$ donde $$r_i = \frac{D^{-l_i}}{\sum_j D^{-l_j}}$$ que minimiza $$L - H(X) = D(p \Vert r) - \log(\sum D^{-l_i}) \geq 0$$ La elección de las preguntas $l_i = \log_D \frac{1}{p_i}$ dará $L = H$ . Desde $\log_D \frac{1}{p_i}$ no es necesariamente un número entero, podrías $$l_i = \lceil \log_D \frac{1}{p_i} \rceil$$ . Usando La desigualdad de Kraft-McMillan puedes decir $$\sum D^{-\lceil \log_D \frac{1}{p_i} \rceil} \leq \sum D^{- \log \frac{1}{p_i}} = \sum p_i = 1$$ Ahora obtendrás que el óptimo $l_i$ están delimitadas entre $$\log_D \frac{1}{p_i} \leq l_i < \log_D \frac{1}{p_i} + 1$$ que te da

$$H(X) \leq L < H(X) + 1$$ Usted computó $L \simeq 2.666$ y $H(X) \simeq 2.58$