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

Problem:

Each box of cereal contains one of $\displaystyle 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 $\displaystyle i-1$ coupons, the probability of obtaining a new one is $\displaystyle p_i=1-\frac{i-1}{n}$. Hence, $\displaystyle X_i=1/p_i=\frac{n}{n-i+1}$, and $\displaystyle E[X]=E\left[\displaystyle\sum_{i=1}^nX_i\right]$.

By linearity of expectations, then, $\displaystyle 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:
$\displaystyle 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..

Originally Posted by schwartz92

Problem:

Each box of cereal contains one of $\displaystyle 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 $\displaystyle i-1$ coupons, the probability of obtaining a new one is $\displaystyle p_i=1-\frac{i-1}{n}$. Hence, $\displaystyle X_i=1/p_i=\frac{n}{n-i+1}$, and $\displaystyle E[X]=E\left[\displaystyle\sum_{i=1}^nX_i\right]$.

By linearity of expectations, then, $\displaystyle 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:
$\displaystyle 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 $\displaystyle {n-i+1}=j$

Now note
$\displaystyle \sum_{i=1}^n\frac{1}{n-i+1} = \sum_{j=1}^n\frac{1}{j}$

Originally Posted by schwartz92

Problem:

Each box of cereal contains one of $\displaystyle 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 $\displaystyle i-1$ coupons, the probability of obtaining a new one is $\displaystyle p_i=1-\frac{i-1}{n}$. Hence, $\displaystyle X_i=1/p_i=\frac{n}{n-i+1}$, and $\displaystyle E[X]=E\left[\displaystyle\sum_{i=1}^nX_i\right]$.

By linearity of expectations, then, $\displaystyle 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:
$\displaystyle 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..

$\displaystyle \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 $\displaystyle \sum_{i=1}^n \frac{1}{i}$.

Aha, got it! Thanks for the replies.