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

**schwartz92** · October 15th 2009, 12:16 AM

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..

**aman_cc** · October 15th 2009, 12:22 AM

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}$

**mr fantastic** · October 15th 2009, 12:27 AM

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}$ .

**schwartz92** · October 15th 2009, 12:43 AM

Aha, got it! Thanks for the replies.

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

LinkBack

Thread Tools

Display

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

Similar Math Help Forum Discussions

Basic Word Problem ("Bigger Than" / "The Size Of")

What does "solved analytically" and "closed-form solution" means?

Ellipse: extract "minor axis" (b) when given "arc length" and "major axis" (a)

Definition clarification: "state-space", "support" and "sample space"

Efficient solution to "risky drivers" problem

Search Tags