$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$).
Best Answer
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$.
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.