0
$\begingroup$

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

$\endgroup$

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.