The probability that a Binomial Distribution deviates from its mean by one standard deviation

Question

Let $X$ be a random variable that follows the Binomial Distribution $\text{BIN}(n,p)$, where $n$ is a positive integer while $p\in(0,1)$. Its mean is $np$, and standard deviation is $\sqrt{np(1-p)}$. Chebyshev's inequality yields that $$\Pr\left(|X-np| > \sqrt{np(1-p)}\right) \le 1,$$ which is trivial. Hoeffding’s inequality seems not helpful to improve the bound if applied in a direct way.

Questions:

1. When $p=1/2$, is it possible to prove for all $n\ge 1$ that $$\Pr\left(|X-np| > \sqrt{np(1-p)}\right) \le \frac{1}{2}?$$

2. What can we say for a general $p\in(0,1)$?

Remarks:

1. I found a positive answer to Question 1 (presented below; essentially the same as @Mau314's comment). However, it is not completely satisfactory because we have to verify the inequality for small n (at most 25) numerically. I am still looking forward to an answer that is completely analytical.

2. I am teaching basic probability theory and these questions occur to me when I think about the Central Limit Theorem. When $n\rightarrow \infty$, asymptotically we have $$\Pr\left(|X-np| > \sqrt{np(1-p)}\right) \sim \Pr(|Y| > 1) < \frac{1}{2},$$ where $Y$ is a random variable that follows the Standard Normal Distribution. Hence I raise the questions by curiousity.

3. Note that my main interest is the non-asymptotic behaviour of the probability because the asymptotic case is characterized by the CLT.

4. One may attack the problem by directly estimate the cumulative distribution function of Binomial Distributions. To this end, bounds for Binomial Coefficients are likely necessary. Results of such kind can be found in, e.g., [Das], [Stanica], [Spencer, Chapter 5], and Wikipedia. Note that non-asymptotic estimations are needed.

Thanks.

Answer 1

Here is a positive answer to Question 1. However, it is not completely satisfactory because we have to verify the inequality for small $n$ (at most $25$) numerically. I am still looking forward to an answer that is completely analytical.

As @Mau314 points out in his comment, a natural approach is to examine the error in the CLT, a classical result being the Berry-Esseen theorem. See also the question "Berry-Esseen bound for binomial distribution". According to the Berry-Esseen theorem, $$\sup_{x\in\mathbb{R}}|F(x) - \Phi(x)| \le \frac{C[p^2+(1-p)^2]}{\sqrt{np(1-p)}},$$ where $F$ is the cumulative distribution function of $(X-np)/\sqrt{np(1-p)}$ while $\Phi$ is that of the Standard Normal Distribution, and $C$ is a constant. It is known that $C<0.5$ (see [Shevtsova]), which holds for a large class of distrbutions besides Binomial. [Nagaev and Chebotarev, Theorem 2] proves $C\le0.4215$ for $\text{BIN}(n,1/2)$. According to such bounds, $$\Pr\left(|X-np| > \sqrt{np(1-p)}\right) \le \Pr(|Y|>1) + \frac{2C[p^2+(1-p)^2]}{\sqrt{np(1-p)}} < \frac{1}{3} + \frac{2C[p^2+(1-p)^2]}{\sqrt{np(1-p)}}.$$ Thus $$\Pr\left(|X-np| > \sqrt{np(1-p)}\right) < \frac{1}{2}$$ for $$n \ge \frac{144 C^2[p^2+(1-p)^2]^2}{p(1-p)}.$$ When $p=1/2$, we find that $n\ge 26$ suffices to guaruantee the desired inequality. Indeed, $n\ge 22$ is enough with a bit more care. One can check numberically that the desired inequality (for $p=1/2$) holds for $n\le 25$ as well. Hence the answer to Question 1 is positive.

Alternatively, one can use [Hipp and Mattner, Corollary 1.5], which says that $$\left|P\left(X< \frac{n-\sqrt{n}}{2}\right)-\Phi(1)\right| \le \frac{1}{\sqrt{2\pi n}}.$$ Hence $$\Pr\left(\left|X- \frac{n}{2}\right| > \frac{\sqrt{n}}{2}\right)\le \Pr(|Y|>1) + \sqrt{\frac{2}{\pi n}}.$$ This will justify the desired inequality for $n\ge 23$. The cases with $1\le n \le 22$ can be checked numerically.

Answer 2

This is too long for a comment, but isn't a full answer.

Motivation In de Moivre's derivation of his famous Central Limit Theorem for Bernoulli random variables, he also derived a local limit theorem as well:

(de Moivre) Denote $P_n(k) = \binom{n}{k}p^k(1-p)^{n-k}$. Then \begin{align*} \sup_{x: |x| \le \psi(n)} \left|\frac{P_n(np + x \sqrt{npq})}{\frac{1}{\sqrt{2\pi npq}}e^{-x^2/2}} - 1\right| \rightarrow 0 \end{align*} for some function $\psi(n) = o(npq)^{1/6}$.

What fails for Berry-Esseen is the fact thatt he sup is taken over $x \in \mathbb{R}$, while in reality we want it taking over $|x| \le 1$ (in the parametrization of de Moivre above). In the proof of this local limit theorem, asymptotics are used, and hence a lot of information is lost, including the exact form of $\psi(n)$ and the rate at which the expression above goes to 0. If we try to reproduce this proof, but be mindful in keeping track of all the pesky terms and bound them with inequalities rather than big-$O$ notation, then we might get somewhere.

A partial journey Using Stirling's formula, we may express \begin{align*} P_n(k) = \frac{1}{\sqrt{2\pi\hat{p}\hat{q}}}\exp\left(-n D(\hat{p}\|p)\right) \mathcal{E}(n, k, n-k) \end{align*} where \begin{align*} \hat{p} &= \frac{k}{n}, \quad \hat{q} = 1 - \hat{p}, \\ D(a\|b) &= a \log\frac{a}{b} + (1-a)\log \frac{1-a}{1-b} \ge 2(a - b)^2, \\ \mathcal{E}(n,k,n-k) &= \frac{1 + \frac{1}{12n} + \frac{1}{288n^2} - \cdots}{(1 + \frac{1}{12k} + \frac{1}{288k^2} - \cdots)(1 + \frac{1}{12(n-k)} + \frac{1}{288(n-k)^2} - \cdots)} \le \exp\left(\frac{1}{12n}\right) \end{align*} Therefore, \begin{align*} P_n(k) \le \frac{1}{\sqrt{2\pi\hat{p}\hat{q}}}\exp\left(-2n (\hat{p} - p)^2\right) \exp\left(\frac{1}{12n}\right) \end{align*} Letting $k = np + x \sqrt{npq}$ for $|x| \le 1$, \begin{align*} P_n(np + x\sqrt{npq}) &\le \frac{1}{\sqrt{2\pi pq}}\exp\left(-2pq x^2 \right) \exp\left(\frac{1}{12n}\right) \frac{\sqrt{pq}}{\sqrt{\hat{p}\hat{q}}} \\ &\le \frac{1}{\sqrt{2\pi pq}}\exp\left(-2pq x^2 \right) \exp\left(\frac{1}{12n}\right) \frac{\sqrt{pq}}{\sqrt{(p - \sqrt{pq/n})(q - \sqrt{pq/n})}} \end{align*} Let $x_k = -1 + 2k/N$ for $k = 0, \cdots, N$ and arguing via Riemann integration, \begin{align*} \sum_{k=0}^{N} P_n(np + x_k\sqrt{npq})\cdot \frac{2}{N} &\le \sum_{k=0}^{N}\frac{1}{\sqrt{2\pi pq}}\exp\left(-2pq x_k^2 \right) \exp\left(\frac{1}{12n}\right) \frac{\sqrt{pq}}{\sqrt{(p - \sqrt{pq/n})(q - \sqrt{pq/n})}}\cdot \frac{2}{N} \\ &\color{red}{\approx} \exp\left(\frac{1}{12n}\right) \frac{\sqrt{pq}}{\sqrt{(p - \sqrt{pq/n})(q - \sqrt{pq/n})}} \int_{-1}^{1} \frac{1}{\sqrt{2\pi pq}}\exp\left(-2pq x^2 \right) dx \end{align*} This last step will certainly need some justification and inequalities relating Riemann sums and their respective integrals. I hope this is a good start to an analytical answer; note that I've listed as many inequalities out as possible, and while I simplified a few, you can retain them through the steps to obtained sharper bounds.