3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – leonbloy Jun 19 '14 at 18:36
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)\;. $$ $\endgroup$ – joriki May 27 '16 at 20:56

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.