1
$\begingroup$

$n$ balls are thrown randomly into $k$ bins, where the bins have a limited capacity $c$. If a ball would land in a full bin, it "bounces" randomly into a different bin, until it finds a non-full bin.

How many bins are expected to be full after all balls have been thrown? A solution for $c = 2$ for $n < 2k$ is specifically what I'm after. (So in this case, finding the number of empty bins is just as good.)

I'm having trouble dealing with the fact that the number of eligible bins changes as the balls are thrown, depending where they have landed so far. I've looked at other ball-and-bin problems here, but I can't find any that have this feature. Edit: This question also has this feature but has no answer. One commenter says "Unfortunately this is, as far as I'm aware, a rather intractable problem." But perhaps something can be done for $c=2$.

If you want to know, I'm trying to calculate equilibria for a population simulation where creatures (players) may or may not run into each other. If a creature is lucky enough to not run into another creature (like a single ball in a bin), it gets free food. If two creatures run into each other (two balls in a bin), they play a round of hawk-dove. The sim assumes a creature can tell when two creatures are already meeting at a location, and then stays away.

I could just numerically find the specific results I need, but I would love to find a general solution (for any $n<2k$, even with $c=2$).

$\endgroup$
  • $\begingroup$ What do you want to find? $\endgroup$ – Parcly Taxel May 30 at 18:18
  • $\begingroup$ Yeah... What's the problem? $\endgroup$ – David G. Stork May 30 at 18:19
  • $\begingroup$ I want to know how many bins are expected to be full. (Added to question.) $\endgroup$ – Justin Helps May 30 at 18:22
  • $\begingroup$ Suppose you throw balls into bins (without capping the number of balls that can be in a bin) until twice the number of empty bins plus the number of bins with one ball is exactly equal to $2k - n$. Shouldn't this give you the answer? And you should be able to approximate this process really well with a Poisson distribution of balls in bins. $\endgroup$ – Peter Shor May 30 at 19:17
  • $\begingroup$ That does seem promising, but I don't find myself able to carry it through to the end. Would you be willing to carry that reasoning a bit further and put it as an answer? $\endgroup$ – Justin Helps Jun 12 at 13:43
2
$\begingroup$

Suppose you throw balls into bins (without capping the bins) until twice the number of empty bins plus the number of bins with one ball is exactly equal to $2k-n$. Now, let's let $b_0$, $b_1$, and $b_2$ be the number of bins with exactly $0$, exactly $1$, and with $2$ or more balls, respectively.

We know that $$b_0 + b_1 + b_2 = k,$$ and $$ 2b_0 + b_1 = 2k-n.$$

Subtracting the second equation from twice the first one, we get that $$b_1 + 2b_2 = n.$$ Thus, if we throw balls into bins (without capping the bins) until the above condition is met, and remove all the excess balls from bins from two or more balls, the result is exactly the same as if we throw $n$ balls into $k$ bins, capping the size of the bins at $2$.

Now, let's look at expectations for a Poisson process. These won't directly prove your theorem, but you should be able to put good bounds on how much the expectation of a Poisson process differs from your exact ball-and-bin problem, and show that it will give you the corruct answer up to approximately $1/\sqrt{k}$.

A Poisson process with rate $\lambda$ will yield an expected number of $e^{-\lambda} k$ bins with $0$ balls, and $\lambda e^{-\lambda} k$ bins with $1$ ball. Thus, to find the rate corresponding to $n$ balls, we need to solve the equations:

$$ 2 e^{-\lambda} k + \lambda e^{-\lambda} k = 2k - n,$$

or

$$ 2 - e^{-\lambda} (2 + \lambda) = \frac{n}{k}.$$

We can solve this equation numerically and plot the fraction of bins that are filled as the ratio of balls to bins, $n/k$, goes from $0$ to $2$.

Fraction of filled bins versus ratio of balls to bins

If the number of bins equals the number of balls, roughly 31.8% of the bins are filled with two balls. If there are three balls for every two bins, roughly 61.8% of the bins are filled.

In fact, the same solution will apply to any maximum capacity, although solving the equations will get harder.

$\endgroup$
  • $\begingroup$ Thanks for this. To make sure I understand, for each point on the curve, you're taking one value of n/k, finding the corresponding lamba, using that lamba to approximate the number of non-full bins, then using that to get the ratio of full bins, which is the vertical position of each point on the curve? $\endgroup$ – Justin Helps Jul 8 at 22:51
  • 1
    $\begingroup$ @JustinHelps: that's right. We start with n/k, find the corresponding lambda, and then compute the ratio of full bins, which is the ratio of bins that do not have $0$ or $1$ balls in them, namely $1 - e^{-\lambda} - \lambda e^{-\lambda}$. Maple actually gave a closed-form formula in terms of Lambert W functions for lambda in terms of n/k, but I couldn't make it work to create the plot, presumably because it was choosing the wrong branch of the function, so I solved the equation numerically to create the plot. $\endgroup$ – Peter Shor Jul 9 at 8:30
0
$\begingroup$

This is more a suggestion for an approach than a solution. Nevertheless, I think it may prove useful.

Work backward: Start with each of the $k$ bins filled to its capacity of $c=2$ balls. Then remove balls one-by-one from the set of $2k$ until you have the required number $n$ remaining.

I think (but cannot quite prove) that this process is statistically equivalent to filling the bins in the "forward" manner. It would seem to simplify the vexing task of determining how many empty and single-filled bins exist at any stage.

I'm not certain this will lead to a closed-form solution... but it might!

$\endgroup$
  • $\begingroup$ Thanks for the idea! Woudn't non-empty bins to remove balls from then be the hard and necessary thing to track? $\endgroup$ – Justin Helps May 30 at 22:21
  • $\begingroup$ @JustinHelps: A bit... yes. But you would never have to worry about special cases at a single bin many times. (Frankly, this simplification makes me worry a bit as to whether the two approaches are guaranteed to give the same result.) $\endgroup$ – David G. Stork May 30 at 22:43

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.