1
$\begingroup$

This question already has an answer here:

I have seen a few related questions but not exactly what I am looking for (in particular this and this) I think. I may be missing something since I am only a beginner at these counting problems.

I am trying to calculate the amount of times (experiments) I need to perform were I choose $k$ items from a list of $n$ items so that I have a probability $P$ that each of the n items was selected at least once.

I attacked the problem by starting small and saying I have 5 items and each experiment consists of drawing two of them (without replacement). After the first experiments I reasoned that I have 100% probability that there are 3 items not selected yet. I proceeded to calculate the probability that after the second experiment I have three, two, or one items not selected. And so on with the third experiment and more.

Unfortunately, I am having trouble generalizing this approach to $n$ and $k$ and to a number of experiments $m$.

I suspect there is a good chance that this is a duplicate. If so can someone please point me in the right direction?

$\endgroup$

marked as duplicate by whuber probability Sep 1 at 13:36

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ This is with replacement? $\endgroup$ – Art Sep 1 at 2:13
  • $\begingroup$ Each experiment consists of picking k elements without replacement. But every time a new experiment begins we start with the same n items. $\endgroup$ – LasEspuelas Sep 1 at 2:31
1
$\begingroup$

We could find the probability of not having some items selected at all after the experiment, for a given $m$. For a chosen set of $x$ items, the probability of not having selected them at all after $m$ draws is $$p_x=\left(\frac{{n-x \choose k}}{{n \choose k}}\right)^m$$ There are ${n\choose x}$ ways of choosing these $x$ isolated items, for $1\leq x\leq n-k$. And, the probability can be calculated using Inclusion-Exclusion principle, because once we consider two distinct items, we include the case where they're isolated together twice, which goes on similarly for pairs, triples etc. applying IE principle, we'd have: $$p=\sum_{x=1}^{n-k}(-1)^{x+1}{n\choose x}p_x$$

I don't know/see how this can be reduced further, but below is a Matlab simulation that supports the above claim:

n = 9; k = 4; m = 6; p = 0;
for x = 1:n-k
    p = p + (-1)^(x+1) * (nchoosek(n-x,k)/nchoosek(n,k))^m ...
        * (nchoosek(n,x));
end

N = 10^6; s = 0;
for it = 1:N
    arr = false(1,n);
    for i = 1:m
        arr(randperm(n,k)) = true;
    end
    s = s + (sum(arr) ~= n);
end

s/N, p
$\endgroup$
  • 2
    $\begingroup$ Please see the duplicate for formulas. $\endgroup$ – whuber Sep 1 at 13:37

Not the answer you're looking for? Browse other questions tagged or ask your own question.