How many bags would need to be bought to have all the red noses?

Question

There are 9 types of Red Noses, for comic relief this year:

Each one is sold in an opaque packet, so it is lucky dip which one you will get.

Assuming there is the same amount of each type (${1\over9}$^th). On average, how many bags would need to be bought for someone to get all 9 of them?

Answer 1

---

I'm going assume that there are, effectively, infinite bags of noses—if we only had 9 bags... well, you get it. ;)

Say we have $n-1$ of the $9$ unique noses. The probability of getting a new style of nose on the next bag is $p_n = 1 - \frac{n-1}{9}$. Then, on average, it takes $\frac{1}{p_n}$ bags to get the next unique nose. (i.e. - Say we have $0$ unique noses. Then, $n = 1$ and $p_n = 1 - \frac{0}{1} = 1$ and it will take only one bag to get a new nose. Similarly, if we have $4$ nose-styles, $n = 5$ and it will take $1 - \frac{4}{9} = \frac{9}{5}$ bags to get a $5^{\text{th}}$ nose.)

The probabilities here are independant. That is, the chance of getting the $5^{\text{th}}$ new nose on the next bag doesn't depend on the chance of getting the $4^{\text{th}}$ one (once you have the $4^{\text{th}}$ nose, the probability of getting the $5^{\text{th}}$ will always be $\frac{1}{p_5}$). Thus, we can just sum the average of each $p_n$ until $n = 9$.

So, we have: $$\frac{1}{p_1} + \frac{1}{p_2} + \frac{1}{p_3} + \frac{1}{p_4} + \frac{1}{p_5} + \frac{1}{p_6} + \frac{1}{p_7} + \frac{1}{p_8} + \frac{1}{p_9} + = \\ 1 + \frac{9}{8} + \frac{9}{7} + \frac{9}{6} + \frac{9}{5} + \frac{9}{4} + \frac{9}{3} + \frac{9}{2} + \frac{9}{1} = \\ 9 \sum_{n=1}^{9} \frac{1}{n} = \frac{9 \times 7129}{2520} = 25.46$$

That is, on average, it'd take about 25 bags to get all nine noses.

Answer 2

The trick to this problem is that the first few bags almost certainly are mostly different noses.

With absolute certainty, you only need to buy one bag to have one type of nose in your collection. To collect two types of noses, you need to buy at least two bags, but there is a probability $\frac89$ that you only need to buy two bags. The expected number of bags you have to buy in order to acquire the second type of nose, after you already have one type of nose, is $\frac98$.

The expected number of bags you have to buy to get the next type of nose only gets to be more than $2$ when you already have most of the noses. When you get to $7$ types of nose, you have a $\frac29$ chance to get a new kind of nose with each bag you buy, so the expected number of bags to get from $7$ types of nose to $8$ types of nose is $4.5$. After that the expected number of bags required to find the last type of nose is $9$ bags.

Add up $1 + \frac98 + \frac97 + \frac96 + \frac95 + \frac94 + \frac93 + \frac92 + 9$ and see what you get.