# A variant of “hypergeometric” distribution

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)$$?

• 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. – Clement C. Jul 17 at 1:34
• 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?) – Clement C. Jul 17 at 1:37
• 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. – Sudipta Roy Jul 17 at 1:44
• 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. – Sudipta Roy Jul 17 at 1:55
• 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). – Clement C. Jul 17 at 2:05