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

Question

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?

Answer 1

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.

Answer 2

The answer is

$$L \left (\frac{1}{L} \right )^{n} \sum_{i=0}^n \min (i,G){n \choose i }(L-1)^{n-i}=\left (\frac{1}{L} \right )^{n-1} \left ( \sum_{i=0}^G i{n \choose i }(L-1)^{n-i} +\sum_{i=G+1}^n G{n \choose i }(L-1)^{n-i} \right )= \\n-L \left [ G \mathbb{P}\left (W(n) \le G\right ) - n \mathbb{P}\left (W(n-1)\le G-1\right ) +n-G \right ] $$

with $W(n) \sim \text{Binomial}(n,1/L)$ and $W(n-1) \sim \text{Binomial}(n-1,1/L)$.

The method used to obtain the above is detailed here for a related problem. For $G=n$, the expectation is $n$.

Note that here we must not use the conditional distribution $W(n)|W(n)\le G$.