Throw $n$ balls into $n$ bins. Each bin is selected uniformly at random but the process is only pairwise independent. Call the maximum number of balls in any bin the max load.

Lemma 2 in these notes tells us that the max load is at most $\sqrt{2n}$ with probability at least $1/2$.

Can we give an explicit uniform but only pairwise independent random process for selecting the next bin to put a ball into which gives the expected max load to be $\Theta(\sqrt{n})$ asymptotically?


Here's how to do it.

First, choose a random $k$ between 1 and $n$ to be the "crowded bin". Next, choose a random permutation $\pi$ of $1,2,\ldots, n-1$.

Now, for $1 \leq i \leq n-1$,
$$ \mbox{put ball } i \mbox{ into bin } \begin{cases} k \ \ \ \ \ \ \ \ \ \ \ \ \mbox{with probability }\ \frac{1}{\sqrt{n}}, \\ k + \pi(i) \mbox{ with probability }1 - \frac{1}{\sqrt{n}}, \end{cases}$$ where the sum is taken mod $n$.

Put ball $n$ into a random bin.

Consider balls $i,j$ where $1 \leq i < j \leq n-1$. Both these balls go into the crowded bin with probability $\frac{1}{n}$, and the crowded bin is equally likely to be any of the $n$ bins. And if they don't both go into the crowded bin, by symmetry they are equally likely to be in any two different bins. Thus, the bins these two balls are placed into are independent.

Since ball $n$ is placed into a random bin, it is independent of the other balls.

The expected max load here is essentially the expected number of balls in the crowded bin, which is $$\frac{n-1}{\sqrt{n}}+\frac{1}{n} = \sqrt{n} + o(1).$$

  • $\begingroup$ That is really nice and clear. Thank you. $\endgroup$ – felix Apr 11 '15 at 8:49

Not the answer you're looking for? Browse other questions tagged or ask your own question.