M balls and N boxes

Problem: There are M balls and N boxes. Each ball is randomly placed into a box. What is the expected number of boxes that have at least one ball inside?

Solution: We can create a series of identification variables, Ii, which denotes for the i th box, if there is at least one ball inside. If yes, Ii = 1, otherwise Ii = 0. Then our problem is to calculate the expected value to I, where I = I1 + I2 + ... + IN. There is symmetric here, so E(I) = N*E(Ii) = N*(1-(N-1/N)^M)

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

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