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

I'm looking for a proof, that $$\sum_{i=0}^{\lambda n} \binom{n}{i} \le 2^{nH(\lambda)}$$ with $n>0$, $0 \le \lambda \le 1/2$ and $H(\lambda)=-[\lambda log \lambda + (1-\lambda) log (1-\lambda)]$.

Context: This shows, that if there is a bitstring with a ratio of ones and zeros ('pick i from n' where i is smaller than 0.5, hence the binomial) sufficiently different from 50/50, there are also less than $2^n$ possibilities for such a string of a length up to $n$. This means they can be enumerated and described as their index in the enumerated sequence, which is shorter than the string itself, which is a compression.

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).