# Probability that m samples without replacement cover the entire set

Let $n$ be the size of the set $S = \{s_1, s_2, ..., s_n\}$ of unique items. Let $m$ be the number of players $p_1, p_2, ..., p_m$. Each player draws $k < n$ items from the set $S$ without replacement and with uniform probability, forming their own subset $p_i = \{p_{i, 1}, p_{i, 2}, ..., p_{i, k} \}$. Each player draws their item iid, so different players can hold the same item.

Given the size of the set $n$, the number of players $m$, and the sample size of each player $k$, what is the probability that the union of the sets of all the $m$ players cover the entire set $S$? i.e. that $p_1 \cup p_2 \cup ... \cup p_m = S$?

I'm not sure if this is a solved problem or not, so any analysis of the probability would also be appreciated (e.g. approximations, lower/upper bound, asymptotic behaviors)! Solutions other than closed form are also appreciated (e.g. recursive, polynomial-time algorithm).

• What is $N$? And what is the relation between $m,n,k$? (for instance, if $mk < n$, the probability is $0$) – Clement C. Mar 11 '18 at 21:37
• Inclusion/Exclusion should give a way to proceed. Start with $1$, subtract the probability that some specified element is uncovered, add the probability that two specified elements are uncovered, and so on. (Note: I am assuming that $N=n$. In any case, that should be clarified). – lulu Mar 11 '18 at 21:47
• Sorry, by $N$ I meant $n$, let me edit my post to fix that. I'm hoping to find non-trivial answers, so $mk < n$ would be another good bound! – user3667125 Mar 11 '18 at 22:09
• @lulu That was my first intuition... but I think finding the probability that some number of elements are uncovered is hard! I couldn't find a mathematical solution to it after spending a few days thinking, nor a polynomial-time algorithm to compute it for large values of $n$, $m$, and $k$. Any hints or ideas? edit: I do note that when $k=1$ and $m=n$, the probability becomes $\frac{n!}{n^n}$. – user3667125 Mar 11 '18 at 22:14
• If you fix $r$ elements, the probability that a given player misses all of them is $\binom {n-r}k /\binom nk$ where the numerator is understood to be $0$ if $n-r<k$. – lulu Mar 11 '18 at 22:56

Fix $r$ elements in the set $S$. The probability that one player does not sample any of those $r$ elements is $\binom{n-r}{k}/\binom{n}{k}$. The probability that all $m$ players do not sample those $r$ elements is $(\binom{n-r}{k}/\binom{n}{k})^m$.
There are $\binom{n}{r}$ such ways to choose those $r$ elements. Therefore the probability that all the players do not sample any arbitrary set of $r$ elements is $(\binom{n-r}{k}/\binom{n}{k})^m \binom{n}{r}$. Let $P(r) = (\binom{n-r}{k}/\binom{n}{k})^m \binom{n}{r}$
Due to the principle of inclusion/excluson, the probability that all the players can cover the entire set $S$ is: $P^* = 1 - P(1) + P(2) - ... + (-1)^{n-k}P(n-k)$ $= 1 + \sum_{i=0}^{n-k} (-1)^i (\binom{n-i}{k}/\binom{n}{k})^m \binom{n}{i}$
Note that we don't consider the probability of missing more than $n-k$ items, since those probabilities will be $0$.