Proving an upper bound for Prob[X>=E[X]] Let random variable $X\sim\text{Binomial}\left(a+b,\frac{a}{a+b}\right)$, where $a$ and $b$ are positive integers.
I'm trying to prove that $\mathbb{P}[X\geq\mathbb{E}[X]]\leq\frac{3}{4}$, which appears to be true numerically.
Does anyone have a suggestion on how to proceed?
The complication in this particular problem is that the condition is not a strict inequality "$>$".
I've tried the Chernoff bound but it's not tight enough.
 A: Here is an answer giving the outline of a proof.  
The Bound is tight
If the bound is true then it is tight: If $a=1$, $b=1$ then 
$\mathbb{P}[X\geq \mathbb{E}[x]] = \mathbb{P}[X\geq 1] =1-\mathbb{P}[X=0] = 1-\frac{1}{2}\frac{1}{2}=\frac{3}{4}$
Getting a feel for the problem
As a rule of thumb (though can be made precise) if $a>5$ and $b>5$ then we can approximate the Binomial by normal random variable by the central limit theorem. That is $X\sim N(a,Var(X))$ approximately.  The error in this approximation becomes increasing small as $a$ and $b$ increase. 
Hence $\mathbb{P}[X\geq \mathbb{E}[x]] \approx \frac{1}{2}<\frac{3}{4}$ for $a>5$ and $b>5$
To make precise, first read this: http://en.wikipedia.org/wiki/Binomial_distribution#Normal_approximation
and then: Box, Hunter and Hunter (1978). Statistics for experimenters. Wiley. p. 130
We are left with three cases: a and b both small, a large and b small, b large and a small. 
$b$ large and $a\leq 5$
If $b+a>100$ then a poisson approximation to the Binomial r.v. becomes appealling. That is $X\sim Po(a)$ approximately. 
Then $\mathbb{P}(X\geq a)=1-\sum_{i=0}^{a-1}\frac{e^{-a}a^i}{i!}\leq 0.63<\frac{3}{4}$
For explicit error bounds look in A bound on the Poisson-binomial relative error by Teerapabolarn (2007). Theorem 2.1 contains a good error bound.
$b\leq 5$ and $a$ large
Let $Y=a+b-X\sim  \text{Bin}(a+b,\frac{b}{a+b})$ now if $b+a>100$ $Y$ is approximately Poisson and 
$\mathbb{P}(X\geq a)\approx\mathbb{P}(Y\leq b) <0.45 \leq \frac{3}{4}$
Remaining cases
Note that the cases above are not quite mutually exclusive, but there a finite number of cases left. The cases left are 
1) $a\leq 5$ and $b\leq 100$
2) $b\leq 5$ and $a\leq 100$
And this can be checked on a computer. To give the bound. 
