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).

  • $\begingroup$ What is $N$? And what is the relation between $m,n,k$? (for instance, if $mk < n$, the probability is $0$) $\endgroup$ – Clement C. Mar 11 '18 at 21:37
  • $\begingroup$ 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). $\endgroup$ – lulu Mar 11 '18 at 21:47
  • $\begingroup$ 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! $\endgroup$ – user3667125 Mar 11 '18 at 22:09
  • $\begingroup$ @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}$. $\endgroup$ – user3667125 Mar 11 '18 at 22:14
  • $\begingroup$ 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$. $\endgroup$ – lulu Mar 11 '18 at 22:56

With the help of @lulu I found this closed form solution:

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


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.