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

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?

• Could you clarify how you are "picking" elements? Are you perhaps sampling without replacement and uniformly from $Z$? Or from $A\cup B$?
– whuber
Aug 29, 2018 at 19:37
• I think you clarified my problem. It is that once I get one element, there is no replacement in my scenario, because I have limited resources. Aug 29, 2018 at 19:54

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$.
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.