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?
