# 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.

-

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.

-
There may be a slightly easy method then the above but as soon as Chernoff bound is not tight enough then you have to work a lot harder. – alext87 Sep 27 '10 at 9:27
Thanks a lot for your answer! I think the Poisson approximation looks very promising numerically. Unfortunately, I can't find any good information about error bounds for the approximation. Do you have any suggestions on where I can look? – Marcus Fry Sep 28 '10 at 8:21
@Marcus: See edit. If you need anything else explained then just comment again. – alext87 Sep 28 '10 at 12:53
For a binomial random variable $X$ with parameters $(n, p)$, if $E[X] = np$ is an integer, then the mean, mode, and median coincide (cf. wikipedia entry for references). In this instance, the mean is the integer $a$, and thus $P\{X > a\} < \frac{1}{2}$. So maybe just looking at $P\{X = a\}$ and showing that it is smaller than $\frac{1}{4}$ except for a few cases when it can be checked by hand or computer that $P\{X \leq a\} \leq \frac{3}{4}$ might suffice? – Dilip Sarwate Oct 6 '11 at 19:45