# What is the distribution of the cardinality of the intersection of independent random samples without replacement?

$S$ is some set with $n\in\mathbb{N}$ elements, and $a_1,a_2,...,a_m$ are fixed positive integers less than or equal to $n$.

With the elements of $S$ being equally likely, $m$ samples $L_1, L_2,...,L_m$ are separately and independently drawn from $S$ without replacement, the size of which are $a_1,a_2,...,a_m$, respectively.

The cardinality of the intersection of the samples $\left|L_1\cap L_2\cap\ ...\ \cap L_m\right|$ has, in general, support equal to $\{0,1,...,\min\{a_1,a_2,...,a_m\}\}$, but which distribution does it follow?

• I can provide you a recipe for calculating it recursively but I'm not aware of a closed form solution. Would that suffice, or do you want an explicit expression of the distribution function given $a_1, \dots, a_m$ and $n$? – Bridgeburners Mar 7 '18 at 21:23
• @Bridgeburners A recipe would be nice, at least it would provide some method/way of attacking this problem and related. – llrs Mar 7 '18 at 21:39

Here's another approach, one that doesn't involve recursion. It still uses sums and products whose lengths depend on the parameters, though. First I'll give the expression, then explain.

We have \begin{align} P &\bigl( | L_{1} \cap L_{2} \cap \cdots \cap L_{m} | = k \bigr) \\ &= \frac{\binom{n}{k}}{\prod_{i = 1}^{n} \binom{n}{a_{i}}} \sum_{j = 0}^{\min(a_{1}, \ldots, a_{m}) - k} (-1)^{j} \binom{n - k}{j} \prod_{l = 1}^{n} \binom{n - j - k}{a_{l} -j - k}. \end{align}

EDIT: At the end of writing all of this, I realized that we can consolidate the expression above a little by combining the binomial coefficients into hypergeometric probabilities and trinomial coefficients. For what it's worth, the revised expression is $$\sum_{j = 0}^{\min(a_{1}, \ldots, a_{m}) - k} (-1)^{j} \binom{n}{j, k, n - j - k} \prod_{l = 1}^{n} P( \text{Hyp}(n, j + k, a_{l}) = j + k).$$ Here $\text{Hyp}(n, j + k, a_{l})$ is a hypergeometric random variable where $a_{l}$ draws are taken from a population of size $n$ having $j + k$ success states.

## Derivation

Let's get some notation in order to make the combinatorial arguments a little easier to track (hopefully). Throughout, we consider $S$ and $a_{1}, \ldots, a_{m}$ fixed. We'll use $\mathcal{C}(I)$ to denote the collection of ordered $m$-tuples $(L_{1}, \ldots, L_{m})$, where each $L_{i} \subseteq S$, satisfying

• $|L_{i}| = a_{i}$; and
• $L_{1} \cap \cdots \cap L_{m} = I$.

We'll also use $\mathcal{C}'(I)$ for a collection identical except that we require $L_{1} \cap \cdots \cap L_{m} \supseteq I$ instead of equality.

A key observation is that $\mathcal{C}'(I)$ is relatively easy to count. This is because the condition $L_{1} \cap \cdots \cap L_{m} \supseteq I$ is equivalent to $L_{i} \supseteq I$ for all $i$, so in a sense this removes interactions between different $i$ values. For each $i$, the number of $L_{i}$ satisfying the requirement is $\binom{|S| - |I|}{a_{i} - |I|}$, since we can construct such an $L_{i}$ by choosing a subset of $S \setminus I$ of size $a_{i} - |I|$ and then unioning with $I$. It follows that $$| \mathcal{C}'(I) | = \prod_{i = 1}^{n} \binom{|S| - |I|}{a_{i} - |I|}.$$

Now our original probability can be expressed via the $\mathcal{C}$ as follows: $$P \bigl( | L_{1} \cap L_{2} \cap \cdots \cap L_{m} | = k \bigr) = \frac{ \sum_{I : |I| = k} | \mathcal{C}(I) | } { \sum_{\text{all I \subseteq S}} | \mathcal{C}(I) | }.$$

