Demuestra que las cadenas de bits con una relación 1/0 diferente a 50/50 son comprimibles

Question

Estoy buscando una prueba, que $$ \sum_{i=0}^{\lambda n} \binom{n}{i} \le 2^{nH(\lambda)} $$ con $n>0$ , $0 \le \lambda \le 1/2$ y $ H(\lambda)=-[\lambda log \lambda + (1-\lambda) log (1-\lambda)] $ .

Contexto: Esto demuestra que si hay una cadena de bits con una proporción de unos y ceros ('elige i de n' donde i es menor que 0,5, de ahí el binomio) suficientemente diferente de 50/50, también hay menos de $2^n$ posibilidades para una cadena de este tipo con una longitud de hasta $n$ . Esto significa que se pueden enumerar y describir como su índice en la secuencia enumerada, que es más corta que la propia cadena, lo que supone una compresión.

Answer 1

La desigualdad deseada es equivalente a demostrar

$$P(n,\lambda)=\frac{1}{2^n}\sum_{i=0}^{\lambda n} \binom{n}{i} \le 2^{-n(1-H(\lambda))}$$

Ahora, $P(n,\lambda)$ es la probabilidad de que la media de $n$ Variables aleatorias de Bernoulli (con $p=1/2$ ) no es mayor que $\lambda$ . Aplicando Confinamiento de Chernoff (versión de entropía relativa) obtenemos

$$ P(n,\lambda) \le e^{ -n D(\lambda \mid\mid p) } = 2^{-n D_2(\lambda \mid\mid p)} $$ con $p=\frac{1}{2}$ , donde $D_2(\lambda\mid\mid p) = \lambda \log(\lambda/p)+ (1-\lambda) \log((1-\lambda)/(1-p))$ (logaritmos en base $2$ ).

En nuestro caso: $D_2(\lambda\mid\mid 1/2) =-H(\lambda) +1$

Por lo tanto, se deduce la desigualdad deseada.

(Tenga en cuenta que esto supone que $H(\lambda)$ en la ecuación original está en bits).