4
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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$) $\endgroup$ Aug 23, 2011 at 15:55
  • $\begingroup$ 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. $\endgroup$ Aug 24, 2011 at 12:37

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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