Two choices:

\(m\) balls and \(n\) bins. Each ball is randomly and fully independently assigned two target bins that it is allowed to be placed in. It chooses the less crowded of the two.

The overload is the fill of the fullest bin minus \(\frac{m}{n}\).

Theorem. - Overload is \(\mathcal{O}(\log m)\) whp in \(m\) - Overload is \(\mathcal{O}(\log\log n)\) whp in \(n\)

Proof.

Actually this is basically a question that my friend Nathan told me a while ago.

Here’s a really simple argument: Imagine you’re at overload \(h\). We play the following casino game:

you keep placing balls until you either hit overload \(2h\) or hit \(0\), at which time you lose.

Observe that the probability that it is like \(3^{h}\) times more likely that you will be at \(0\) than at \(2h\).

Now consider the following thought experiment:

You have a game that you win with probability \(n^{-100}\). You play the game \(n\) times. What is the probability that you win? Answer at most \(n^{-99}\).

So in summary, this proves that overload is \(\mathcal{O}(\log m)\).

As for the other result I’m not sure, but will think about it sometime.