10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Bridgeburners Mar 7 '18 at 21:23
  • $\begingroup$ @Bridgeburners A recipe would be nice, at least it would provide some method/way of attacking this problem and related. $\endgroup$ – llrs Mar 7 '18 at 21:39
3
$\begingroup$

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 \begin{equation} \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). \end{equation} 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 \begin{equation} | \mathcal{C}'(I) | = \prod_{i = 1}^{n} \binom{|S| - |I|}{a_{i} - |I|}. \end{equation}


Now our original probability can be expressed via the $\mathcal{C}$ as follows: \begin{equation} 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) | }. \end{equation}

We can make two simplifications here right away. First, the denominator is the same as \begin{equation} | \mathcal{C}'(\emptyset) | = \prod_{i = 1}^{n} \binom{|S|}{a_{i}} = \prod_{i = 1}^{n} \binom{n}{a_{i}}. \end{equation} 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 \begin{equation} \sum_{I : |I| = k} | \mathcal{C}(I) | = \binom{n}{k} | \mathcal{C}(I_{0}) |, \end{equation} 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 \begin{equation} | \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}. \end{equation}


Let $J_{1}, \ldots, J_{n - k}$ be the distinct subsets of $S$ formed by adding exactly one element to $I_{0}$. Then \begin{equation} \mathcal{C}(I_{0}) = \mathcal{C}'(I_{0}) \setminus \biggl( \bigcup_{i = 1}^{n - k} \mathcal{C}'(J_{i}) \biggr). \end{equation} (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 \begin{equation} | \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|. \end{equation}


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 \}$, \begin{equation} \bigcap_{i \in \mathcal{I}} \mathcal{C}'(J_{i}) = \mathcal{C}' \biggl( \bigcup_{i \in \mathcal{I}} J_{i} \biggr). \end{equation} 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 \begin{equation} | \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} \end{equation} as claimed.

$\endgroup$
  • $\begingroup$ +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 $\endgroup$ – llrs Mar 12 '18 at 11:07
4
+50
$\begingroup$

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
$\endgroup$
  • $\begingroup$ Thanks for your solution, and your code. I wait for other answers approaches (if they come) before awarding the bounty. $\endgroup$ – llrs Mar 8 '18 at 8:50

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.