I am trying to find the smallest $0< \delta < 1/2$ so that the following bound holds:

$$\sum_{k=0}^{\delta n} {n \choose k}\left(\sum_{i=k}^{n}{n \choose i}\right)\leq \frac{2^{2n}}{4n} $$

Plotting this, it seems like $\delta \leq (\frac{1}{2}- \frac{c}{\sqrt{n}})$ is plenty when $c \geq 2$ (I think the actual value of $c$ probably resembles the constant in Sterling's formula). I'm having trouble actually proving this however.

I tried upper bounding using the Entropy based bound for sums of binomial coefficients:

$$\frac{2^{h(\delta)\cdot n}}{n} \leq \sum_{k=0}^{\delta n}{n \choose k} \leq 2^{h(\delta)\cdot n}$$

(where $h(\cdot)$ is the binary entropy function) which holds for $\delta<\frac{1}{2}$, But this bound doesn't seem to be tight enough. Considering out-of-the-box bounds for binary entropy, this approach only gives $\delta \leq (\frac{1}{2}- \frac{c}{\sqrt{n}})$ for $c= \omega(1)$. Ideally, I would like to show that this holds for $c=O(1)$ suffices. Any help would be greatly appreciated.


An equivalent way of stating things: Let $X$ and $Y$ be two independent variables, each having distribution $Bi(n,\frac{1}{2})$. You want $$P(X \leq \delta n \textrm{ and } X \leq Y) \leq \frac{1}{4n}.$$ The equivalence here comes from dividing both binomial sums by $2^n$ to view them as probabilities.

In a way, the second inequality $X \leq Y$ is redundant "up to a constant factor". For any $\delta < \frac{1}{2}$ we have $$P(X \leq \delta n) > P(X \leq \delta n \textrm{ and } X \leq Y) > P(X \leq \delta n \textrm{ and } \delta n \leq Y ) > \frac{1}{2} P(X \leq \delta n)$$

So we're really just looking at asymptotics of a single binomial variable. In particular, taking $\delta=\frac{1}{2} - \frac{c}{\sqrt{n}}$ is not sufficient, since by the Central Limit Theorem $X$ will be at least $c \sqrt n$ away from $\frac{n}{2}$ with probability bounded away from $0$.

  • $\begingroup$ I really appreciate the response. Literally just realized this and posted it myself (deleting my post now). Thank you! $\endgroup$ – mm8511 May 22 '18 at 22:08

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.