# Show that interval of maximum probability grows no faster than $\sqrt{n}$ for binomial distribution

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$.
• See "Chernoff bounds", as in en.wikipedia.org/wiki/Binomial_distribution#Tail_bounds – usul Jun 2 '18 at 16:27
• 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). – Nate Eldredge Jun 2 '18 at 17:18
• @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. – Iosif Pinelis Jun 3 '18 at 17:45

## 1 Answer

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

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