Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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,

share|improve this question
1  
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

1 Answer 1

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

 
discard

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.