= Solution
For each of the $b$ balls, let $I_i$ be the <indicator random variable> that ball $i$ survives the round of <uniform balls-in-bins allocation>. Condition on its chosen bin. Each of the other $b-1$ balls avoids that bin with <probability> $1-1/n$, independently, so the <probability> that ball $i$ is served is $(1-1/n)^{b-1}$. Hence, for $b\geq2$,
$$
\boxed{\mathbb E[\text{balls next round}\mid b]
=b\left[1-\left(1-\frac1n\right)^{b-1}\right].}
$$
We used <linearity of expectation> to sum the <indicator random variables>; their mutual <independence> is unnecessary. For $b=0$ or $b=1$, the next count is zero. This states the boundary cases without an ambiguous $0^0$ when $n=1$.
Back to article page
