Let $X$ a binomial variable of parameter $(N,p)$, with $0<p<0.5$
I would like to lower bound $\mathbb{P}\left(X <Np \right)$ by a constant ($\frac{1}{5}$ seems true and is enough for me).


Thank you by advance



Lower bound for the probability of binomial variable to be less than her expectation
$\newcommand{\al}{\alpha}
\newcommand{\de}{\delta}
\newcommand{\De}{\Delta}
\newcommand{\ep}{\varepsilon}
\newcommand{\ga}{\gamma}
\newcommand{\Ga}{\Gamma}
\newcommand{\la}{\lambda}
\newcommand{\si}{\sigma}
\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}} 
\newcommand{\PP}{\operatorname{\mathsf P}}
\newcommand{\ii}[1]{\operatorname{\mathsf I}\{#1\}} 
\newcommand{\tf}{\widetilde{f}}$ 


Let $n:=N$. User usul gave in his comment a [reference](https://cs.nyu.edu/media/publications/binomial.pdf) to a result, which implies the exact lower bound, $1/4$, on $\PP(X\le np)$ for $p\in(0,1-\frac1n]$. Let us show here that the same lower bound holds under the following slightly better condition on $p$ (which can be shown optimal). Namely, let us show that 
\begin{equation\*}
 \PP(X<np)\ge\tfrac14\tag{1}
\end{equation\*}
for  

\begin{equation\*}
 p\in\Big(0,1-\frac cn\Big],\tag{2}
\end{equation\*}
where 
\begin{equation\*}
 c:=\ln\frac43=0.28768\dots.\tag{3} 
\end{equation\*}
Our proof appears to be significantly simpler than that in [reference](https://cs.nyu.edu/media/publications/binomial.pdf). 


By Shevtsova's version of the [Berry--Esseen bound](https://en.wikipedia.org/wiki/Berry%E2%80%93Esseen_theorem), 
\begin{equation\*}
 \PP(X<np)\ge \frac12-\ep,\quad\ep:=\frac{c\_3}{\sqrt n}\Big(\frac\rho{\si^3}+c\_2\Big), 
\end{equation\*}
$\rho=q^3p+p^3q$, $\si=\sqrt{pq}$, $q:=1-p$, $c\_3:=\frac{33554}{100000}$, $c\_2=\frac{415}{1000}$. 
Since $\ep$ is a simple algebraic function of $p,n$, one can (algorithmically) solve a simple problem of real algebraic geometry to show that $\frac12-\ep$ is $\ge$ a certain algebraic number $0.25579\ldots>\frac14$ when $np\ge2$ and $nq\ge2$. 


Therefore and because (2) can be rewritten (for $p\in(0,1)$) as $nq\ge c$, it remains to consider the following cases. 


*Case 1:* $1<np\le2$ and $n\ge3$. Then 
\begin{equation\*}
 \PP(X<np)=\PP(X\le1)=f\_1(p):=f\_1(p,n):=q^n + n q^{n - 1} p. 
\end{equation\*}
We have $f\_1'(p)=-(n-1) n q^{n-2} p<0$, and so, $f\_1(p)$ is decreasing in $p$. So, here without loss of generality (wlog) $p=2/n$, and 
and 
\begin{equation\*}
 \tilde f\_1(n):=f\_1(2/n,n)=\frac{3 n-2}{n-2}\,\left(\frac{n-2}{n}\right)^n. 
\end{equation\*}
Letting 
\begin{equation\*}
 D\tilde f\_1(n):=\tilde f'\_1(n)\Big/\frac{\left(\frac{n-2}{n}\right)^n \left(3 n^2-8 n+4\right)}{(n-2)^2}
 =\frac{\left(3 n^2-8 n+4\right) \ln\frac{n-2}{n}+6 n-8}{(n-2) (3 n-2)}, 
\end{equation\*}
we have 
\begin{equation\*}
 (D\tilde f\_1)'(n)=-\frac{4 \left(3 n^2-4 n+4\right)}{(2-3 n)^2 (n-2)^2 n}<0. 
\end{equation\*}
So, $D\tilde f\_1$ is decreasing. Also, $D\tilde f\_1(\infty-)=0$. So, $D\tilde f\_1>0$ and hence $\tilde f\_1$ is increasing, from $\tilde f\_1(3)=\frac 7{27}=0.25925\dots>\frac14$. So, $\PP(X<np)>\frac14$ in Case 1. 


*Case 2:* $0<np\le1$ and $n\ge2$. This case is similar to, and simpler than, Case 1. In this case the lower bound $\frac14$ is attained when $n=2$ and $p=1/2$. 


*Case 3:* $1<nq\le2$ and $n\ge4$. This case is similar to, and slightly simpler than, Case 1. Note that $\PP(X<np)=1-\PP(X\ge n-nq)$, and here $nq$ is small. In this case the infimum of $\PP(X<np)$ is $67/256=0.26171\ldots>\frac14$, and it is attained "in the limit" when $n=4$ and $p=\frac34-$. 


*Case 4:* $c\le nq\le1$ and $n\ge1$, where $c$ is as in (3). Then 
\begin{equation\*}
 \PP(X<np)=1 - p^n\ge1 - p^{c/q}\ge\tfrac14. 
\end{equation\*}


*Case 5:* $n\in\{1,2,3\}$. For each of these three values of $n$, $\PP(X<np)$ is piecewise polynomial in $p$ and thus is easily minimized, which allows us to conclude that in this case (1) holds as well. 


