"coupon collector's problem" -- need help in final step of the solution

Printable View

October 15th 2009, 12:16 AM
schwartz92

"coupon collector's problem" -- need help in final step of the solution

Problem:

Each box of cereal contains one of $n$ different coupons (uniformly at random). Calculate the expectation of the number of boxes bought until at least one of each coupon is obtained.

Solution (from a textbook)
When we have exactly $i-1$ coupons, the probability of obtaining a new one is $p_i=1-\frac{i-1}{n}$ . Hence, $X_i=1/p_i=\frac{n}{n-i+1}$ , and $E[X]=E\left[\displaystyle\sum_{i=1}^nX_i\right]$ .

By linearity of expectations, then, $E[X]=\displaystyle\sum_{i=1}^nE[X_i] = \displaystyle\sum_{i=1}^n\frac{n}{n-i+1}$

And the final step of the solution from the textbook is:
$E[X]=\ldots= \displaystyle\sum_{i=1}^n\frac{n}{n-i+1}=n\,\displaystyle\sum_{i=1}^n\frac{1}{i}$

How do I obtain this last expression? I haven't been able to figure this one out on my own. Not really a statistics question though, feel free to redirect me to another subforum..
October 15th 2009, 12:22 AM
aman_cc

Quote:

Originally Posted by schwartz92

Problem:

Each box of cereal contains one of $n$ different coupons (uniformly at random). Calculate the expectation of the number of boxes bought until at least one of each coupon is obtained.

Solution (from a textbook)
When we have exactly $i-1$ coupons, the probability of obtaining a new one is $p_i=1-\frac{i-1}{n}$ . Hence, $X_i=1/p_i=\frac{n}{n-i+1}$ , and $E[X]=E\left[\displaystyle\sum_{i=1}^nX_i\right]$ .

By linearity of expectations, then, $E[X]=\displaystyle\sum_{i=1}^nE[X_i] = \displaystyle\sum_{i=1}^n\frac{n}{n-i+1}$

And the final step of the solution from the textbook is:
$E[X]=\ldots= \displaystyle\sum_{i=1}^n\frac{n}{n-i+1}=n\,\displaystyle\sum_{i=1}^n\frac{1}{i}$

How do I obtain this last expression? I haven't been able to figure this one out on my own. Not really a statistics question though, feel free to redirect me to another subforum..

If it is only the last step you are stuck with it is trivial.
put ${n-i+1}=j$

Now note
$\sum_{i=1}^n\frac{1}{n-i+1} = \sum_{j=1}^n\frac{1}{j}$
October 15th 2009, 12:27 AM
mr fantastic

Quote:

Originally Posted by schwartz92

Problem:

Each box of cereal contains one of $n$ different coupons (uniformly at random). Calculate the expectation of the number of boxes bought until at least one of each coupon is obtained.

Solution (from a textbook)
When we have exactly $i-1$ coupons, the probability of obtaining a new one is $p_i=1-\frac{i-1}{n}$ . Hence, $X_i=1/p_i=\frac{n}{n-i+1}$ , and $E[X]=E\left[\displaystyle\sum_{i=1}^nX_i\right]$ .

By linearity of expectations, then, $E[X]=\displaystyle\sum_{i=1}^nE[X_i] = \displaystyle\sum_{i=1}^n\frac{n}{n-i+1}$

And the final step of the solution from the textbook is:
$E[X]=\ldots= \displaystyle\sum_{i=1}^n\frac{n}{n-i+1}=n\,\displaystyle\sum_{i=1}^n\frac{1}{i}$

How do I obtain this last expression? I haven't been able to figure this one out on my own. Not really a statistics question though, feel free to redirect me to another subforum..

$\sum_{i=1}^n \frac{n}{n-i+1} = n \sum_{i=1}^n \frac{1}{n-i+1}$ .

Now write out the first few and last few terms of the sum and you will see why it can be written as $\sum_{i=1}^n \frac{1}{i}$ .
October 15th 2009, 12:43 AM
schwartz92

Aha, got it! Thanks for the replies.