0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Could you clarify how you are "picking" elements? Are you perhaps sampling without replacement and uniformly from $Z$? Or from $A\cup B$? $\endgroup$ – whuber Aug 29 '18 at 19:37
  • $\begingroup$ 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. $\endgroup$ – Caiosan Aug 29 '18 at 19:54
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes. You are very correct. I did not think through the matter of replacement. Thank you very much! $\endgroup$ – Caiosan Aug 29 '18 at 19:55

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.