Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have run across a question that seems like it should have a well known answer, but I can't find one, so I thought I would ask this hive mind:

Suppose we start with t piles of s rocks each. In a given turn, I will choose at random (with equal probabilities) one of the piles that still has at least one rock in it and remove one of the rocks from that pile. After I have removed k total rocks (with k less than st), what is the expected number of piles that are left? It would be even nicer to know what the probability is that a given number of piles remain or the expected size of the largest pile or things of that nature.

I have done some monte carlo simulations and I would be happy to share those results, but I am curious if anyone has any insights into this or has run across something similar in the literature.

Thanks!

share|improve this question
5  
Problems like this are usually treated the other way around: start with $t$ empty bins of capacity $s$ and throw in balls at random. It is called an "allocation" problem, a "balls and bins" problem, a "coupon collection" problem, etc. Books have been written about it... –  Brendan McKay Jun 5 '12 at 14:49
    
Thanks! As this is far from my area I hadn't realized how much there is pertaining to balls and bins with fixed capacities. Now the real question I am curious about involves unequal probabilities, which seems like it will be quite a bit hairier... –  user4535 Jun 5 '12 at 18:56
    
There isn't much difficulty counting the ways you can end up with various configurations. Unfortunately, these paths have different weights. For some types of answers, you can estimate the differences between the actual weights and uniform, but I'm not sure what answers you want. By the way, if you have different probabilities for each pile, and each pile starts with one stone, then this is called the Independent Chip Model in poker, and it is the main model used to evaluate situations in poker tournaments which have prizes for second and lower places. –  Douglas Zare Jun 6 '12 at 5:02
1  
If you would like a calculator for the Independent Chip Model with up to $10$ stacks, you can download my program ICM Explorer from icmexplorer.com for free. –  Douglas Zare Jun 6 '12 at 5:09

1 Answer 1

As Brendan noted, the literature on the coupon collector's problem is large. I suspect a close fit to your problem would be The Collector’s Brotherhood Problem Using the Newman-Shepp Symbolic Method by Foata and Zeilberger. For the case of unequal probabilities, you might consider the methods in my paper Coupon Collecting with Quotas. It turns out that the case of unequal probabilities is not too much "hairier" than the uniform case, so it seems feasible to mesh these two papers to obtain the result you're looking for.

share|improve this answer
    
In the classical coupon collector problem, the probability of each coupon does not change based on the past sequence of coupons. In dg's formulation (and for the independent chip model) it does. If you have collected your quota of a coupon then the probabilities of the others rescale. –  Douglas Zare Jun 6 '12 at 18:36

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.