Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Recently I tried to solve a problem that based on coupons collector problem. Let it be sth like this:

If a package has one of 50 random baseball cards, how many packages do you need to buy to get a complete set? (or sth like this, doesnt matter)

If I need every card one time, so it makes one set that is easy, explaination is on wikipedia and I already understood it. But what if we consider to collect every card k times? (To collect k sets of cards)

How can I tried to solve this problem? I found sth about Chernoff's bound ( but I dont get it actually if it is a solution of this problem. I need to estimate E(X) and Var(X) for k sets of cards.

Could anyone give me a hint how to solve this problem? Thanks for all answers:)


share|cite|improve this question
The answer is on the Wikipedia page on the Coupon Collector's problem:… , where the Newman-Shepp result says that approximately $\Theta(n\log\log n)$ more samples are needed for each additional set. You should be able to find their AMM article without too much trouble. – Steven Stadnicki May 29 '12 at 20:18
@StevenStadnicki the Wikipedia link gives $O(n \log n)$ not $O(n \log \log n)$ (unless we think of $k$ as a function of $n$...). – John Engbers May 29 '12 at 20:22
@JohnEngbers Wikipedia says $n\log n+(k-1)n\log\log n$, so I was breaking it down as $n\log n$ for the 'first' (which was the result I presumed the OP already knew) and then $n\log\log n$ for each additional set. – Steven Stadnicki May 30 '12 at 0:13

I'm closing some other questions as a duplicate of this one, so I'll collect the information that's been posted in various places in one place:

This problem was treated in the paper The double Dixie cup problem by Newman and Shepp. The expected collection time is

$$ n \log n + (m-1) n \log\log n + O(n)\;, $$

so, as Steven Stanicki noted, each additional set collected takes $n\log\log n$ time.

In Some new aspects of the coupon collector's problem, Myers and Wilf gave a simpler derivation of the result and a generating function in one variable.

The result is also derived in Section $5$ of The Coupon Collector’s Problem by Ferrante and Saltalamacchia, which treats various generalisations of the coupon collector's problem with various approaches.

share|cite|improve this answer

It asymptotically almost surely takes $O(n \log n)$ time to collect $n$ cards, so for any constant number of sets it should take (a.a.s.) $O(n \log n)$ time as well, since at worst case you can imagine 'forgetting' to count duplicates until you have a new set. Therefore you can only hope to improve the constant, unless you are hoping to incorporate the number of sets ($k$) as a variable.

share|cite|improve this answer
I think incorporating the number of sets as a variable is the point of the question... – Steven Stadnicki May 29 '12 at 20:18
Yes - your wikipedia link provides the nice formula. – John Engbers May 29 '12 at 20:27
Thanks for all answers, I think it will be easier to understand for me now. Once again, thanks a lot for all answers!:) – trox May 29 '12 at 20:47

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.