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.

What happens if we still look at two bins for each ball and the bins are still selected uniformly but only with pairwise independence?