## Balls in finite buckets

Arrangements, combinations and permutations, probability, ...
Mr.Wizard
Posts: 26
Joined: Sun Jan 02, 2011 9:20 am

### Balls in finite buckets

I don't know if I should post this here, or under "Programming Problems" but at its core it's combinatorics.

The question was posed:
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.

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

N could be in the (tens)thousands [although most cases 95% it will be 10-100s), H will likely be 5 or less (10 would be most. A note, that the higher H is, its much less likely N will be big, ie, N is inversely proportional to H), and D would then be at most N * (H - 1)

I don't think people will be able to tell if its 1-2% off. That is the limit of human observation. It does need to be 100% accurate in cases where if I have D = N * (H - 1) In that 100% of that case will result in a bucket filling. It also needs to be 100% accurate in the cases of D <= H - 2 In that 0% of that case will result in a bucket filling.
I believe I have a grasp of the basic math, and I can compute results for smaller values using integer partitions and multinomial coefficients, but I cannot give an answer that accommodates values as large as requested. My method also uses a bignum library, and I don't think that is necessary for the accuracy required.

I will relay any help that is given, or if you wish to reply directly, the original is here.
Lord_Farin
Posts: 239
Joined: Wed Jul 01, 2009 10:43 am
Location: Netherlands

### Re: Balls in finite buckets

The problem can easily been brought down to finding the number of partitions of an integer (D) into N non-negative integers, all of which are at most equal to some constant (H). Call this solution $f_H(n,d)$. This also covers the filling question, you just need to compute $\frac1{f_{H-1}(N,D)}\sum_{i=0}^N\binom{N}{i}\frac{i}{N}f_{H-2}(N-i,D-i(H-1))$. I then proceeded to find the bivariate generating function $F_H(x,y)=\sum_{n,d=0}^\infty f_H(n,d)x^dy^n$ from which then hopefully we could find the terms by differentiation. To this end I used the recursion $f_H(n,d)=\sum_{i=0}^Hf_H(n-1,d-i)$ which obviously holds, after which some gruesome summations and cancellations and such had to be done (if your interested, I can post them, but for now I leave the calculation out), but eventually I got the equation $(1-y\frac{x^{H+1}-1}{x-1})F_H(x,y)=\frac{1}{1-y}-\frac{x^H-1}{x-1}\frac{y}{1-y}+\frac{y}{1-y}\left(\frac{\left(\frac{x}{y-1}\right)^H-1}{\frac{x}{y-1}-1}-1\right)+H \frac{y^2}{1-y}+H \frac{y^2}{y-x-1}-\frac{y^2\left(\frac{x}{y-1}\right)^H}{y-x-1}\frac{\left(\frac{y-1}{x}\right)^H-1}{\frac{y-1}{x}-1}$. So surprisingly enough, there is a closed form for the generation function (albeit not a particularly nice one). I haven't set myself up for differentiation to arbitrary N and D, but in principle it should be possible. Note also that there are probably some simplifications possible, as I haven't tried yet.
Hopefully, this partial result gives you motivation to continue.
thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

### Re: Balls in finite buckets

I have a different question, but it matches the subject line so I'll ask it in the same topic.

How many ways can you distribute k identical balls into n buckets, if each bucket can hold a maximum of m balls?

If m=1, the answer is "n choose k". I'm not sure what the convention is for writing that in ASCII, so I'll say C(n,k).

If m>=k, any ball can go in any bucket. I think the answer is C(n+k-1, k).

What if 1 < m < k?

If m = k-1, you can count the illegal cases with all k balls in the same bucket and subtract them from the total, i.e. C(n+k-1, k) - C(n,1). But as k/m increases, subtracting gets more complicated.

In the case I'm dealing with, n is 13 digits -- too large to solve using n steps of DP.

Can anybody suggest a closed-form solution, or a DP approach that doesn't increase with n?
Lord_Farin
Posts: 239
Joined: Wed Jul 01, 2009 10:43 am
Location: Netherlands

### Re: Balls in finite buckets

I would say your expression for $m > k$ is correct. (That has to count for something)

When $n > k$, you can maybe do DP for integer partitioning (into non-negative integer summands) and correct it a bit to suit with the fact that you have $n$ distinguishable buckets. This might have a running time proportional to $n^2$ or $n^{\frac 3 2}$, or something like that. I think it's more than $n$.

I have no idea for a closed-form solution. However, a suggestion may be to reword the problem:

Consider the lattice $\mathbb{Z}^n$, restricted to positive coordinates. Find the number of paths from the origin to the hyperplane given by $x_1+\cdots+x_n = k$. (when $m < k$, restrict further to $x_i \leq m$). I don't see how it may help, but one never knows...
wrongrook
Posts: 480
Joined: Sat Oct 17, 2009 10:39 pm

### Re: Balls in finite buckets

How big are m and k?

For small m (the maximum in each bucket) you could write the DP solution in a matrix formulation and then use the normal exponentiation technique to compute high powers of the matrix in log(n) multiplies rather than n steps.
(The matrix will have a special form that means it is possible to achieve faster than normal matrix multiplication if necessary, but if m is of order 13 digits I don't think even this will be feasible.)

For high m, then k/m gets smaller and you could use inclusion-exclusion to exclude the illegal cases based on the number of buckets x with >m balls in them.
I think this would look something like sum (-1)**x C(n,x) C(n+k-1-x*(m+1),k) where x goes from 0 to k/m.
This would have order O(k/m).
thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

### Re: Balls in finite buckets

wrongrook wrote:How big are m and k?
m and k are both less than 100. Only n is huge. I've been attempting inclusion/exclusion but it's so messy...

That matrix exponentiation idea sounds good. I will see if I can make it work.

Than you both for the suggestions!
Lord_Farin
Posts: 239
Joined: Wed Jul 01, 2009 10:43 am
Location: Netherlands

### Re: Balls in finite buckets

Lord_Farin wrote:This might have a running time proportional to $n^2$ or $n^{\frac 3 2}$, or something like that. I think it's more than $n$.
The $n$'s in this sentence should all be $k$'s. I apologise.
thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

### Re: Balls in finite buckets

Lord_Farin wrote:
Lord_Farin wrote:This might have a running time proportional to $n^2$ or $n^{\frac 3 2}$, or something like that. I think it's more than $n$.
The $n$'s in this sentence should all be $k$'s. I apologise.
I used the matrix exponentiation method. Since the matrices were square with dimension k+1, multiplication was O(k^3), and exponentiation was O(k^3 * log(n)).
wrongrook
Posts: 480
Joined: Sat Oct 17, 2009 10:39 pm

### Re: Balls in finite buckets

If you want any more speed, you might like to look at the solution thread for problem 258 as it gives details of various faster (and very elegant!) methods for solving a recurrence relation of this type.