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 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})$.

pairwise independenceselection process you speak of? $\endgroup$ – cardinal Apr 10 '15 at 11:25