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
    Commented 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
    Commented 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
    Commented 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__
    Commented Jun 6, 2018 at 12:23
  • $\begingroup$ P.S. you forgot the factor $C$ within $P(... \leq \sqrt{n})$. $\endgroup$
    – Julien__
    Commented Jun 6, 2018 at 12:23
  • $\begingroup$ @Julien__ : Thank you for your comment. I have now fixed the typo. $\endgroup$
    – Iosif Pinelis
    Commented Jun 6, 2018 at 13:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .