Let $H$ be a random variable with hypergeometric distribution of parameters $n,h,r$ (that is $n$ is the total number of elements, $h$ elements are white and I choose $r$ elements).

Let $B$ be a random variable with binomial distribution of parameters $r$, $h/n$ (that is $r$ independent trials with success probability $h/n$)

Is it true that for any $k$ $$Pr(H\ge k)\ge Pr(B\ge k)?$$



Since $H$ and $B$ have the same expected value, $$ \sum_{k} Pr(H\ge k) - Pr(B \ge k) = E[H] - E[B] = 0 $$ In any case where the distributions are not the same, your inequality can't be true for all $k$.

  • $\begingroup$ Is the statement valid for $k$ beyond the mean? Since the Chernoff tail bounds for binomial apply to hypergeometric (negative correlation), it seems like binomial should have a heavier tail than hypergeometric. $\endgroup$ – elexhobby Nov 21 '14 at 17:32

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.