# Coupon collector problem for collecting set k times.

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 (http://www.math.ucla.edu/~pak/courses/pg/l10.pdf) 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:)

Greetings,

-
The answer is on the Wikipedia page on the Coupon Collector's problem: en.wikipedia.org/wiki/… , 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.

-

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.

-
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