full bins with limited capacity after throwing balls

Question

Expected number of full bins after throwing balls uniformly randomly to bins that have limited capacity

Let us have $N$ bins with the same limited capacity ($N_{max}=C$), in the sense that if a ball is threw into a bin that already has $C$ balls in it, the ball is discarded. After throwing (uniform random allocation) $L$ balls, what is the expected number of bins that are full?

considerations:

• since uniform random allocations, after $L$ launches of balls we should have an uniform distribution of $L/N$ balls in each bin
• if $L<C$, no bin can be full (few balls to have the chance to have one bin full), so the expected number of "full" bins should be 0.
• if $L \in [C,C\cdot N ) $ it should be expected to have $\dfrac{L}{C}$ full bins, and $N-L/C$ bins remain free to host a new ball.
• if $L>=C\cdot N$ no bin can be filled any more,all the bins reached their capacity. Any attempts of a new launch of a ball is rejected.

This is an idea, is there an analytical closed form way to express that?

Answer 1

This answer assumes the model you have described, where balls always choose their target uniformly (and independently of each other) among all bins, even if some are full.

Let $B_i$ denote the number of balls thrown at the $i$th bin after $L$ balls have been thrown. Since each ball has a $\frac{1}{N}$ chance of being thrown at the $i$th bin, $B_i \sim \textrm{Bin}\left(L, \frac{1}{N} \right)$ is binomially distributed.

The $i$th bin is full if $B_i \ge C$. Using the probability mass function of the binomial distribution, the probability of this happening is $\sum_{n = C}^L \binom{L}{n} \frac{1}{N^n} \left(1 - \frac{1}{N} \right)^{L - n}$.

By linearity of expectation, the expected number of full bins is the sum of the probabilities that each bin is full. The bins have the same distribution, and so the expected number of full bins after $L$ balls have been thrown is $$ N \sum_{n = C}^L \binom{L}{n} \frac{1}{N^n} \left(1 - \frac{1}{N} \right)^{L - n}. $$

Note that this will converge to $N$ as $L \rightarrow \infty$, but will never be equal to $N$, since, as mentioned in the comments, you might get so unlucky as to have all the balls thrown at the same bin.

Answer 2

I don't think the third bullet is right, either. If L=C, I would certainly not expect a bin to be full, since the only way that happens is if all L=C balls go into one bin.

Based on the problem description, it seems that the appropriate sample space $S$ is the set of ways to distribute L indistinguishable balls into N distinguishable boxes, independent of the fullness constraint, since any box being full does not prevent attempts to add more balls.

In this sample space, let $A_i$ denote the set of trials with $i \in {1..N}$ such that bin $i$ is full. This occurs whenever bin $i$ has at least C balls, which can happen in $\displaystyle{{L-C+N-1}\choose{N-1}}$ ways.

Now, $A_i$ may contain trials where boxes other than box $i$ are full, so to calculate probabilities we would need to use inclusion/exclusion. But since we only need the expected number of full boxes, I think we can calculate this as $$\frac{1}{|S|}\sum_{i=1}^N |A_i|$$ Every trial with more than one full box gets counted once for each full box, which is exactly the multiple counting needed for the value of the random variable in the expectation calculation. Noting that $|S|=\displaystyle{{L+N-1}\choose{N-1}}$, we get the expectation $$\frac{N\times L!\times(L-C+N-1)!}{(L-C)!\times(L+N-1)!}$$

Note: I'm traveling, without references, but believe this is correct.