0
$\begingroup$

If I randomly pick 80 cards, uniformly, from a standard 52-card deck, with replacement, what is the probability that every card is drawn at least once?

I understand that to tackle this question, I will most probably need to use Inclusion/Exclusion, however, I'm not entirely sure how to solve this.

Any help would be greatly appreciated.

$\endgroup$
2
$\begingroup$

Someone else asked a similar question a little while after this one. I'm modifying and reposting my answer from there to here. I've also added an example since it's early in the morning and the baby is still sleeping.

The short answer is $$\frac{{80\brace52}52!}{52^{80}}.$$

Explanation: Suppose we have a deck of $k$ cards, say $C=\{c_1,c_2,\ldots, c_k\}$, and we draw, with replacement, $n\geq k$ of them. Let $(d_1,\ldots, d_n)$ be the sequence of draws (so each $d_j\in C$). I'll call this a drawing.

Obviously there are $k^n$ possible drawings.

In how many drawings is each card chosen at least once? I'll call these good drawings. Well, let $(d_1,\ldots, d_n)$ be a drawing and suppose we have $k$ buckets labelled $\{c_1,c_2,\ldots, c_k\}$. Place $d_j$ into bucket $c_i$ when $d_j=c_i$. Then we know that the drawing is good if and only if each bucket is non-empty.

Now, suppose we have $k$ identical buckets and place symbols $\{D_1,\ldots, D_n\}$ into the buckets, making sure that each bucket gets at least one symbol. We make the convention that two such placements are the same if the buckets can be rearranged to get one from the other. By the definition of the Stirling number of the second kind, there are ${n\brace k}$ ways of doing this. Next, label the buckets with labels $\{c_1,\ldots,c_k\}$. There are $k!$ ways of doing this.

For each of the above placements and labellings, we can then define a good drawing $(d_1,\ldots, d_n)$ by setting $d_j=c_i$ if and only if $D_j$ was placed in bucket labelled $c_i$.

Thus there are exactly ${n\brace k}k!$ good drawings and so the probability that a drawing is good is $$\frac{{n\brace k} k!}{k^{n}}.$$

Example with a deck of $k=2$ cards, say $\{0,1\}$, and $n=3$ draws. In this case a drawing is simply a binary sequence of length 3, and clearly only $(1,1,1)$ and $(0,0,0)$ are not good drawings, so the probability should be $3/4$.

Now let $B_1$, and $B_2$ be the buckets. We want to put symbols $D_1,D_2,D_3$ into these and so there are ${3\brace 2}=3$ possibilities:

$D_1\in B_1, \{D_2,D_3\}\in B_2$ (which we consider the same as placing $D_1\in B_2$ and $\{D_2,D_3\}\in B_1$).

$D_2\in B_1, \{D_1,D_3\}\in B_2$,

$D_3\in B_1, \{D_1,D_2\}\in B_2$.

If $B_1$ is labelled $1$ and $B_2$ is labelled $0$ we get the drawings $(1,0,0)$, $(0,1,0)$ and $(0,0,1)$. The other labeling gives the drawings $(0,1,1)$, $(1,0,1)$ and $(1,1,0)$. As noted above, this is indeed all good drawings in this case and the probability of getting a good drawing is $$\frac{{3\brace 2}2!}{2^3} = \frac{3}{4}.$$

$\endgroup$
-1
$\begingroup$

Hint: Think of the following situation:

  1. You need to pick a specific card from a set of 52 cards. By specific, I mean choose a card in advance. What would be the probability of picking the card?

  2. Do this 52 times, and make sure all the 52 cards are chosen. You can do this by not replacing the card picked before. You thus get a probability of choosing 52 different cards.

  3. The remaining 28 cards can be picked without any restrictions. So, it would be just ${52 \choose 28} (\frac {1}{52})^{28} (\frac {51}{52})^{24}$.

Multiply the answer from 3 and 2 to get final answer.

$\endgroup$
  • $\begingroup$ Well, if the events take place without replacement, the probability will be 1. $\endgroup$ – user98380 Oct 6 '13 at 7:28
  • $\begingroup$ For 2, I assume it would be $(\frac {1}{52})^{52}$. Is this correct? $\endgroup$ – user98380 Oct 6 '13 at 9:47
  • $\begingroup$ $\frac{1}{52}.\frac{1}{51}.\frac{1}{50}....\frac{1}{2}.\frac{1}{1} = \frac{1}{52!}$ This is true because we want different card each time. So we do not consider the card(s) we picked before. $\endgroup$ – math Oct 6 '13 at 10:17
  • $\begingroup$ This is on the assumption that there is no replacement; correct? $\endgroup$ – user98380 Oct 7 '13 at 1:59
  • $\begingroup$ This is wrong. The $52$ different cards can be picked at any time, not necessarily as the first $52$. And the expression in $3$. isn't the number of ways of picking $28$ cards without restrictions. $\endgroup$ – joriki May 14 '16 at 5:58

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.