Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The bound formula is:

$$H(M,N,n,k) \leq (( \frac{p}{p+t} )^{p+t} (\frac{1-p}{1-p-t})^{1-p-t})^n$$

So how to proof it?

Some papers discuss it: this one, that one.

They say the proof is in the following paper: The tail of the hypergeometric distribution. Discrete Mathematics

But I can not find the online version.

share|cite|improve this question
The paper is online here, but you need a university subscription. – t.b. Feb 14 '11 at 12:56
Please don't post the same questions (more or less) simultaneously here and on MathOverflow. I suggest the following procedure: Ask here first and if you didn't get any helpful answer in a few days you might consider asking on MathOverflow. – t.b. Feb 14 '11 at 12:58
Also you have the MR entry – Willie Wong Feb 14 '11 at 13:04
That, plus the fact that the inequality is a straightforward consequence of the usual exponential inequalities applied to sums of random variables. That is, coming back to the physical interpretation of the hypergeometric distribution, one considers $S_n=X_1+\cdots+X_n$ where $X_i$ is Bernoulli and $X_i=1$ iff the ball drawn at time $i$ is white. The only twist here is that the $X_i$s are not independent. Fortunately, they are negatively correlated, hence the upper bound one would get by assuming independence is still valid. – Did Feb 14 '11 at 13:36
@Fan: That would be absurd and is not what I wrote. Rather, for every negatively correlated $U$ and $V$, $E(UV)\le E(U)E(V)$. (And if you merely look at the definition, you will see that it is meaningless to say that a random variable is negatively correlated, on its own, all alone...) – Did Feb 14 '11 at 17:57
up vote 2 down vote accepted

This question has been answered to the satisfaction of the OP in the comments.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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