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



Show that interval of maximum probability grows no faster than $\sqrt{n}$ for binomial distribution
$\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. 


