Finding Tight bound for Binomial Coefficient inequality

Question

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.

Answer 1

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