I am looking at the standard balls and bins example and more precisely to the expected number of empty bins. Given $n$ balls and $n$ bins, we throw balls into bins sequentially uniformly at random. So the probability for a ball $i$ to fall into a given bin is exactly, $$ P(\text{ball } i \text{ fall into bin } i ) = \frac{1}{n}. $$

If $X$ denotes the number of empty bins then, we know that $$ E[X] = n \left( 1 - \frac{1}{n} \right)^n \approx \frac{n}{e}. $$

However, I was wondering if there were known results concerning the 2 choices method? Instead of choosing one bin uniformly at random, we select 2 potential bins and place the ball in the least loaded one, breaking ties arbitrarily.

I would be tempted to say that $$ E[X] = n \left( 1- \frac{2}{n} \right)^n \approx \frac{n}{e^{2}} $$

but is it true?

Moreover, are there known results when the probability is not uniform? For example, what would happen if the probability to choose a bin depends on the number of ball inside it?

Thanks in advance


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.