Lower bound for the probability of binomial variable to be less than her expectation

Question

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

Answer 1

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

Answer 2

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.