This is already posted here.

We all are aware of Hypergeometric distribution. Let me first briefly discuss what it is.

Suppose we have an urn containing $N$ balls, $M$ of which are red, rest are blue. We draw $n$ balls from the urn (without replacement) and let $H(n,N,M)$ denotes the number of red balls in the sample.

We have $Pr[H(n,N,M) = k] = \frac{\binom{M}{k}\binom{N-M}{n-k}}{\binom{N}{n}}$ and $\mathbb{E}[H(n,N,M)] = n\frac{M}{N}$.

Hypergeometric distribution enjoys centain concentration property. Formally for any $\epsilon>0$

$Pr[H(n,N,M) \geq n\frac{M}{N} + \epsilon n] \leq \exp(-2\epsilon^2 n)$ and

$Pr[H(n,N,M) \leq n\frac{M}{N} - \epsilon n] \leq \exp(-2\epsilon^2 n)$

See, for example The tail of the hypergeometric distribution for an elementary proof.

Now suppose the urn contain at least $M$ red balls, as opposed to exactly $M$ red balls. As before we draw $n$ balls from the urn without replacement and $H^{apx}(n,N,M)$ counts the number of red balls in the sample. My question is that : can we somehow translate the expectation and tail bound of $H(n,N,M)$ to $H^{apx}(n,N,M)$. More formally is the following true for any $\epsilon > 0$ and some (rapidly decreasing as $n$ tends to $\infty$) function $f(n,\epsilon)$?

$Pr[H^{apx}(n,N,M) \geq \mathbb{E}[H^{apx}(n,N,M)] + \epsilon n] \leq f(n,\epsilon)$ and

$Pr[H^{apx}(n,N,M) \leq \mathbb{E}[H^{apx}(n,N,M)] - \epsilon n] \leq f(n,\epsilon)$

Moreover, whether $\frac{\mathbb{E}[H^{apx}(n,N,M)]}{\mathbb{E}[H(n,N,M)]} = \Theta(1)$?

  • 1
    $\begingroup$ For your last question: not in general -- your constraint that the true number be at least $M$ doesn't preclude all the balls to be red, in which case of course the ratio becomes $\frac{n}{n\frac{M}{N}} = \frac{N}{M}$, which can be arbitrarily large. $\endgroup$ – Clement C. Jul 17 at 1:34
  • $\begingroup$ Now, given that the tail bounds do not explicitly depend on $M$, why can't you apply them with the true (unknown, but fixed) value $M^\ast$ to get exactly what you want regarding the tails? (Maybe I am missing something?) $\endgroup$ – Clement C. Jul 17 at 1:37
  • $\begingroup$ Suppose $S\subseteq [N]$ with $\vert S\vert\geq \beta N$(red balls). Now if it was eactly $\beta N$, then if we sample $N/2$ balls(WOR), it will contain at least $\frac{1}{4}\beta N$ points of $S$ (whp), according to the(second) stated inequality. I was wondering if the same is true here. $\endgroup$ – Sudipta Roy Jul 17 at 1:44
  • $\begingroup$ One approach : fix any subset $S^\prime$ of $S$ of size $\beta N$ and consider the rest of the $S$ as white balls. Since the concentraion bound only depends on $M$, I think this will work. $\endgroup$ – Sudipta Roy Jul 17 at 1:55
  • 1
    $\begingroup$ What I was suggesting is just to apply the inequality with the (unknown, true value) $|S|$. From the existing inequality you state, the only dependence on $|S|$ is in the expectation $\mathbb{E}[H^{apx}(n,N,M)] = \mathbb{E}[H(n,N,|S|)] = n\frac{|S|}{N}$ , so things will go through and you will get the statement you want. The fact that you don't know $|S|$ doesn't mean you can't reason about it (it has a fixed, well-defined value). $\endgroup$ – Clement C. Jul 17 at 2:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.