Conditional probability of intersection of multiple hypergeometric distributions

Question

What's given:

• I have an urn with with a set $S$ of balls where $|S| = N$. Each ball $b_i$ has a unique id and can either be red or blue. There are $m$ red balls in the urn.
• $d$ times I randomly draw a subset $D_j \subseteq S$ of the balls from the urn. $|D_j|$ is predetermined for each trial. After each trial, I put all the balls I drew back, so the population is always the same for each trial.
• I know that $D_j$ has $r_j$ red balls and I know the id of the balls that I drew, but I don't know which of the balls I drew were red.
• Let $E_j$ be the event that $D_j$ contains $r_j$ red balls.

Find an expression for: $$P(E_n|\bigcap_{j = 1}^{n - 1}E_j)$$

Here's a more concrete example:

$N = 5, m = 3, d = 2$
$D_1 = \{b_1, b_2\}, r_1 = 1$
$D_2 = \{b_1, b_2, b_3\}, r_2 = 2$

I think the answer is supposed to be 2/3 because I wrote out all the combinations, but I don't know how to generalize it. Because I'm drawing from a finite population without replacement, I think I'm supposed to use a hypergeometric distribution. Something like $X_j \sim HypG(|D_j|, N, m)$. So I'm looking for $P(X_n = r_n | \bigcap_{j = 1}^{n - 1} X_j = r_j)$.

Since we gain information about how many red balls a particular subset of the population has, the $X_j$s are not independent. Once trial 1 happens, we know that exactly 1 of ball 1 and ball 2 are red, so for trial 2 we can eliminate any possibilities that both ball 1 and 2 are red. If they were independent, I think we would have a 3/5 chance of getting trial 2. Knowing which balls were in which trial affects knowledge about the outcome.

I've tried solving using
$$P(X_n = r_n | \bigcap_{j = 1}^{n - 1} X_j = r_j) = \frac{P(\bigcap_{j = 1}^{n} X_j = r_j)}{P(\bigcap_{j = 1}^{n - 1} X_j = r_j)}$$ But I run into trouble trying to interpret the outcome of the previous trials, especially when I'm getting the intersection of more than two trials. How do I account for the information that exactly $r_j$ balls from $D_j$ are red?

Answer 1

Your presentation here is very complicated, but the problem appears to be quite trivial. Unless I am missing something here, you are effectively just drawing a sequence of independent values from the hypergeometric distribution. (You have not specified any source of statistical dependence between the trials.) Letting $d_i \equiv |D_i|$ be the number of balls drawn on trial $i$, you have:

$$\mathbb{P}(E_i) = \mathbb{P}(D_i = r_i) = \frac{{m \choose r_i} {N-m \choose d_i-r_i}}{{N \choose d_i}}.$$

Since you replace the balls each time, assuming random sampling of the balls in each trial, there should be no dependence between the trials, so you would have:

$$\mathbb{P}(E_n | E_1 \ \cap \ ... \ \cap \ E_{n-1} ) = \mathbb{P}(E_n) = \frac{{m \choose r_n} {N-m \choose d_n-r_n}}{{N \choose d_n}}.$$

Now, unless I have misunderstood something here, most of what you have added to this question is an unnecessary complication. Since all balls are replaced after each trial, and the numbers of balls, etc., is taken as known, there is nothing in your question that would induce any statistical dependence between the trials.

Answer 2

I figured out a rather complicated program that computes the answer, but I'm not sure how to explain it. If it's not clear from my question, my grasp on stats and math notation is tenuous at best. (Sorry.)

The hard part of the problem comes down to how to represent the intersection of multiple trials. Once that part is down, we can use $$P(E_n|\bigcap_{j=1}^{n-1}E_j)=P(\bigcap_{j=1}^{n}E_j)/P(\bigcap_{j=1}^{n-1}E_j)$$.

I couldn't find a single generalizable way to do it, but I was able to narrow it down to two cases: the simple case and the... less simple case. The example in the question demonstrates the simple case.

Each trial can be written as a set of tuples that encode the number of red balls in $D_j$ and $D_j^C$. Let $T$ be a set of tuples in the form $(B, r)$ where $B$ is a subset of the balls in the urn, and $r$ is the number of red balls in $B$. So trial 1 is $T_1 = \{(\{b_1,b_2\}, 1),(\{b_3,b_4,b_5\},2)\}$ and trial 2 is $T_2 = \{(\{b_1,b_2,b_3\}, 2),(\{b_4,b_5\},1)\}$.

I'm not sure how this works, but I was able to find $T_n \cap T_m$ by taking $T_n \cup T_m$ and transforming it using the following process:

1. Compare each element with each other element, looking for elements where the first tuple value is a proper subset of the first tuple value of another element. In other words, find a $t = (B_a, r_a)$ where there exists some $s = (B_b, r_b)$ where $t, s \in T$ and $B_b \subset B_a$.
2. Replace $t$ in the set with $(B_a - B_b, r_a - r_b)$.
3. Repeat steps (1) and (2) until for every $t, s \in T$ where $t = (B_a, r_a)$ and $s = (B_b, r_b)$, $B_b \not\subset B_a$.

