0
$\begingroup$

From a deck of 52 cards, we draw $N$ times one card, with the return. Calculate the probability that each card in the deck will be drawn at least once.

I know that it looks a bit like Coupon collector's problem, but as I understand it, it's about expected value and variance. Here I need to look the other way around - I am given N and have to calculate the probability.

For N < 52 that will be 0 of course.

Then, for N = 52 we have: $1 \cdot \frac{51}{52} \frac{50}{52} \cdot ... \cdot \frac{1}{52}$ as I need to get a 'new card' each time and that probability is smaller with each draw as the set of 'old' (already chosen) cards gets bigger.

For $N = 53$ I have $1$ 'extra draw' that I can loose on drawing an 'old' card - one of $52$. But I can't just choose one of $51$ places between draws extending the set of already chosen cards and choose one of $52$ cards. I think that I would calculate many times the same sequences.

Therefore I lack the idea for scaling the idea from $52$ draws onwards. Any help would be appreciated.

$\endgroup$
11
  • $\begingroup$ The answer is $\dfrac{52!\, S_2(N,52)}{52^N}$ where $S_2(N,52)$ is a Stirling number of the second kind. You can also use inclusion-exclusion or recursion to find it. math.stackexchange.com/questions/4506194/… is one of many similar questions on this site. $\endgroup$
    – Henry
    Commented Jun 16 at 0:21
  • $\begingroup$ @Henry thank you for help! Could you show me the inclusion-exclusion and recursion ideas? Provided link and the answer mention Stirling numbers of second kind and I would love to avoid those. $\endgroup$
    – thefool
    Commented Jun 16 at 1:27
  • $\begingroup$ My answer to the linked question gives a recursion if you replace $365$ days with $52$ cards. For an example of inclusion-exclusion see math.stackexchange.com/a/4813267/6460 using $m=52$ $\endgroup$
    – Henry
    Commented Jun 16 at 1:57
  • $\begingroup$ See this article for an introduction to Inclusion-Exclusion. Then, see this answer for an explanation of and justification for the Inclusion-Exclusion formula. $\endgroup$
    – user2661923
    Commented Jun 16 at 5:20
  • $\begingroup$ @Henry I see the recursion.If I replace 365 days with 52 cards I get: $p(N,m) = \frac{m}{52}p(N-1,m)+\frac{53-m}{52}p(N-1,m-1)$. But that is a recoursion on $N$ and $m$. In my case, I need compact function of $N$ (not including sums). $\endgroup$
    – thefool
    Commented Jun 16 at 17:30

1 Answer 1

Reset to default
1
$\begingroup$

To calculate the probability that each card in a deck of $52$ cards will be drawn at least once in $N$ draws with replacement, we can use the principle of inclusion-exclusion.

Let $A_i$​ be the event that the $i$-th card is not drawn in $N$ draws.

We want the probability that every card is drawn at least once, which is $\mathbb{P}(\bigcap_{i=1}^{52} A_i^c)$.

The probability of not drawing a specific card $i$ in a single draw is $1 − \frac{1}{52} = \frac{51}{52}$

The probability that card $i$ is not drawn in $N$ draws is $\left( \frac{51}{52} \right)^N$.

The principle of inclusion-exclusion allows us to calculate the probability that at least one of the events $A_i$​ occurs: $$\mathbb{P} \left( \bigcup_{i=1}^{52} ​A_i​ \right) = \sum_{i=1}^{52} ​\mathbb{P}(A_i​) − \sum_{1≤i<j≤52} \mathbb{P} (A_i​ \cap A_j​) + \sum_{1≤i<j<k≤52} ​\mathbb{P} (A_i​ \cap A_j ​\cap A_k​) − ...$$

For each $k$-subset of cards, the probability that all $k$ cards are not drawn in $N$ draws is: $$\mathbb{P} (A_{i_1}​​ \cap A_{i_2} \cap ... \cap A_{i_k}​​) = \left( \frac{52-k}{52} \right)^N$$

We can use inclusion-exclusion to find the probability that at least one card is missing, and subtract this from $1$ to get the probability that every card is drawn at least once.

Finally:

$$\mathbb{P}(\text{each card drawn at least once}) = 1 − \mathbb{P}(\text{at least one card is missing})$$

$$\mathbb{P}(\text{each card drawn at least once}) = 1 − \sum_{k=1}^{52} ​(−1)^{k+1} {{52}\choose{k}} \left( \frac{52-k}{52} \right)^N$$

$\endgroup$
2
  • $\begingroup$ +1 to your accurate and valid answer. My only constructive criticism is to suggest that in general with such problems, you (alternatively) express the probability as something like $~\dfrac{A}{D} ~: ~D = (52)^N.~$ So, you compute $~A~$ combinatorically, using Inclusion-Exclusion, bypassing any considerations of probability, thus (arguably) making things easier on yourself. You might end up with something like $$A = \sum_{k=0}^{52} (-1)^{k} \binom{52}{k} (52-k)^N.$$ $\endgroup$
    – user2661923
    Commented Jun 17 at 4:47
  • $\begingroup$ See also this answer for an explanation of and justification for the Inclusion-Exclusion formula. $\endgroup$
    – user2661923
    Commented Jun 17 at 4:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .