Lower bound on right tail probability of binomial distribution 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.
 A: 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.
A: $$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.
A: 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).
