Question

A big chain grocery store was giving away domino pieces for every 20 CHF one spends from September until Nov. 2. These domino pieces have flags of Swiss Cantons and half Cantons. Suppose we now aim to collect all flags of Swiss Cantons and half Cantons. This is equivalent to the coupon collector’s problem: Coupons in this context map to the dominos with flags of Swiss Cantons and half cantons, and are being collected with replacement.

Let T be the time to collect all n = 36 dominos. Let Ti be the time to collect the i-th new domino after i − 1 unique dominos have been collected. The key for solving the problem is to understand that it takes very little time to collect the first few dominos. On the other hand, it takes a long time to collect the last few new dominos. Note that T1 = E[T1] = 1.

(a) Compute the probability of collecting a domino with a new flag given that i − 1 unique ones have been collected.

(b) What is the distribution of Ti?

(c) Compute the expected value E(Ti).

(d) Compute E(T).

Thank you,

Answer 1

GEOMETRIC DISTRIBUTION:

the geometric distribution is either of two discrete probability distributions:

• The probability distribution of the number X of Bernoulli trials needed to get one success, supported on the set { 1, 2, 3, ... }
• The probability distribution of the number Y = X − 1 of failures before the first success

The geometric distribution gives the probability that the first occurrence of success requires k independent trials, each with success probability p. If the probability of success on each trial is p, then the probability that the k th trial (out of k trials) is the first success is

for k = 1, 2, 3, ....