Probability that all cards have been drawn [duplicate]

Question

Let's say, I have a deck of $m$ cards from which I will draw $n$ cards at random, watch them and put them back in the deck. I want to know; what is the change after $k$ draws, that I have seen all cards in the deck.

It is actually a variant to the problem described here, however in this and this case the number of items per draw is only one.

simulation

I made a simulation where the decksize is 10 and the number of cards each draw is 4, the results are plotted below (here's the python code).

personal attempt

I only got to the point to calculate the probability that a single card is not in a single draw:

$\displaystyle P = (1 - \frac{1}{m})(1 - \frac{1}{m-1})(1 - \frac{1}{m-2})(1 - \frac{1}{m-3}) = \sum_{i=1}^n (1 - \frac{1}{m-i+1}) $

Answer 1

I think the solution would go something like this:

Let $P(m, n, k, x, y)$ be the probability of seeing exactly $x$ cards at least once over $k$ draws, once $y$ cards have already been seen.

Then $P(m, n, k, x, 0) = \sum_{i=0}^{x}P(m, n, k-1, x-i, 0) * P(m, n, 1, i, x-i)$

I think the possibilities under the sum sign are all unique, so we can sum them.

Your solution is then $P(m, n, k, m, 0)$. What is left is to define $P(m, n, 1, i, x-i)$ and we should be able to solve the problem recursively.

Edit: full solution in Python, implementing the method above:

import numpy as np
from scipy.special import comb
import matplotlib.pyplot as plt
m = 10
n = 4
def P(k, x, y):
    if k == 1:
        return (comb(m-y, x) * comb(y, n-x))/comb(m, n)
    else:
        prob = 0
        for i in range(x):
            prob += P(k-1, x-i, y) * P(1, i, y+x-i)
        return prob

def P_MC(k, x, y):
    sims = 10000
    good = 0
    for s in range(sims):
        ar = np.arange(m)
        seen = set(np.arange(y))
        for draw in range(k):
            np.random.shuffle(ar)
            for el in ar[:n]:
                seen.add(el)
        if len(seen) == (x+y):
            good += 1
    return good/sims

ests = []
acts = []
for k in range(1,16):
    ests.append(P_MC(k, m, 0))
    acts.append(P(k, m, 0))

plt.plot(range(1,16), ests)
plt.plot(range(1,16), acts)
plt.grid()
plt.legend(['Simulated', 'Actual'], loc='lower right')

Answer 2

This is a simple variant of the coupon collector's problem, which uses the classical occupancy distribution. Let $K$ be the number of distinct cards that have been drawn, distributed according to the classical occupancy distribution. With $m$ distinct cards in the deck, and $n \geqslant m$ random draws with replacement, the probability of drawing each card at least once is:

$$\mathbb{P}(\text{All cards drawn}) = \mathbb{P}(K=m) = \frac{m! \cdot S(n,m)}{m^n},$$

where the function $S$ denotes the Stirling numbers of the second kind. This can be written in explicit form as:

$$\mathbb{P}(K=m) = \sum_{i=0}^m (-1)^i {m \choose i} \bigg( 1-\frac{i}{m} \bigg)^n.$$