Results 1 to 4 of 4

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

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    3

    "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..
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by schwartz92 View Post
    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}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by schwartz92 View Post
    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}.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Oct 2009
    Posts
    3
    Aha, got it! Thanks for the replies.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: August 6th 2011, 04:00 PM
  2. Replies: 2
    Last Post: June 4th 2011, 01:11 PM
  3. Replies: 2
    Last Post: April 24th 2011, 08:01 AM
  4. Replies: 1
    Last Post: October 25th 2010, 05:45 AM
  5. Efficient solution to "risky drivers" problem
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: April 13th 2008, 04:05 PM

Search Tags


/mathhelpforum @mathhelpforum