Tasa de entropía de una repetición finita

Question

Supongamos que generamos la siguiente secuencia eligiendo repetidamente una letra del alfabeto (26 letras):

LLL EEE HHH QQQ MMM QQQ OOO TTT EEE YYY XXX GGG...

Así, la primera letra de cada grupo de 3 letras se extrae de forma independiente con una probabilidad de $\frac{1}{26}$ y las dos siguientes son entonces deterministas e iguales a la letra extraída en la primera posición de cada grupo.

La entropía de cada primer símbolo de la secuencia me parece $\log26$ (utilizamos base 2) ya que necesitamos $\log26$ bits y $0$ las dos letras que le siguen, ya que no aportan ninguna información nueva y no necesito ninguna parte nueva.

Así, al añadir una nueva letra en la segunda secuencia (en el ejemplo, la letra "E"), necesitaría $2$ veces $\log26$ bits para describir 6 letras en la secuencia, por lo que eventualmente podría comprimir mi secuencia con un factor de $3$ y por lo tanto mi tasa de entropía sería $\frac{\log26}{3}$ .

Pero me pierdo con la derivación teórica de la misma. Dice que la tasa de entropía se define como:

$$H(X) = \lim_{n->\infty} \frac{1}{n}H(X_1, X_2, X_3, \dots X_n)$$

Luego dice que $H(X)$ es una medida de la entropía por símbolo de la variable $X_t$ y la función es como:

$$\log26 + 0 + 0 + \log26 + 0 + 0+\dots+ \log26 + 0 + 0$$

Ahora dice que esta función está "aplastada" entre dos límites:

$\frac{\log26}{3}n \le H(X_1, X_2, X_3, \dots X_n) \le \frac{\log26}{3}(n+2)$

Dividiendo ambos límites con $n$ Veo que la tasa de entropía es efectivamente $\frac{\log26}{3}$ .

Pero, ¿podría alguien explicar la intuición detrás de la función $H(X)$ y cómo se establecen estos límites?

Answer 1

Boceto:

En general, $n$ puede escribirse como $$n = 3 m + r $$ donde $m,r$ son enteros no negativos y $r \in \{1,2, 3\}$ es el resto de $n$ dividido por $3$ más uno.

Puis $$H_n = (m +1)H(X) = \left(\frac{n+3-r}{3}\right) H(X)$$

¿Puedes seguir desde aquí?

Answer 2

$X_i^{1} \sim U(\{1,2,\ldots 26\})$ i.i.d., s.t., $H(X_i^{1})=\log_2{26}$ donde la v.r. representa el primer símbolo del $i^{th}$ grupo $X_i$ . Todos los grupos (excepto posiblemente el último) contienen (como máximo) 3 variables, con la $1^{st}$ siendo aleatorios, y los otros completamente deterministas.

Puede haber 3 casos:

1. $n \equiv 0 (\text{mod } 3)$ : hay $\frac{n}{3}$ grupos para los que el primero se elige aleatoriamente (uniformemente) entre $26$ símbolos, los otros dos están totalmente determinados, por lo que la entropía total $H(X)=\sum\limits_{i=1}^{\frac{n}{3}}H(X_i^{1})=\frac{n}{3}\log{26}$ .

2. $n \equiv 1 (\text{mod } 3)$ : hay $\frac{n-1}{3}$ grupos para los que el primero se elige aleatoriamente (uniformemente) entre $26$ símbolos, los otros dos están totalmente determinados, además hay un único símbolo en el grupo $X_{\frac{n-1}{3}+1}$ por lo tanto la entropía total $=\sum\limits_{i=1}^{\frac{n-1}{3}}H(X_i^{1})+H\left(X_{\frac{n-1}{3}+1}^{1}\right)=\frac{n-1}{3}\log{26}+\log{26}=\frac{n+2}{3}\log{26}$ .

3. $n \equiv 2 (\text{mod } 3)$ : hay $\frac{n-2}{3}$ grupos para los que el primero se elige aleatoriamente (uniformemente) entre $26$ símbolos, los otros dos están totalmente determinados, además hay un último grupo con dos símbolos en el grupo $X_{\frac{n-2}{3}+1}$ por lo tanto la entropía total $=\sum\limits_{i=1}^{\frac{n-2}{3}}H(X_i^{1})+H\left(X_{\frac{n-2}{3}+1}^{1}\right)=\frac{n-2}{3}\log{26}+\log{26}=\frac{n+1}{3}\log{26}$ .

Por lo tanto, $\frac{n}{3}\log{26}\leq H(X) \leq \frac{n+2}{3}\log{26}$ .