8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I very much like your question. While I fail to prove it theoretically, I can at least say that numerical evaluations agree with your proposition at least until $n=1000$. Convergence to the value you give (approx $1/3$) is very strong there already. $\endgroup$ – Mau314 Feb 14 at 13:36
  • $\begingroup$ Thanks, @Mau314. You might consider upvoting the question so that more people see it. $\endgroup$ – Nuno Feb 14 at 14:01
  • 1
    $\begingroup$ It's not quite the kind of answer you were hoping for, but you can have some non-asymptotic quantification from the Berry-Esseen-theorem: Here it tells us that $$P\left(\frac{|S_n-np|}{\sqrt{np(1-p)}}>1\right)\leq P(|Y|>1)+\frac{1}{2*(p(1-p))^{3/2}\sqrt{n}}$$ and in the the case $p=0.5$ we can derive that your desired bound at least holds for $n\geq 712$. I know, it's very far from satisfactory... (The 712 can be improved a bit, but it will still be large.) Sorry I don't have time to write it in more detail right now. $\endgroup$ – Mau314 Feb 14 at 14:19
  • $\begingroup$ Thank you very much, @Mau314. I also noted the B-E bound when checking Wikipedia. $\endgroup$ – Nuno Feb 14 at 14:47
  • $\begingroup$ I incorporated your comment into the answer below. Thank you very very much, @Mau314. $\endgroup$ – Nuno Feb 15 at 4:21
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Congrats! So being more careful with the constants is more worthwile than I thought! $\endgroup$ – Mau314 Feb 15 at 7:19
  • $\begingroup$ Thank you, @Mau314. $\endgroup$ – Nuno Feb 15 at 7:25
0
$\begingroup$

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.

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