# Lower bound for tail of hypergeometric distribution

There are several simple and widely used upper bounds on the tail of the hypergeometric distribution, including $P(X > E[X]+tn) <= e^{-2t^{2}n}$, where X is hypergeometric with parameters N, M, and n. (Thinking of the hypergeometric as describing sampling from a population, N is the population size, M is the number of "interesting" items, n is the size of the sample we draw, and X is the number of interesting items in the sample.) This amusing paper is a good summary:

Matthew Skala. Hypergeometric tail inequalities: ending the insanity, 2009.

It appears to be an unpublished manuscript, but is available at http://ansuz.sooke.bc.ca/professional/hypergeometric.pdf

However, I've been unable to find a simple and reasonably tight lower bound on that same tail probability. Anyone know one?

• I would have thought you can't do much better than taking the maximum of the sum. i.e. $P(X>E[X]+tn)\geq P(X=k)$ where $k$ is the smallest integer above $E[X]+tn$ (for $t>0$) Aug 23, 2011 at 15:55
• You may be right, but the tail of a hypergeometric (especially for big N) behaves so nicely it seems like there ought to be a simple and fairly tight lower bound. Aug 24, 2011 at 12:37

The problem is, that the $2t^2n$ tail is only quite sharp when $n$ is quite small compared to $N$. When it's large, you get an exponent of $\frac{2(tn)^2}{N-n}$, which can be a lot stronger. See https://ahlenotes.wordpress.com/2015/12/08/hypergeometric_tail/ for more details.

You could get a general lower bound by simply looking at the largest term in the sum:

\begin{aligned} \Pr[X > EX + tn] &= \Pr[X > (M/N+t)n]\\ &\ge \left.{M \choose (M/N+t)n}{N \choose (1-M/N-t)n} \middle/ {N \choose n}\right.\\ &\ge ... \end{aligned}

But it's not really going to be elegant, unless you know what parameter range you are looking for.