0
$\begingroup$

I could not find a similar question already asked on math.stackexchange, and it is bugging me, so here we go.

In the standard balls and bins paradigm, $m$ balls are thrown into $n$ bin uniformly and independently at random. A standard result is that on average, $n \left( 1 - \left(1 - \frac{1}{n}\right)^{m} \right)$ bins will contain at least one ball.

Now suppose we throw $m$ balls into $n$ bins, still uniformly and independently at random, but this time, before the beginning of the process, $k$ bins already contain one ball or more. How many bins, on average, will contain at least one ball at the end of the process?

The standard result can be easily solved with indicator random variables on whether bin $j$ received at least one ball or not, but I have no idea how to use them here.

Or maybe with the inclusion-exclusion principle, but I did not manage to apply it here.

Thank you

$\endgroup$
1
$\begingroup$

Indicator variables seems to work just as they do in the original case.

Let $X_i$ be the indicator variable for the $i^{th}$ bin (so it is $1$ iff the $i^{th}$ bin contains a ball) Then the probability that $X_i=1$ is $$P=\frac kn\times 1 +\frac {n-k}n\times \left(1-(1-\frac 1n)^m \right)$$

As before, the average you want is then just $nP$, so $$E=k+(n-k)\times \left(1-(1-\frac 1n)^m \right)=n-(n-k)\times \left(1-\frac 1n\right)^m$$

$\endgroup$
  • $\begingroup$ Thank you! I did not realize it was that straightforward. $\endgroup$ – Laurent Hayez Nov 2 '17 at 19:28

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.