0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Is that last bullet point really true? What if someone were to throw all the balls at the first bin? Sure, it's unlikely and the majority of the balls would be discarded, but in that case, you only have one full bin. $\endgroup$ – benguin Aug 15 '16 at 22:22
  • $\begingroup$ The question is if the bins that are full are removed from future consideration as targets or not. $\endgroup$ – Marko Riedel Aug 15 '16 at 23:00
  • $\begingroup$ @benguin is right, but I'm talking about expected value, average on system replications. Then if a bin is full, it can be selected again but the ball is rejected. $\endgroup$ – FabIO Aug 16 '16 at 7:20
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Please ignore this answer...made a key mistake. Probability of trials in the sample space I posited are not equal in the actual model. In reality, order does matter. $\endgroup$ – Jeremy Dover Aug 16 '16 at 3:50

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.