# Buckets of Balls, Will one fill if I add another Ball?

I was refereed here by stackoverflow.com. With some searching I found this: another balls and bins question, but its not quite what I am looking for. Rather the inverse. IE the expected number of buckets that have H-1 balls in them.

I realize the title is a bit odd. But this is a statistics/probability problem that I am trying to figure out, but am stumped. (No no, its not homework, see the bottom for the real explanation)

The premise is simple. You have N buckets. Each bucket can hold H balls. None of the buckets is full. You have D balls already in the buckets, but you don't know where the balls are (you forgot!) You choose a bucket at random to add 1 ball. What is the probability that that bucket will then be full.

Some example possible diagrams, with N = 4, H = 3, D = 4. Each case is just a hypothetical arrangement of the balls. for one of many cases.

Scenario 1: 1 bucket could be filled.
|   |   |   |   |
+ - + - + - + - +
| B |   |   |   |
+ - + - + - + - +
| B | B |   | B |
+ - + - + - + - +

Scenario 2: 2 buckets could be filled.
|   |   |   |   |
+ - + - + - + - +
|   | B | B |   |
+ - + - + - + - +
|   | B | B |   |
+ - + - + - + - +

Scenario 3: 0 buckets could be filled.
|   |   |   |   |
+ - + - + - + - +
|   |   |   |   |
+ - + - + - + - +
| B | B | B | B |
+ - + - + - + - +

The problem is I need a general purpose equation in the form of P = f(N, H, D)

Alright, you've tuned in this far. The reason behind this query on math, is I'm curious in having large battles between units. Each unit could belong to a brigade that contains many units of the same type. however, the battle will progress slowly over time. At each phase of the battle, the state will be saved to the DB. Instead of saving each unit and each health for each unit, I want to save the number of units and the total damage on the brigade. When damage is added to a brigade, the f(N, H, D) is run and returns a % chance that a unit in the brigade is destroyed (all of its HP are used up). This then removes that unit from the brigade decrementing N by 1 and D by H.

Before you get too technical, I need to implement this solution to a program. So Integrals are out of the question for now. I'm stuck with algebra and trig functions.

I appreciate the help

