Results 1 to 5 of 5

Math Help - Expected value of draws to get all 52 cards in a deck?

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    17

    Expected value of draws to get all 52 cards in a deck?

    Say I have a deck of 52 cards. I draw a card and then return it to the deck, and the probability of drawing each card is 1/52 each time.

    What is the expected value of the number of draws needed to draw every card in the deck at least once?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by cubrikal View Post
    Say I have a deck of 52 cards. I draw a card and then return it to the deck, and the probability of drawing each card is 1/52 each time.

    What is the expected value of the number of draws needed to draw every card in the deck at least once?
    Cubrikal,

    This is called the "coupon collector's problem" in reference to someone who wants to collect a complete set of coupons. In your case, you have 52 "coupons", i.e. cards.

    You can find a discussion of the problem and a formula for the expected number of draws needed to get a complete set here:

    Coupon collector's problem - Wikipedia, the free encyclopedia
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Apr 2009
    Posts
    136
    Awards
    1
    In probability theory, the coupon collector's problem describes the "collect all coupons and win" contests. It asks the following question: Suppose that there are n coupons, from which coupons are being collected with replacement. What is the probability that more than t sample trials are needed to collect all n coupons? The mathematical analysis of the problem reveals that the expected number of trials needed grows as O(nlog(n)). For example, when n = 50 it takes about 225 samples to collect all 50 coupons.


    I am a bit confused by this

    50log(50) =
    84.9485002

    how do i get 225?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by Joel View Post
    In probability theory, the coupon collector's problem describes the "collect all coupons and win" contests. It asks the following question: Suppose that there are n coupons, from which coupons are being collected with replacement. What is the probability that more than t sample trials are needed to collect all n coupons? The mathematical analysis of the problem reveals that the expected number of trials needed grows as O(nlog(n)). For example, when n = 50 it takes about 225 samples to collect all 50 coupons.


    I am a bit confused by this

    50log(50) =
    84.9485002

    how do i get 225?
    The "big Oh" formula is only meant to give an idea of the rate of growth. It is not meant for precise computation. Probably your best formula is

    E(T) \approx n \ln (n) + \gamma n + 1/2
    where \gamma is the "Euler gamma constant", about 0.5772.
    Last edited by awkward; December 18th 2009 at 12:06 PM. Reason: Read the wrong formula
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2009
    Posts
    17
    Quote Originally Posted by awkward View Post
    Cubrikal,

    This is called the "coupon collector's problem" in reference to someone who wants to collect a complete set of coupons. In your case, you have 52 "coupons", i.e. cards.

    You can find a discussion of the problem and a formula for the expected number of draws needed to get a complete set here:

    Coupon collector's problem - Wikipedia, the free encyclopedia
    Thanks for the name of the problem. That wiki article is pretty informative too.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: December 6th 2011, 07:11 AM
  2. Replies: 2
    Last Post: October 2nd 2010, 03:09 PM
  3. Deck of cards
    Posted in the Statistics Forum
    Replies: 2
    Last Post: March 9th 2009, 10:39 AM
  4. Deck of Cards
    Posted in the Statistics Forum
    Replies: 4
    Last Post: November 4th 2008, 02:44 PM
  5. Deck of Cards
    Posted in the Statistics Forum
    Replies: 2
    Last Post: January 23rd 2007, 05:34 PM

Search Tags


/mathhelpforum @mathhelpforum