# Probability that $S$ of the sets are of a given type?

I have an urn with $N$ red balls and $M$ white balls, total $T=N+M$.

I draw balls without replacement $K$ at a time, where $K|T$, ending up with $T/K$ sets of $K$ balls.

I'd like to calculate the probability distribution for the number of sets that have exactly $K$ red balls.

For example, say there are 10 Red and 20 White, I draw 10 sets of 3 balls each, I'd like to get the PMF for the number of sets of 3 Red balls present among the 10 sets drawn.

I was able to get proper results for very simple cases (like all the red balls ending up in full sets), but I'm at a loss how to generalize this.

• You draw one $K$ set without replacement... OK. Before you draw the second $K$ set, do you put the first $K$ set back, or do you select without replacement all over the process? – zoli Feb 6 '17 at 10:34
• @zoli: No, balls are never replaced. If they were, it becomes super simple - it's just a binomial distribution on the number of sets drawn for probability equal to the hypergeometric probability of getting a complete set of red on a draw. I think inclusion-exclusion might be needed here, added that tag. – HammyTheGreek Feb 6 '17 at 20:52

You can answer this question using logic similar to inclusion/exclusion, but the standard formula does not seem to apply directly. Let's treat all balls as being distinguishable, and let's cast our experiment as drawing all of the balls in sequence, and then grouping the first $K$ balls drawn into a set $S_1$, then the second set of $K$ balls into a set $S_2$, etc., until we have $K' = \frac{T}{K}$ sets $S_i$ for $i \in \{1 \ldots K'\} = {\cal I}$. Modeling this way, our sample space is the set of all permutations of $T$ balls, of which there are $T!$ elements.

Define $Z = \lfloor \frac{N}{K}\rfloor$, which is the largest number of groups that can be entirely red, and for any $Y \subset {\cal I}$, let $R_Y$ denote the set of all permutations of the balls such that the set $S_i$ is entirely red if and only if $i \in Y$.

Suppose first that $Y \subset {\cal I}$ is of size $Z$. Then we can count $R_Y$ by assigning red balls to all sets $S_i$ with $i \in Y$, which can be done in $\frac{N!}{(N-ZK)!}$ ways, and then assigning balls to the remaining sets arbitrarily, which can be done in $(T-ZK)!$ ways. Note that no additional sets $S_j$ with $j \notin Y$ can be created, since there are not enough red balls remaining to fully populate a set.

Let's denote this number of permutations in $R_Y$ for a particular set $Y \subset {\cal I}$ of size $Z$ as $${\cal R}(Z)=\frac{N!}{(N-ZK)!}(T-ZK)!$$ Hence the probability of having exactly $Z$ sets of entirely red balls is $\frac{{K' \choose Z}{\cal R}(Z)}{T!}$, since ${\cal R}(Z)$ depends only on the cardinality of $Y$, not the elements of $Y$ themselves.

Now suppose $Y \subset {\cal I}$ has size $Z-1$. We can count the number of permutations that have $S_i$ all red for each $i \in Y$ just like before as $\frac{N!}{(N-(Z-1)K)!}(T-(Z-1)K)!$, but this count includes permutations which have one additional set of balls entirely red. To quantify the overcount, we can pick an additional set $S_j$ to be entirely red in $K'-Z+1$ ways, and then we know that the number of sets which have $S_i$ red for all $i \in Y \cup \{j\}$ is exactly ${\cal R}(Z)$. Letting ${\cal R}(Z-1)$ denote the number of permutations that have $S_i$ entirely red if and only if $i \in Y \subset {\cal I}$, with $|Y| = Z-1$, we have $${\cal R}(Z-1)= \frac{N!}{(N-(Z-1)K)!}(T-(Z-1)K)! - (K'-Z+1){\cal R}(Z)$$

Using the same logic, for any fixed $x$ we can calculate ${\cal R}(x)$ recursively with the formula $${\cal R}(x) = \frac{N!}{(N-xK)!}(T-xK)! - \displaystyle \sum_{i=x+1}^Z {{K'-x} \choose {i-x}}{\cal R}(i)$$ Let $X \subset {\cal I}$ have size $x$, so that ${\cal R}(x)$ is the size of $R_X$. We can populate the sets $S_i$ with red balls for $i \in X$, and distribute the remaining balls randomly in $\frac{N!}{(N-xK)!}(T-xK)!$ ways. But for every superset of $X$ with size $Z$ or less, this count includes permutations with all sets in the superset being entirely red. For each such superset $X'$, there are exactly ${\cal R}(X')$ permutations which have $S_i$ entirely red if and only if $i \in X'$; moreover, none of these permutations are double-counted because of the "if and only if". Thus we just subtract off ${\cal R}(|X'|)$ for each superset $X'$ of $X$ that has size less than or equal to $Z$, proving the formula above.

With this formula in place, we have that the probability of getting exactly $x$ sets of entirely red balls is $${K' \choose x}\frac{{\cal R}(x)}{T!}$$ I used Magma to enumerate some small cases to test out the formula against enumeration, and the results check out. Looking at the test case in the original post, with 30 balls, of which 10 are red and we draw balls three at a time, I find the distribution of $X$, the number of sets consisting of entirely red balls, as $$Pr[X=0] = 0.72026\\Pr[X=1] = 0.26399\\Pr[X=2] = 0.01566\\Pr[X=3] = 0.00008$$

• Nice! I'm working through understanding the derivation, but your work is clear enough I was able to go ahead and implement in Python, works perfectly. Thanks! – HammyTheGreek Feb 9 '17 at 20:38