a.) There are $4$ distinct items in the set. What is the probability of picking all $4$ items after picking $n\ge4$.
b.) How many items do you need to pick to collect all four with a probability of at least $.9$.

My answer for part a. (which I think is wrong):
The sample space is the all the possible ways of picking $n$ items from the set of $4$ items. That number is equal to the number of non negative integer-valued solutions to this problem:
that number is $\binom{n+4-1}{4-1}=\binom{n+3}{3}$

All possible ways of picking $n$ items and having at least 1 of each of the $4$ items is the number of positive integer-valued solutions to this problem:
That number is $\binom{n-1}{4-1}=\binom{n-1}{3}$

So the probability of picking all $4$ items after picking $n$ items is:

Using this answer, I find that the probability of picking all $4$ items after picking $4$ random items is:

Please explain where I went wrong.

  • $\begingroup$ See this thread from the Wikipedia math reference desk. $\endgroup$ – Ilmari Karonen Oct 3 '11 at 16:46
  • 2
    $\begingroup$ The problem is incompletely specified. Is the following equivalent? We have a $4$-sided fair die, faces labelled $1$, $2$, $3$, $4$. Toss $n$ times. What is probability that after $n$ tosses we have obtained each side at least once? $\endgroup$ – André Nicolas Oct 3 '11 at 16:49
  • $\begingroup$ @AndréNicolas Yes, what you said is equivalent to my problem. $\endgroup$ – jamesio Oct 3 '11 at 17:05

The original problem is incompletely specified. And one problem with a "stars and bars" approach is that not all solutions are equally likely, making the calculation of probabilities very difficult.

We consider the following equivalent situation. An experiment consists of picking one of the digits $1$, $2$, $3$, $4$, with each choice equally likely. (a) If we perform this experiment $n$ times, what is the probability that we have chosen each of $1$, $2$, $3$, $4$ at least once? (b) What is the smallest $n$ such that if we perform the experiment $n$ times, the probability of having picked each digit at least once is at least $0.9$?

For (a), represent the result of the $n$ experiments as a word of length $n$ over the alphabet $\{1,2,3,4\}$. There are $4^n$ such words, all equally likely. Now we count the words that have all four digitss. As is often the case, it is a little easier to count the complement, the words in which not all of $1$, $2$, $3$, and $4$ appear.

To do this, we will use Inclusion-Exclusion. The number of words that do not have a $1$ is $3^n$. So is the number of words that do not have a $2$, and so on. Add up, for a total of $4\cdot 3^n$. This doesn't quite work, since we have double counted, for example, the words that have neither a $1$ nor a $2$. There are $2^n$ of these. But there are $\binom{4}{2}=6$ double counted patterns. This gives us the estimate $4\cdot 3^n -6\cdot 2^n$ for the number of words with at least one missing digit. However, we have subtracted once too many times the words with just the digit $1$, or just $2$, and so on. So the total number of words with at least one missing digit is $$4\cdot 3^n -6\cdot 2^n +4\cdot 1^n.$$ It follows that the required probability is $$1 -\frac{4\cdot 3^n -6\cdot 2^n +4\cdot 1^n}{4^n}.$$

(b) We want the smallest integer $n \ge 4$ such that $$\frac{4\cdot 3^n -6\cdot 2^n +4\cdot 1^n}{4^n} \lt 0.1.$$ The dominant term is $(4\cdot 3^n)/4^n$. A little calculator work shows that the smallest $n$ that works is given by $n=13$.


You disregarded the order of the picks, and this leads to an underestimation of the probability. Disregarding order, there's only one way to pick all $4$ times in $4$ picks, namely $1,2,3,4$. You're also disregarding the order in the denominator, but since many of the combinations being counted there contain one or more items more than once, there are fewer different ways of ordering them, so the effect of disregarding order is stronger in the numerator than in the denominator.

In your other solution, $\frac44\frac34\frac24\frac14$, you did take order into account: The numerator is the number of ordered ways of drawing one of each item, and the denominator is the number of ordered ways of drawing arbitrary items.

A good way to get things straight is often to look at as small as possible an example. In this case, think of just two items and two picks. Taking order into account, you see that you can pick either first $1$, then $2$ or first $2$, then $1$, and there are two more possibilities where you pick either $1$ or $2$ twice, so the probability of getting one of each item is $2/4=1/2$. Disregarding order, you'd get just one desired result, $(1,2)$, but three in total: $(1,1)$, $(1,2)$ and $(2,2)$. It's perhaps more obvious in this case that and why the first is the correct result.


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.