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

Question

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

Answer 1

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.

Answer 2

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.