We can make two simplifications here right away. First, the denominator is the same as $$| \mathcal{C}'(\emptyset) | = \prod_{i = 1}^{n} \binom{|S|}{a_{i}} = \prod_{i = 1}^{n} \binom{n}{a_{i}}.$$ Second, a permutation argument shows that $| \mathcal{C}(I) |$ only depends on $I$ through the cardinality $|I|$. Since there are $\binom{n}{k}$ subsets of $S$ having cardinality $k$, it follows that $$\sum_{I : |I| = k} | \mathcal{C}(I) | = \binom{n}{k} | \mathcal{C}(I_{0}) |,$$ where $I_{0}$ is an arbitrary, fixed subset of $S$ having cardinality $k$.

Taking a step back, we've now reduced the problem to showing that $$| \mathcal{C}(I_{0}) | = \sum_{j = 0}^{\min(a_{1}, \ldots, a_{m}) - k} (-1)^{j} \binom{n - k}{j} \prod_{l = 1}^{n} \binom{n - j - k}{a_{l} - j - k}.$$

Let $J_{1}, \ldots, J_{n - k}$ be the distinct subsets of $S$ formed by adding exactly one element to $I_{0}$. Then $$\mathcal{C}(I_{0}) = \mathcal{C}'(I_{0}) \setminus \biggl( \bigcup_{i = 1}^{n - k} \mathcal{C}'(J_{i}) \biggr).$$ (This is just saying that if $L_{1} \cap \cdots \cap L_{m} = I_{0}$, then $L_{1} \cap \cdots \cap L_{m}$ contains $I_{0}$ but also does not contain any additional element.) We've now transformed the $\mathcal{C}$-counting problem to a $\mathcal{C}'$-counting problem, which we know more how to handle. More specifically, we have $$| \mathcal{C}(I_{0}) | = | \mathcal{C}'(I_{0}) | - \biggl| \bigcup_{i = 1}^{n - k} \mathcal{C}'(J_{i}) \biggr| = \prod_{l = 1}^{n} \binom{n - k}{a_{l} - k} - \biggl| \bigcup_{i = 1}^{n - k} \mathcal{C}'(J_{i}) \biggr|.$$

We can apply inclusion-exclusion to handle the size of the union expression above. The crucial relationship here is that, for any nonempty $\mathcal{I} \subseteq \{ 1, \ldots, n - k \}$, $$\bigcap_{i \in \mathcal{I}} \mathcal{C}'(J_{i}) = \mathcal{C}' \biggl( \bigcup_{i \in \mathcal{I}} J_{i} \biggr).$$ This is because if $L_{1} \cap \cdots \cap L_{m}$ contains a number of the $J_{i}$, then it also contains their union. We also note that the set $\bigcup_{i \in \mathcal{I}} J_{i}$ has size $|I_{0}| + |\mathcal{I}| = k + |\mathcal{I}|$. Therefore \begin{align} \biggl| \bigcup_{i = 1}^{n - k} \mathcal{C}'(J_{i}) \biggr| &= \sum_{\emptyset \neq \mathcal{I} \subseteq \{ 1, \ldots, n - k \}} (-1)^{| \mathcal{I} | - 1} \biggl| \bigcap_{i \in \mathcal{I}} \mathcal{C}'(J_{i}) \biggr| \\ &= \sum_{j = 1}^{n - k} \sum_{\mathcal{I} : |\mathcal{I}| = j} (-1)^{j - 1} \prod_{l = 1}^{n} \binom{n - j - k}{a_{l} - j - k} \\ &= \sum_{j = 1}^{n - k} (-1)^{j - 1} \binom{n - k}{j} \prod_{l = 1}^{n} \binom{n - j - k}{a_{l} - j - k}. \end{align} (We can restrict the $j$ values here since the product of the binomial coefficients is zero unless $j \leq a_{l} - k$ for all $l$, i.e. $j \leq \min(a_{1}, \ldots, a_{m}) - k$.)

