# Variation of Coupon Collectors Problem, involving N Cereal Boxes and 6 Prizes

Suppose boxes of cereal are filled with a random prize, each drawn independently and uniformly from 6 possible prizes. If N boxes of cereal is bought, what is the expected number of distinct prizes that will be collected?

Hint: Use indicator random variables.

Comments: The question being asked is worded a bit strange. My initial thought was to find N, but with the helpful hints below, I now understand what the question is asking (Thank you all).

-
$N$ is a constant; they're asking for $E(P)$, where $P$ is the (random variable describing the) number of types of prizes you got. There is no value of $N$ for which $P=6$ (or even $E(P) = 6$). –  Hurkyl Mar 21 '13 at 0:49
Oh, I understand now. I'm having trouble starting though. How may I go about thinking how to solve this problem? –  Sol Bethany Reaves Mar 21 '13 at 0:52

Label the boxes $1$ to $N$.

Let $X_i=1$ if the $i$-th box has a "new" prize, that is, a prize not contained in any box $j$ with $j\lt i$.

Let $X=X_1+X_2+\cdots +X_N$.

Then $X$ is the total number of distinct prizes.

We want $E(X)$. The expectation of a sum is the sum of the expectations, so we will be finished if we can find $E(X_i)$ for each $i$.

We will know $E(X_i)$ once we know $\Pr(X_i)=1$. Perhaps divide into disjoint cases. The prize in the $i$-th box could be any of $P_1,P_2,\dots,P_6$.

Whatever it is, what is the probability that it is "new?"

-
The probability for each "new" prize would decrease for every new discovery. For the first one, for instance, the probability that we get a "new" toy is 1, because it is the first one we see, but now the probability of the next "new" prize is 5/6 and the probability of the next prize being the same as the one we already collected is 1/6. Continuing down, the probability for the third "new" prize is 4/6 and the probability for the third prize being the same one we've seen before is 2/6. And the pattern continues. But how to get going from here? –  Sol Bethany Reaves Mar 21 '13 at 1:31
Yes, at $1$ it is $1$. Now let's go directly to any $i\gt 1$, like $17$. Whatever we get at $17$, it is new iff we didn't see it in rounds $1$ to $16$, which has probability $\left(\frac{5}{6}\right)^{16}$. Please tell me if on thinking about it things are still unclear. –  André Nicolas Mar 21 '13 at 1:47
Unfortunately I still have questions on this. On your most recent example (5/6)^16, is that assuming that we got the SAME prize from rounds 1 to 16 then since 5/6 means 5 choices left to choose from 6? –  Sol Bethany Reaves Mar 21 '13 at 1:53
Suppose the prize we got in box $17$ was a $1000$ dollar bill. What is the probability we did not get a $1000$ dollar bill in any of the first $16$ boxes? In any box, the probability we don't have a $1000$ dollar bill is $\frac{5}{6}$. The probability this happens $16$ times in a row is $(5/6)^{16}$. Basically all I am doing is the probability that on tossing a die $16$ times in a row, we never get a $4$. –  André Nicolas Mar 21 '13 at 1:58
Ok, I understand what you did there. Thank you for being thorough. –  Sol Bethany Reaves Mar 21 '13 at 2:20