The power of two random choices with pairwise independence

Question

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

Answer 1

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

Answer 2

Let me sketch why I think the answer is still $\Theta(\sqrt{n})$.

Given any distribution such that, for each pair of the $2n$ random numbers, the probability that they are the same is $1/n$, we can symmetrize it by applying a random permutation in $S_n$.

Consider the distribution in which we choose $c \sqrt{n}$ of the $2n$ pairs at random. For each pair, we set one equal to $1$ and the other equal to $2$. This contributes $c /2n$ to the probability that two elements in different pairs are the same, and $0$ to the probability that two elements in the same pair are the same. Then let's balance that out by choosing $c/2$ pairs and setting both equal to $3$, contributing $c/2n$ to the probability that two elements in the same pair are the same. Then the elements we have not yet chosen can be distributed between $4$ and $n$ in such a way that they are less likely than normal to be the same, by ensuring that the numbers $4$ to $n$ each occur about the same number of times, and assigning those randomly. Choosing the correct number $c$ we should be able to balance the probability that two numbers are equal to be exactly $1/n$, or very close. Symmetrizing, we get an acceptable distribution (or we have to mix with a very slight quantity of a different distribution to get it exactly right.)

Then because we give the system $c \sqrt{n}$ choices between the same two bins, the max load is $c \sqrt{n}/2 = \Theta(\sqrt{n})$.