Lower bound on right tail probability of binomial distribution

Question

Let $X$ be a binomial($n$, $p$) random variable with $p<1$ and expected value $E(X)=np\geq 1$. Does it always hold that $P(X>E(X))\geq 1/4$?

Letting $n=2$ and $p=1/2$ shows that this would be best possible.

Answer 1

$$P(X>np)=\sum_{k=m}^n \binom{n}{k}p^k(1-p)^{n-k}$$ where $m=\lceil np \rceil$

Now, as $n\to \infty$ with $np$ constant, the distribution converges to $\mathcal{N}(np,npq)$, then $P(X>np)\to 1/2$, So at the limiting case the proposition holds, but it seems to be difficult to see if this true for the finite case for any $p$ and in the comments Jack has given one counterexample too.

Answer 2

As you've stated it, it looks like the answer is no. To see this, just take $n=1$, then you get

$E[X]=p$ and $P[X>EX]=p$.

However according to Wikipedia's article on the Binomial Distribution, if $np$ is integer (like in your example), then it is also the median, and so

$$P[X>EX] = (1 - P[X=EX])/2$$

Like in your case.

The article also has some more results and sources which may interest you.

Answer 3

Yes. You need $p < 1$ and $p \ge 0.29/n$ (which is weaker than the $p \ge 1/n$ from the question).

I sketch the main argument below. A full proof including all elementary estimates can be found in

Benjamin Doerr. An elementary analysis of the probability that a binomial random variable exceeds its expectation. Statistics and Probability Letters, 139:67-74, 2018,

or the arxiv preprint at https://arxiv.org/abs/1712.00519.

The main argument, valid for $1/n \le p < 1$, is as follows. Let $X$ be a binomial random variable with parameters $n$ and $p$. Let $k = \lfloor E[X] \rfloor$ and let $Y$ be a binomial random variable with parameters $n$ and $k/n$. Then \begin{align*} \Pr[X > E[X]] &= \Pr[X \ge k+1] \\ &\ge \Pr[Y \ge k+1] \\ &= \Pr[Y \ge k] - \Pr[Y = k] \\ &> \frac 12 - \sqrt{\frac{n}{2\pi k (n - k)}}. \end{align*} Here the first inequality stems from the natural stochastic domination relation between binomial distributions with different success probabilities. The last estimate uses (i) the well-known fact that a binomial distribution with integral expectation has this expectation as (unique) median and an elementary estimate for the binomial distribution (building on Stirling's formula).