CSC 789 Assignment 4

Due date, October 19, 2004, 5:30 PM.

  1. The "Coupon Collector's Problem."

    The expected waiting time is generally defined to be the expected value of the time it takes for a given event to occur. In this problem, a customer is given a "coupon" with a random number from 1 to n each day, and the given event is that the customer has collected at least one coupon for each number. A more formal definition is given below.

    Let n be a positive integer. Let X1, X2, ... be a sequence of independent random variables, where each Xi is uniformly distributed among the integers 1, ... n. Let T be the smallest number such that, for each i from 1 to n, there is at least one Xt = i, for some t <= T.

    What is the expected value of T, in terms of n? I want an exact answer. The answer will include a Harmonic number in the formula.

    As a hint to the above problem, prove the following Lemma: If the probability that a boolean random variable Yi is true is p for each i, and the values are independent, then the expected waiting time for the first "true" is 1/p.

    For example, if your chances of winning the lottery are one in a billion, and you play once a week, your expected waiting time to win the lottery is a billion weeks. (That's almost 20 million years, but it's certainly worth waiting for!)

Back to Course Page