1
$\begingroup$

Another balls into bins question...

I have n balls to distribute into k bins which can hold no more than l balls. What probability density function describes the number of balls in a (randomly selected) bin?

i.e. If I pick one of these bins, what is the probability of it containing 0, 1, 2 balls, etc?

To try and clarify a bit, there's not meant to be anything fancy going on here - for each of n balls, pick a non-full bin at random (all non-full bins have equal probability). (Assume n <= kl otherwise the whole thing is fairly meaningless!)

$\endgroup$
  • $\begingroup$ You need to say how the balls are distributed. Normally each ball goes into each bin with equal probability. But if that's the intended interpretation, it's not clear why you mention that the balls are indistinguishable, because that would be irrelevant. Perhaps by describing the balls as indistinguishable you intended to imply that all partitions of $n$ into $k$ parts not greater than $l$ are equiprobable? $\endgroup$ – joriki May 15 '16 at 19:58
  • $\begingroup$ @joriki - the first thing you said - balls are distributed into (non-full) bins with equal probability. I've edited the question to try and clarify it a bit. btw, thanks for picking up a nearly 3 year old question! $\endgroup$ – FredL May 16 '16 at 22:58
  • $\begingroup$ Unfortunately this is, as far as I'm aware, a rather intractable problem. The difficulty arises because the probabilities change in the course of the process, once bins get full. Counting the number of different ball distributions is relatively straightforward using inclusion-exclusion (see Balls In Bins With Limited Capacity), but they're not equiprobable, so that doesn't help. To see how complicated things get already in a simple example, consider e.g. $k=2$ and $n=2l-j$ for small $j$. $\endgroup$ – joriki May 17 '16 at 7:47
  • 1
    $\begingroup$ Ahh, I think I see. It was quite a while ago now but IIRC the actual application this question came from had fairly low physically possible values of k and l, so we just enumerated the different possibilities - but was interested if there was some kind of general solution available. Thanks again. $\endgroup$ – FredL May 18 '16 at 10:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.