5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.