In our example, $T_1 \cup T_2 = \{(\{b_1,b_2\}, 1),(\{b_3,b_4,b_5\},2),(\{b_1,b_2,b_3\}, 2),(\{b_4,b_5\},1)\}$. We see an element $t = (\{b_1,b_2,b_3\}, 2)$ and another element $s = (\{b_1,b_2\}, 1)$. We can replace $t$ with $(\{b_3\}, 1)$. We continue until we end up with $T_1 \cap T_2 = \{(\{b_1,b_2\}, 1),(\{b_3\},1),(\{b_4,b_5\},1)\}$.

Then check if there are any elements whose first value intersects with the first value of any other element. If for every $(B_a, r_a), (B_b, r_b) \in T$ $B_a$ and $B_b$ are disjoint sets, then we are in the simple case. Otherwise, we are in the less simple case.

Simple case: all sets disjoint

Because all the sets in the tuples in the simple case are disjoint, each $t \in T$ can be considered a draw from the urn without replacement. To find $P(T)$, consider a $D$ that is a sequence of draws $d_i$ from the urn without replacement where each $d_i = (B_i,r_i)$ is a different element of T. (Basically, pretend $T$ is ordered.) $$P(T) = \prod\limits_{i=1}^{|T|}P(X_i=r_i)$$ where $X_i \sim HypG(m_i,N_i,n_i)$
$n_i = |B_i|$
$m_i = m_{i-1} - r_{i - 1}$
$N_i = N_{i - 1} - n_{i - 1}$
$N_1 =$ number of balls in the urn
$m_1 =$ number of red balls in the urn.

In other words, take the probability that $d_i$ has $r_i$ red balls, update the total number of balls and red balls left to account for the draw, and repeat until the urn is empty.

Recall that for a hypergeometric distribution, $P(X_i=r_i)=\frac{\dbinom{m_i}{r_i}\dbinom{N_i - m_i}{n_i - r_i}}{\dbinom{N_i}{n_i}}$, and you have a solution for the simple case. Going back to the example $P(T_1 \cap T_2) = \left(\frac{\dbinom{3}{1}\dbinom{2}{1}}{\dbinom{5}{2}}\right)\left(\frac{\dbinom{2}{1}\dbinom{1}{0}}{\dbinom{3}{1}}\right)\left(\frac{\dbinom{1}{1}\dbinom{1}{1}}{\dbinom{2}{2}}\right) = 2/5$. Since $P(T_1) = 3/5$, $P(T_2|T_1) = 2/3$.

Less simple case: some sets intersecting

But imagine a less simple case where for some $(B_a, r_a), (B_b, r_b) \in T$, $B_a$ intersects with $B_b$. Then $P(T) = \sum\limits_{b \in B_a}P(T|E_b)P(E_b)$ where $E_b$ is the event that $b$ is red. In other words, we add up the probabilities $T$ happens given $b$ is red times the probability that $b$ is red. (Law of total probability.) We know to encode $E_b$ as $T_b = \{(\{b\},1)\}$ and repeat the whole song and dance for $T \cap T_b$.

For example, consider a
$T_1 = \{(\{b_1,b_2\}, 1),(\{b_3,b_4,b_5\},2)\}$ and
$T_2 = \{(\{b_1,b_3\},1),(\{b_2,b_4,b_5\},2)\}$.
We find that $T_1 \cap T_2 = \{(\{b_1,b_2\}, 1),(\{b_1,b_3\},1),(\{b_2,b_4,b_5\},2),(\{b_3,b_4,b_5\},2)\}$.
Since $\{b_1,b_2\}$ intersects with $\{b_1,b_3\}$, we take $\{b_1,b_2\}$ and create two cases: $R_1 = \{(\{b_1\}, 1)\}$ and $R_2 = \{(\{b_2\}, 1)\}$. We then see that $P(T_1 \cap T_2) = P(T_1 \cap T_2|R_1)P(R_1) + P(T_1 \cap T_2|R_2)P(R_2)$.

To represent $T_1 \cap T_2|R_i$, remove 1 red ball at $b_i$ from the urn. So you end up with
$T_1 \cap T_2|R_1 = \{(\{b_2\}, 0),(\{b_3\},0),(\{b_4,b_5\},2)\}$
$T_1 \cap T_2|R_2 = \{(\{b_1\}, 0),(\{b_3\},1),(\{b_4,b_5\},1)\}$
$P(T_1 \cap T_2 | R_1) = \left(\frac{\dbinom{2}{0}\dbinom{2}{1}}{\dbinom{4}{1}}\right)\left(\frac{\dbinom{2}{0}\dbinom{1}{1}}{\dbinom{3}{1}}\right)\left(\frac{\dbinom{2}{2}\dbinom{0}{0}}{\dbinom{2}{2}}\right) = 1/6$
$P(T_1 \cap T_2 | R_2) = \left(\frac{\dbinom{2}{0}\dbinom{2}{1}}{\dbinom{4}{1}}\right)\left(\frac{\dbinom{2}{1}\dbinom{1}{0}}{\dbinom{3}{1}}\right)\left(\frac{\dbinom{1}{1}\dbinom{1}{1}}{\dbinom{2}{2}}\right) = 1/3$

Note that $P(R_1) = P(R_2) = 3/5$, so $P(T_1 \cap T_2) = (3/5)(1/6 + 1/3) = 3/10$ and $P(T_2|T_1) = 1/2$.