-
If people give you formulas with factorials, your math library may be able to calculate them faster than looping if n is big, for example many math.h C libraries let you evaluate n! as tgamma(n+1). – Matt Apr 21 '11 at 20:03
In the example you gave, is having 1,0,1,2 (the reverse of Scenario 1) a possibility? – Aryabhata Apr 21 '11 at 20:34
@Moron - All possible combinations are possible, those are just some sample possibilities. @Matt - Yes, factorials are fine. I'm sure this is a combinatory problem, but I can seem to grasp how to set it up. – ohmusama Apr 21 '11 at 20:39
The only difference from the question you reference in your first line (specifically Henry's solution, with k=H-1) is that in your case, the distribution is conditioned on all buckets having H-1 or fewer balls. Unfortunately, this raises the hardness of the question significantly. – Matt Apr 21 '11 at 22:05
@Matt - I know :( thus why I was so confused. – ohmusama Apr 21 '11 at 22:32

The start has been substantially changed as a result of Matt's comments, affecting the result.

Let $f(N,H,D)$ be the number of ways of putting $D$ balls into $N$ buckets where there are strictly fewer than $H$ balls in each bucket, and counting different orders for the balls as distinct (i.e. labelled balls and labelled buckets). We can calculate this with the recurrence

$$f(N,H,D) = \sum_{i=0}^{H-1} {D \choose i} f(N-1,H,D-i)$$

starting with $f(0,H,D)=0$ except $f(0,H,0)=1$ and remembering ${x \choose y} = 0$ if $x<y$. This stems from adding an extra bucket and putting from $0$ to $H-1$ balls in it, in an order mixed with the balls in the other buckets. For example $f(4,3,4)=204$.

How many of these have $H-1$ balls in the first bin? That is like removing $H-1$ balls and one bin, so is $f(N-1,H,D-H+1) {D \choose H-1}$ which in the example is $9 \times {4 \choose 2} = 54$.

So the probability that (a) you put the next ball in the first bin and (b) fill the first bin by doing so is $\frac{1}{D} \cdot \frac{f(N-1,H,D-H+1) {D \choose H-1}}{f(N,H,D)}$, and so the probability of filling any of the bins with the next ball is $D$ times that, i.e.

$$\frac{f(N-1,H,D-H+1) {D \choose H-1}}{f(N,H,D)}$$

or in this example $\dfrac{54}{204} = \dfrac{9}{34}$ confirming Matt's result.

-
I'm not a math wiz, by any stretch of the imagination. Or I would have figured this out, but I would like to understand the methods behind this before I blindly copy the code over to PHP. Do you have a good link that might explain Constraint Compositions? – ohmusama Apr 21 '11 at 22:39
I don't think the final answer here is right. For the example shown, scenario 1 can be drawn in 12 ways (the diagram shown is one of 12 possibilities), each of which can have its balls labeled "first", "second", etc. in 12 ways. Scenario 2 can be drawn in 6 ways, each of which can be labeled in 6 ways. Scenario 3 can be drawn in 1 way, which can be labeled in 24 ways. So the expectation is $\frac{\frac{1}{4}144+\frac{2}{4} \cdot 36}{144+36+24}$ = $\frac{9}{34}$. Also, I thought I saw a generating function answer earlier that incorrectly ignored the labeling... how did it disappear? – Matt Apr 21 '11 at 22:40
@Matt: Moron deleted his earlier answer: it also came to $9/34$, but I think did not do what you did of spotting how many ways each scenario could be constructed and how many ways this could lead to a bin being filled: instead it was $\frac{1}{N}\left(1 - \frac{f(H-2)}{f(H-1)}\right)$; it would be ironic if that turned out to be a correct expression. If you are right, and you may well be, I may delete this answer. – Henry Apr 21 '11 at 22:52
I didn't realize things could disappear without a trace... I spent quite a while trying to figure out whether it was my browser or the web site that was broken! Anyway, I ran a simulation to confirm my answer, so I think it is right unless I am misunderstanding the problem. I take a sample by throwing balls in bins at random until a bin hits the limit of H balls. At that point, if I have thrown D+1 balls it is a "hit", and if I have thrown more than D+1 balls, it is a "miss", and if I have thrown less than D+1 balls, I ignore that sample as invalid. – Matt Apr 21 '11 at 23:01
@Matt - That sounds right. Basically you've randomly thrown in D balls so far, and none of them have filled a bucket yet. So with D+1 what are the odds of filling a bucket. So I think you have it right. – ohmusama Apr 21 '11 at 23:29

Here is how I see this. In your sample case of N, H, D = 4, 3, 4 :

{2,2,0,0}   {6,  6}
{2,1,1,0}   {12,12}
{1,1,1,1}   {1, 24}

On the left we have restricted partitions, on the right the number of ways to permute and uniquely fill each partition.

Therefore, we have a combined enumeration of:

{2,2,0,0}     36
{2,1,1,0}    144
{1,1,1,1}     24

I count the number of nearly-filled bins as 2 * 36 + 144 = 216, out of 4 * (36 + 144 + 24) = 816, for a probability of 216/816 = 9/34.

In other words, I am getting the same result as Matt.

-
This is the same as my calculation. Where you say "restricted partitions", I say "number of possible diagrams, of the type drawn by the original poster", and where you say "the number of ways to permute and uniquely fill each partition", I say "the number of ways to label the balls in the diagram as 'first', 'second', etc.". (Sorry for being jargon-impaired!) – Matt Apr 21 '11 at 23:25
@Matt, I am not a mathematician so the chances are that it is my jargon that is impaired. – Mr.Wizard Apr 21 '11 at 23:28
So If I were doing this programatically. How might I generate the partitions? and then how would I derive the permute and uniquely fill numbers. I think this could be a solution. I wonder if it will also be tractable. – ohmusama Apr 21 '11 at 23:33
@ohmusama it is not too complex, if this actually is correct. I use Mathematica, which does make things simpler, but it should not be hard to implement. I'll update my answer in a little while, if no one has shown this to be invalid, or posted a better answer by then. – Mr.Wizard Apr 21 '11 at 23:41
@ohmusama: If you can count the units in your brigades, and the hit points of your units, on your fingers (preferably of one hand), the method we're using here might work for you... but we need to seriously simplify our formulas before they are ready for practical use! Here we are essentially just double-checking the logic of our approaches on your nicely illustrated example, not yet claiming to have solved your original problem in any useful way. (Speaking for myself, at least.) – Matt Apr 21 '11 at 23:42