# Expected total number of balls in all bins after throwing balls uniformly randomly to bins that have limited capacity

Consider throwing $n$ balls uniformly randomly to $L$ bins. Each bin has capacity $G$, meaning that if a ball is threw to a bin that already has $G$ balls in it, the ball is discarded. Is that possible to determine the expected total number of balls in all bins after throwing $n$ balls?

• First, the "indistinguishable" (ball and bin) adjective looks irrelevant here, no? Second: "expected number of balls in all bins" means the total (sum) number of balls, or in each bin (marginal) or in the full set (joint mean value)? – leonbloy Jun 19 '14 at 18:36

Let $x_i$ be the original (before discarding) number of balls that went to bin $i$. Then $x_i$ follows a Binomial distribution $B(n,p)$, with $p=1/L$. Let $y_i = \min(x_i,G)$.

Now, $y_i$ is a truncated Binomial. Hence, assuming we are interested in $E(\sum y_i)=L E(y_i)$, and that $G<n$ :

$$L \, E(y_i)= L \frac{\sum_{k=0}^G k {n \choose k } \, p^k (1-p)^{(n-k)}}{\sum_{k=0}^G {n \choose k } p^k (1-p)^{(n-k)}}=L \frac{\sum_{k=0}^G k {n \choose k } \, (L-1)^{(n-k)}}{\sum_{k=0}^G {n \choose k } (L-1)^{(n-k)}}$$

I doubt that this can be simplified much more. If the numbers are big, you might approximate this using a normal distribution.

• The probabilities shouldn't be rescaled; all the probability from $x_i\gt G$ is added to $x_i=G$, so it's $$LE(y_1)=n-L\sum_{k=G+1}^n\binom nkp^k(1-p)^{n-k}(k-G)\;.$$ – joriki May 27 '16 at 20:56