Thread: 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?

Originally Posted by cubrikal

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

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?

Originally Posted by Joel

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


where is the "Euler gamma constant", about 0.5772.

Originally Posted by awkward

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.