0
$\begingroup$

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.

Footnotes

  • 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$.
Improve this question
$\endgroup$
3
  • $\begingroup$ See "Chernoff bounds", as in en.wikipedia.org/wiki/Binomial_distribution#Tail_bounds $\endgroup$
    – usul
    Jun 2, 2018 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, 2018 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, 2018 at 17:45

1 Answer 1

Reset to default
7
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.