Question

Question: There are \(n\) different types of collectible cards you can get as prizes when you buy a particular product. Suppose that every time you buy this product it is equally likely that you get any type of these cards. Let \(X\) be the random variable equal to the number of products that need to be purchased to obtain at least one of each type of card and let \({X_j}\) be the random variable equal to the number of additional products that must be purchased after \(j\) different cards have been collected until a new card is obtained for \(j = 0,1, \ldots ,n - 1.\)

a) Show that\(X = \sum\limits_{j = 0}^{n - 1} {{X_j}} \).

b) Show that after\(j\)distinct types of cards have been obtained, the card obtained with the next purchase will be a card of a new type with probability\(\left( {n - j} \right){\rm{ }}/{\rm{ }}n.\)

c) Show that\({X_j}\)has a geometric distribution with parameter\(\left( {n - j} \right){\rm{ }}/{\rm{ }}n.\)

d) Use parts (a) and (c) to show that\(E(X) = n\sum\limits_{j = 1}^n 1 /j\).

e) Use the approximation\(\sum\limits_{j = 1}^n 1 /j \approx \ln n + \gamma \), where\(\gamma = 0.57721 \ldots \)is Euler's constant, to find the expected number of products that you need to buy to get one card of each type if there are 50 different types of cards.

Short answer

Answer

a)\(X = \sum\limits_{j = 0}^{n - 1} {{X_j}} \)

b)\(P\left( {{X_j} = 1} \right) = \frac{{n - j}}{n}\)

c)\(P\left( {{X_j} = k} \right) = {\left( {\frac{j}{n}} \right)^{k - 1}}\frac{{(n - j)}}{n}\)

d)\(E(X) = n\sum\limits_{j = 1}^n {\frac{1}{j}} \) .

e) \(224.5\)

Step-by-step solution

Answer 

a) \(X = \sum\limits_{j = 0}^{n - 1} {{X_j}} \)

b) \(P\left( {{X_j} = 1} \right) = \frac{{n - j}}{n}\)

c) \(P\left( {{X_j} = k} \right) = {\left( {\frac{j}{n}} \right)^{k - 1}}\frac{{(n - j)}}{n}\)

d) \(E(X) = n\sum\limits_{j = 1}^n {\frac{1}{j}} \) .

e) \(224.5\)

Use Probability and Sum of Probabilities for each case

a) Let \({Y_j}\) be the random variable that denotes the no. of products needed to be purchased before \(j\) -th collectible card is received for\(j = 1,2, \ldots ,n\) . Obviously \({X_j} = {Y_{j + 1}} - {Y_j}\forall j = 1,2, \ldots ,n - 1\) and \({X_0} = {Y_1}\). Observe that \(X = {Y_n} = \sum\limits_{i = 2}^n {\left( {{Y_i} - {Y_{i - 1}}} \right)} + {Y_1} = \sum\limits_{j = 0}^{n - 1} {{X_j}} \).

b)\(P\left( {{X_j} = 1} \right) = \frac{{n - j}}{n}\).

c) After the\(j\)-th new card is received, each next purchase can result in a repeat card in\(j\)different ways and in a new card in\((n - j)\)ways until the next new card is received. Hence,\(P\left( {{X_j} = k} \right) = P\left( {{Y_{j + 1}} - {Y_j} = k} \right) = {\left( {\frac{j}{n}} \right)^{k - 1}}\frac{{(n - j)}}{n}\).

d) \(E(X) = \sum\limits_{j = 0}^{n - 1} E \left( {{X_j}} \right) = \sum\limits_{j = 0}^{n - 1} {\frac{1}{{\frac{{(n - j)}}{n}}}} = n\sum\limits_{j = 1}^n {\frac{1}{j}} \) .

e) \(E(X) = 50.(\ln 50 + \gamma ) \approx 224.5\).