Coupon collecting.

•
n coupon types. Get a random one each round. How long to get all coupons?
•
general example of waiting for combinations of events to happen.
•
expected case analysis:
–
after get k coupons, each sample has 1 − k/n chance for new coupon
–
so wait for (k + 1)st coupon has geometric distribution.
–
expected value of geo dist w/param p is 1/p
–
so get harmonic sum
–
what standard tools did we use? using conditional expectation to study on phase; used linearity of expectation to add
–
expected time for all coupons: n ln n + O(n).