Suppose there are n types of toys, which you are collecting one by one, with the goal of getting a complete set. When collecting toys, the toy types are random (as is sometimes the case, for example, with toys included in cereal boxes or included with kids’ meals from a fast food restaurant).
Assume that each time you collect a toy, it is equally likely to be any of the n types. What is the expected number of toys needed until you have a complete set?
Solution: Let N be the number of toys needed; we want to find E(N). Our strategy will be to break up N into a sum of simpler r.v.s so that we can apply linearity. So write
N = N1 + N2 + · · · + Nn,
where N1 is the number of toys until the first toy type you haven’t seen before (which is always 1, as the first toy is always a new type), N2 is the additional number of toys until the second toy type you haven’t seen before, and so forth.
with