How many boxes you need to have in order to collect all the toys?

Problem: Mike likes potato chips and also like the free toys piggybacked with the chips. There are N different toys in total. In each box of potato chips, there will only be one toy and the type of the toy is randomly decided. If Mile wants to collect all the N different toys, how many boxes of chips he needs to buy (on average)?


Solution: We can solve the problem by using Geometric Distribution. After we had collected i-1 toys ( i <=N), the number of  boxes we should get in order to get the i th toy conforms to a geometric distribution. The probability for the geometric distribution is (N-i+1)/N, thus the expected number of boxes to get the i th toy is N/(N-i+1). Then we can construct a random variable X and X = X1 + X2 + ... + XN, where Xi means the number of  boxes we should get in order to get the i th toy when we already have i-1 different toys. So E(X) = E(X1) + E(X2) + ... + E(XN) = N/N + N/N-1 + ...... + N/1 = N*(1/N + 1/(N-1) + ... + 1)

Related: Coupon collector's problem, M balls and N boxes