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,
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.