Throw $n$ balls into $n$ bins, and let $X\_n$ be the max load. That is the number of balls in the fullest bin. It is known that if the balls are thrown uniformly and independently at random then $\mathbb{E}(X\_n) = \Theta(\lg{n}/\lg{\lg{n}})$. 


If instead, for each ball considered sequentially we look at two bins chosen uniformly and independently at random, and throw the ball into the least full one (or a random one if they are equally full), then it is known that $\mathbb{E}(X\_n) = \Theta(\lg{\lg{n}})$, a dramatic decrease. See [this survey](http://people.cs.umass.edu/~ramesh/Site/PUBLICATIONS_files/MRS01.pdf) for example for more discussion of this phenomenon. 



> 
> If we still look at two bins for each ball and the bins are still selected uniformly but only with pairwise independence, what is a tight asymptotic upper bound for $\mathbb{E}(X\_n)$?
> 
> 
> 


We know that in the case of pairwise independence, if we just looked at one bin at a time, then a tight upper bound is $\mathbb{E}(X\_n) = \Theta(\sqrt{n})$. 



The power of two random choices with pairwise independence
Will Sawin's idea seems good. Here is a slightly simpler way to get a similar pairwise independent distribution where the maximum load with under a binary choice is still $\Theta(\sqrt{n}).$


Let $\lbrace x\_i \rbrace$ be a random sequence of bins that is symmetric under permuting bins and indices so that a random set of about $\sqrt{n}$ balls go into one bin (at least $\lfloor \sqrt{n} \rfloor$ go into one bin, but a mixture may be needed), and the other balls go into distinct bins. This can be done so that the chance that two balls go into the same bin is $1/n$ so they are pairwise independent.


Choose a random permutation $\pi$ so that for any $i$, $\pi(i)$ is uniform. For example, we can choose $\pi$ to be uniform on $S\_n$, or we can choose a random translation mod $n$. 


Consider the sequence of pairs $\lbrace (x\_i, \pi(x\_i)) \rbrace$. 


The first coordinates are pairwise independent by the construction of $\lbrace x\_i \rbrace$. The second coordinates are pairwise independent by the symmetry of permuting bins and the pairwise independence of $\lbrace x\_i \rbrace$. The probability that $x\_i = \pi(x\_j)$ is $1/n$ by the construction of $\pi$. So, these are pairwise independent.


Since at least $\lfloor \sqrt{n} \rfloor$ of the pairs are the same $(x,\pi(x))$, at least $\lfloor \sqrt{n} \rfloor/2$ balls have to go into either bin $x$ or bin $\pi(x)$, so the maximum load is $\Theta(\sqrt{n})$.