Finally, by substituting the expression at the end into the equation for $| \mathcal{C}(I_{0}) |$ above and consolidating the sum, we obtain $$| \mathcal{C}(I_{0}) | = \sum_{j = 0}^{\min(a_{1}, \ldots, a_{m}) - k} (-1)^{j} \binom{n - k}{j} \prod_{l = 1}^{n} \binom{n - j - k}{a_{l} - j - k}$$ as claimed.

• +1 for all the effort and the solution, but I'll need to polish my maths to understand most of this (and the other answer). Thanks – llrs Mar 12 '18 at 11:07

I'm not aware of an analytic way to solve this, but here's a recursive way to compute the result.

For $m=2$ you're choosing $a_2$ elements out of $n,$ $a_1$ of which have been chosen before. The probability of choosing $k \le \min\{a_1,a_2\}$ elements that intersect with $L_1$ in your second draw is given by the hypergeometric distribution:

$$P(k \mid n, a_1, a_2) = \frac{ {a_1 \choose k} {n - a_1 \choose a_2 - k} } {n \choose a_2}.$$

We can call the result $b_2.$ We can use the same logic to find $P(b_3 = k \mid n, b_2, a_3),$ where $b_3$ is the cardinality of the intersection of three samples. Then,

$$P(b_3=k) = \sum_{l=0}^{\min(a_1,a_2)} P(b_3=k \mid n, b_2=l, a_3) P(b_2 =l \mid n, a_1, a_2).$$

Find this for each $k \in \{0, 1, 2, \dots, \min(a_1,a_2,a_3)\}$. The latter calculation is not numerically difficult, because $P(b_2 = l \mid n, a_1, a_2)$ is simply the result of the previous calculation and $P(b_3 = k \mid n, b_2=l, a_3)$ is an invocation of the hypergeometric distribution.

In general, to find $P(b_m)$ you can apply the following recursive formulas: $$P(b_i=k) = \sum_{l=0}^{\min(a_1, a_2, \dots, a_{i-1})} P(b_i = k \mid n, b_{i-1}=l, a_i) P(b_{i-1}=l),$$ $$P(b_i = k \mid n, b_{i-1}=l, a_i) = \frac{{l \choose k} {n-l \choose a_i - k}} {n \choose a_i},$$ for $i \in \{2, 3, \dots, m\},$ and $$P(b_1) = \delta_{a_1 b_1},$$ which is just to say that $b_1 = a_1.$

Here it is in R:

hypergeom <- function(k, n, K, N) choose(K, k) * choose(N-K, n-k) / choose(N, n)

#recursive function for getting P(b_i) given P(b_{i-1})
PNext <- function(n, PPrev, ai, upperBound) {
l <- seq(0, upperBound, by=1)
newUpperBound <- min(ai, upperBound)
kVals <- seq(0, newUpperBound, by=1)
PConditional <- lapply(kVals, function(k) {
hypergeom(k, ai, l, n)
})
PMarginal <- unlist(lapply(PConditional, function(p) sum(p * PPrev) ))
PMarginal
}

#loop for solving P(b_m)
P <- function(n, A, m) {
P1 <- c(rep(0, A[1]), 1)
if (m==1) {
return(P1)
} else {
upperBound <- A[1]
P <- P1
for (i in 2:m) {
P <- PNext(n, P, A[i], upperBound)
upperBound <- min(A[i], upperBound)
}
return(P)
}
}

#Example
n <- 10
m <- 5
A <- sample(4:8, m, replace=TRUE)
#[1] 6 8 8 8 5

round(P(n, A, m), 4)
#[1] 0.1106 0.3865 0.3716 0.1191 0.0119 0.0003
#These are the probabilities ordered from 0 to 5, which is the minimum of A

• Thanks for your solution, and your code. I wait for other answers approaches (if they come) before awarding the bounty. – llrs Mar 8 '18 at 8:50