Does an approximation exist between the Cumulative Binomial Distribution and the probability of combinations?

Question

Suppose that we have two disjoint subsets $A$ and $B$ of $Z$. Both $A$ and $B$ have a large number of elements each.

We want to compute the probability of picking $k$ elements from $A$ e $B$, with the condition that at most $t$ elements come from $B$.

I can compute that probability using the cumulative binomial distribution. Given that the probability $p = \dfrac{|B|}{|Z|}$.

So, $\displaystyle \Pr(X \leq t) = \sum_{i = 0}^{t} {k \choose i} p^i (1-p)^{k-i}$

I think I can see this problem in a different fashion. Given all possible ways of choosing $k$ elements of $Z$, which is probability of picking a combination of elements of $A$ and $B$ such as there is at most $t$ elements of $B$.

That, would be given by $\displaystyle \frac{1}{\displaystyle{|Z|\choose k}}\cdot \sum_{i = 0}^{t} {|A| \choose k-i}{|B| \choose i}$

What I realized that when $X$, $A$, and $B$ are large, both equation tend to have approximated results.

In fact, I'm having a little trouble in understanding the difference between this two formulations. Mostly, because I performed both in some data and I had no significant difference between the results.

This R code below is an example of what I am talking about. I want to select 7 elements, being up to 3 from B. The larger $X$, $A$, and $B$ become the closer the probabilities are. I set first case $|A| = 13$, $|B| = 7$. Second case, $|A| = 33$, $|B| = 17$. Third case, $|A| = 53$, $|B| = 47$. Finally, $|A| = 693$, $|B| = 307$.

(choose(13,7)*choose(7,0) + choose(13,6)*choose(7,1) + choose(13,5)*choose(7,2) + choose(13,4)*choose(7,3))/(choose(20,7))
pbinom(3,7,7/20)
(choose(33,7)*choose(17,0) + choose(33,6)*choose(17,1) + choose(33,5)*choose(17,2) + choose(33,4)*choose(17,3))/(choose(50,7))
pbinom(3,7,17/50)
(choose(53,7)*choose(47,0) + choose(53,6)*choose(47,1) + choose(53,5)*choose(47,2) + choose(53,4)*choose(47,3))/(choose(100,7))
pbinom(3,7,47/100)
(choose(693,7)*choose(307,0) + choose(693,6)*choose(307,1) + choose(693,5)*choose(307,2) + choose(693,4)*choose(307,3))/(choose(1000,7))
pbinom(3,7,307/1000)

Would anyone have some light to shed?

Answer 1

First, where you write $A$ e $B$, I think you meant $A\cup B$. You don't clarify whether you mean $A\cup B=Z$. I think you do: in the equality $\displaystyle \Pr(X \leq t) = \sum_{i = 0}^{t} {k \choose i} p^i (1-p)^{k-i}$, you need $A\cup B=Z$ in order to write $(1-p)$ instead of $\frac{|A|}{|Z|}$.

But this argument works also with $A\cup B \subsetneqq Z$ and my answer follows the general case of $A\cup B \subseteqq Z$.

It is important to understand that there is nothing surprising about being able to compute something in two different ways. In fact, it can be used as an instructive exercise to prove an identity between algebraic expressions without calculation, by giving two different, correct arguments why it should be one or the other expression. This is what you are doing here. This technique is called double counting. Vandermonde's identity is an example that is similar to yours.

But you have made a mistake in your first sum (that I have also copied over). You are computing the probability with replacement of what you have drawn. You need to do it without replacement. Without the error, the two expressions would be identical, you're proving an identity, so R should be giving you equal outputs. The reason why you're not getting equal outputs is this mistake: that you erroneously substituted a formula for sampling with replacement for a formula for sampling without replacement.

The right formula would have been instead $$\Pr(X \leq t) = \sum_{i = 0}^{t} {k \choose i} \frac{|B|}{|Z|}\cdot \frac{|B|-1}{|Z|-1}\dots \frac{|B|-i+1}{|Z|-i+1}\cdot \frac{|A|}{|Z|-i}\cdot\frac{|A|-1}{|Z|-i-1}\dots\frac{|A|-(k-i)+1}{|Z|-k+1}.$$ This further equals $$\sum_{i = 0}^{t} \frac{k!}{i!(k-i)!} \frac{1}{\frac{|Z|!}{(|Z|-k)!}}\frac{|B|!}{(|B|-i)!}\frac{|A|!}{(|A|-k+i)!}$$ which is $$\frac{1}{\displaystyle{|Z|\choose k}}\cdot \sum_{i = 0}^{t} {|B| \choose i}{|A| \choose k-i},$$ and this is your other formula.