Balls in finite buckets

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

Balls in finite buckets

Post by Mr.Wizard »

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.
ImageImage
User avatar
Lord_Farin
Posts: 239
Joined: Wed Jul 01, 2009 10:43 am
Location: Netherlands

Re: Balls in finite buckets

Post by Lord_Farin »

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.
Image
thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Balls in finite buckets

Post by thundre »

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?
Image
User avatar
Lord_Farin
Posts: 239
Joined: Wed Jul 01, 2009 10:43 am
Location: Netherlands

Re: Balls in finite buckets

Post by Lord_Farin »

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...
Image
wrongrook
Posts: 480
Joined: Sat Oct 17, 2009 10:39 pm

Re: Balls in finite buckets

Post by wrongrook »

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

Post by thundre »

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!
Image
User avatar
Lord_Farin
Posts: 239
Joined: Wed Jul 01, 2009 10:43 am
Location: Netherlands

Re: Balls in finite buckets

Post by Lord_Farin »

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.
Image
thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Balls in finite buckets

Post by thundre »

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)).
Image
wrongrook
Posts: 480
Joined: Sat Oct 17, 2009 10:39 pm

Re: Balls in finite buckets

Post by wrongrook »

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.
Post Reply