Prove that bitstrings with 1/0-ratio different from 50/50 are compressable

Solution 1:

The desired inequality is equivalent to prove

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

Now, $P(n,\lambda)$ is the probability that the average of $n$ Bernoulli random variables (with $p=1/2$) is not greater than $\lambda$. Applying Chernoff bound (relative entropy version) we get

$$ P(n,\lambda) \le e^{ -n D(\lambda \mid\mid p) } = 2^{-n D_2(\lambda \mid\mid p)} $$ with $p=\frac{1}{2}$, where $D_2(\lambda\mid\mid p) = \lambda \log(\lambda/p)+ (1-\lambda) \log((1-\lambda)/(1-p))$ (logarithms in base $2$).

In our case: $D_2(\lambda\mid\mid 1/2) =-H(\lambda) +1$

Hence the desired inequality follows.

(Note that this assumes that $H(\lambda)$ in the original equation is in bits).