How many times I need to draw k items from a list of n items to get a probability P that each item is selected at least once? [duplicate]

Question

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?

Answer 1

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