Lower bound for the probability of binomial variable to be less than her expectation 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
 A: $\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 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. 
By Shevtsova's version of the Berry--Esseen bound, 
\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.  
A: I also ran into this problem a while ago, and wasn't completely satisfied with the published proof. In fact, I'll present a small poster in Vilnius in two weeks on a rather simple, different proof that generalises the result a bit. It does not involve any approximation at all! Rather, it derives the inequality by proving that the quantity is "sort of" monotone in $n$.
The basic building block of the proof is a result by Hoeffding saying, for our purposes, that if $Y_1, \dotsc, Y_n$ are independent Bernoulli with $\mathbb{P}(Y_i(p) = 1) = p_i$, $\sum_{i=1}^n p_i = k$, and $a \leq k \leq b$ then $$\mathbb{P}(a \leq \sum_{i=1}^n Y_i \leq b) \geq \mathbb{P}(a \leq \operatorname{Bin}(n,k/n) \leq b).$$
Now $X \sim \operatorname{Bin}(n,k/n)$ so that $\mathbb{E}(X) = n \cdot k/n = k$ can be written as $X = \sum_{i=1}^{n} I_i$ where $I_1, \dotsc, I_{n}$ are independent with $\mathbb{P}(I_i = 1) = k/n$. But we also have $X = \sum_{i=1}^{n} I_i + I'_{n+1} = \sum_{i=1}^{n-1} I_i + I''_{n+1} - 1$ where $I'_{n+1} = 0$ and $I''_{n+1} = 1$, in other words Bernoulli with success $0$ and Bernoulli with success $1$! By Hoeffding's result we therefore have
$$\mathbb{P}(X < k) = \mathbb{P}(\sum_{i=1}^{n} I_i + I'_{n+1} < k) \leq \mathbb{P}(\operatorname{Bin}(n+1,k/(n+1)) < k)$$
$$\mathbb{P}(X < k) = \mathbb{P}(\sum_{i=1}^{n} I_i + I''_{n+1} - 1 < k) \leq \mathbb{P}(\operatorname{Bin}(n+1,(k+1)/(n+1)) < k+1)$$
By iterating these inequalities you can identify the extremal case, where $n$ is as small as possible, directly! Indeed, the proof works for values other than the mean, which allows us to, for example, get analogous results for constant shifts away from the mean.
I recently discovered that the same idea was used by Anderson and Samuels.
