Exercise 2 (20 points):
Some years ago, greek video-club chain Seven had the following offer to their customers: every time a customer rented a DVD, he was given a random coupon with the title of the Academy awards (Oscars) winner movie written on it. The first person to gather the coupons with all the unique winner-movie titles won a 10-day vacation on a Caribbean island. If at that time, there were 75 unique such titles, and these titles were uniformly assigned to coupons, find the expected number of DVDs one had to rent in order to gather all of them.
The above problem can be seen as a random sampling problem from sample space S{1,2,3,4,5......n}
Selecting a number randomly from S would be same as receiving a unique coupon.
Let \(X_n\) be the minimum DVDs that need to be rented to receive all the coupons at least once.Here n is the number of coupons
we can define \(Xn\ \) as
\(X_{n=}C_1+C_2+......+C_i+...+C_n\) --eq1 [Total dvds to be bought=sum of dvds to be bought for each coupon]
Where \(C_i\) gives the additional number of dvds to be bought to get the coupon that is different from i-1 other coupons.
eg. \(C_4\), is the number of dvds to be bought to get a coupon that is different than 3 other coupons.
Since each calculation for \(C_i\) requires sampling till a particular unique selection is made , therefore it resembles a geometric random variable.
The probability of finding a unique coupon keeps on decreasing with increasing value of i.
The probability of finding ith distinct coupon can be given as \(p=\frac{\left(n-\left(i-1\right)\right)}{n}\)
Using the formula for the mean of a geometric random variable we can define it as below
Using equation 1 and 2
\(\Rightarrow E\left[X_n\right]=n\left[\frac{1}{n}+...+\frac{1}{2}+1\right]\)
\(\Rightarrow E\left[X_n\right]=n.H_n\)