Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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).

share|improve this question
$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

1 Answer 1

up vote 0 down vote accepted

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?"

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.