Let $X \sim \text{Binom}(n, p)$ a binomial random variable. I want to show that : $$\forall 0 < t < 0.9, \quad \exists C, \quad \forall n >1, \quad \mathbb P\bigg(|X-np| \leq C\sqrt{n}\bigg) \geq t$$

I want to prove the result for all $n$, so pure asymptotic is not enough.

1- Using the normal approximation together with a Berry-Essen bound we can prove that : $$\mathbb P\bigg(|X-np| \leq x\sqrt{p(1-p)}\sqrt{n}\bigg) > \Phi(x) - \Phi(-x) - \frac{2C(p^2 + (1-p)^2)}{\sqrt{np(1-p)}} $$ Taking $x = 3$ and $C = .4215$, this yield (part of) the result when $np(1-p)$ is not too small, for instance $np(1-p) \geq 1$ and $n \geq 1000$. Remains to prove for $n < 1000$ and small $p$.

2- When $np$ is small, we have a great bound on the absolute error for the Poisson approximation : $$\bigg| \text{Binom}(n, p) - \text{Pois}(np) \bigg| \leq p(1 - e^{-np})$$

But I can't show the result for a Poisson random variable.

Any help, either with the Poisson r.v. or using another approach would be greatly appreciated.


  • The value for $C$ comes from Nagaev, Chebotarev (2010).
  • I said $t < 0.9$ but anything that generalizes to $t < 0.99$ and beyond is great, obviously we can't go as far as $t = 1$.
  • $\begingroup$ See "Chernoff bounds", as in en.wikipedia.org/wiki/Binomial_distribution#Tail_bounds $\endgroup$ – usul Jun 2 '18 at 16:27
  • 2
    $\begingroup$ Maybe I've misunderstood the question, but don't you get this directly from the central limit theorem? Let $C_n$ be the least number $P(|X_n - np| / \sqrt{n} \le C_n) \ge 0.9$. By the central limit theorem, the $C_n$ converge to a finite limit (the $0.9$ quantile of an $N(0, p(1-p))$ distribution), so $C = \sup_n C_n$ is finite and satisfies the desired inequality. In fact, I think this proves $\exists C \forall n$ which is stronger than what you wrote (but maybe it's what you meant to write). $\endgroup$ – Nate Eldredge Jun 2 '18 at 17:18
  • 1
    $\begingroup$ @NateEldredge : It appears that the OP wanted the constant $C$ not to depend on $p$. From the central limit theorem or the Berry--Esseen bound, it is apparently impossible to get such a bound. $\endgroup$ – Iosif Pinelis Jun 3 '18 at 17:45

$\newcommand{\de}{\delta} \newcommand{\De}{\Delta} \newcommand{\ep}{\varepsilon} \newcommand{\ga}{\gamma} \newcommand{\Ga}{\Gamma} \newcommand{\la}{\lambda} \newcommand{\Si}{\Sigma} \newcommand{\thh}{\theta} \newcommand{\om}{\omega} \newcommand{\R}{\mathbb{R}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\F}{\mathcal{F}} \newcommand{\E}{\operatorname{\mathsf E}} \renewcommand{\P}{\operatorname{\mathsf P}} \newcommand{\ii}[1]{\operatorname{\mathsf I}\{#1\}} \newcommand{\tf}{\widetilde{f}}$

For any $t\in(0,1)$, let $C=\dfrac1{2\sqrt{1-t}}$. Let also $q:=1-p$ and note that $pq\le1/4$ for all $p\in(0,1)$. So, by Chebyshev's inequality, $$\P(|X-np|\le C\sqrt n)\ge1-\frac{npq}{C^2n}\ge1-\frac1{4C^2}=t,$$ as desired.

  • $\begingroup$ Thank you very much, this is what I was looking for. I should have thought of it myself. +1 $\endgroup$ – Julien__ Jun 6 '18 at 12:23
  • $\begingroup$ P.S. you forgot the factor $C$ within $P(... \leq \sqrt{n})$. $\endgroup$ – Julien__ Jun 6 '18 at 12:23
  • $\begingroup$ @Julien__ : Thank you for your comment. I have now fixed the typo. $\endgroup$ – Iosif Pinelis Jun 6 '18 at 13:03

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.