Let $B$ be Binomial $(n,p)$. Is there a simple but tight bound on \begin{align} \sum_{k=1}^n P(B<k) P(B\ge k) \end{align} as function of $n$?
Here is my attempt, which I think is suboptimal, \begin{align} \sum_{k=1}^n P(B<k) P(B\ge k) &\le \sum_{k=1}^n P(B\ge k) \text{ use $P(B<k) \le 1$ }\\ &= \sum_{k=1}^n e^{-2n(p-\frac{k}{n} )^2}, \end{align} where in the last step we have use a tail bound for Binomial (see wiki). There are some other better tail bounds that can improve this inequality. However, I think we still lose a lot in step.
Is there a better way of approaching this? That would result in a tight bound for large $n$?
We can approximate $B_{n}$ as a normal random variable: $$\hat{B}_{n} = (B_{n}-np) /\sqrt{np(1-p)} \sim N(0,1)$$ Then, $$P(B_{n} < k) = P\left(\hat{B}_{n} < (k-np)/\sqrt{np(1-p)}\right)$$ $$P(B_{n} \geq k) = P\left(\hat{B}_{n} \geq (k-np)/\sqrt{np(1-p)}\right)$$ Therefore,
$$\frac{1}{\sqrt{np(1-p)}}\sum_{k=1}^n P(B<k) P(B\ge k) \rightarrow \int_{-\infty}^{\infty} \Phi(x)(1-\Phi(x)) dx = \frac{1}{\sqrt{\pi}}$$
Is approximately the Riemann integral of $\Phi(x)(1-\Phi(x))$ from $-np/\sqrt{np(1-p)}$ to $n(1-p)/\sqrt{np(1-p)}$ with step sizes of $1/\sqrt{np(1-p)}$.
In conclusion: $$\sum_{k=1}^n P(B<k) P(B\ge k) \approx \sqrt{\frac{np(1-p)}{\pi}}$$ (Approximately as in their ratio goes to $1$.)