Probstat/coupon practice

This is part of probstat and Probstat/week6 practice 2.

Please watch the 1st clip (part 1), and think about how to use the balls-and-bins experiment to analyze the coupon collector's problem before watching the 2nd clip (part 2). If you have tried to use the approach we used to analyze the fullest bin to find the upperbound for the number balls, please proceed on this page.

Analysis on the probability

Use the approach that we analyze the fullest bin to find the upper bound on the probability that we throw k balls into n bin and there exists some bin which is empty.

Hint: Try define an appropriate event B_i for bin i.

Computing the expectation

Please watch the 2nd clip on the coupon collector's problem before attempting this section.

Consider the following experiment: we throw a ball randomly into n bins. We keep throwing a ball until there is no empty bins.

Let random variable X denote the number of balls that we throw.

Find E[X].

Hint questions:

• Suppose that we have already got n-1 different coupons.
  • What's the probability that we get the last coupon when we buy a new box of candies?
  • Suppose that you have got n-1 different coupons. What is the expected number of boxes that we have to buy to get the last coupon?
• Suppose that we have already got n-2 different coupons.
  • What's the probability that we get the (n-1)-th new coupon after buying one box of candies?
  • Suppose that you have got n-1 different coupons. What is the expected number of boxes that we have to buy to get the (n-1)-th new coupon?