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.

  • $\begingroup$ 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. $\endgroup$ – alext87 Sep 27 '10 at 9:27
  • $\begingroup$ 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? $\endgroup$ – Marcus Fry Sep 28 '10 at 8:21
  • $\begingroup$ @Marcus: See edit. If you need anything else explained then just comment again. $\endgroup$ – alext87 Sep 28 '10 at 12:53
  • $\begingroup$ 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? $\endgroup$ – Dilip Sarwate Oct 6 '11 at 19:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.