3
$\begingroup$

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!

Improve this question
$\endgroup$
4
  • 5
    $\begingroup$ 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... $\endgroup$
    – Brendan McKay
    Jun 5, 2012 at 14:49
  • $\begingroup$ 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... $\endgroup$
    – user4535
    Jun 5, 2012 at 18:56
  • $\begingroup$ 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. $\endgroup$
    – Douglas Zare
    Jun 6, 2012 at 5:02
  • 1
    $\begingroup$ 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. $\endgroup$
    – Douglas Zare
    Jun 6, 2012 at 5:09

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Douglas Zare
    Jun 6, 2012 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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