The power of two random choices with pairwise independence

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

• Can you clarify the pairwise independence selection process you speak of? – cardinal Apr 10 '15 at 11:25
• A curiously related question posted on math.SE at about the same time. – cardinal Apr 10 '15 at 11:26
• @cardinal The random process I am thinking of samples integers from $\{1,\dots,n\}$ uniformly at random (but with only pairwise independence). Each sample represents a bin. In the "power of two choices" version, two samples are taken at each turn and both bins are inspected. A ball is then placed in the bin which is least full (or a random bin if they are equally full). The whole process terminates when $n$ balls have been placed into bins. Does this clear it up? – dorothy Apr 10 '15 at 13:02

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

• This is really nice and clear. Thank you. – dorothy Apr 16 '15 at 10:40

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

• Thank you! One possibly very silly question. Is your definition equivalent to a uniform distribution plus pairwise independence? I was thinking we might want for each pair of the $2n$ random numbers, the probability that the first is $x$ and the second is $y$ for $x \ne y$ is $1/n^2$. This seems a little stronger but I could be mistaken. – dorothy Apr 13 '15 at 17:42
• @dorothy - we do want that, but if we apply a random permutation, as long as the probability that the first is not the second is $1-1/n$, then as we distribute this among the $n^2-n$ different pairs, each pair will have a probability $1/n^2$. – Will Sawin Apr 13 '15 at 17:49
• Ah yes. I misread what you wrote originally. Thank you. – dorothy Apr 13 '15 at 17:59
• Of course this now leaves open the intriguing question of the minimal $k$-wise independence for which having two choices does improve the expected max load. – dorothy Apr 14 '15 at 12:41
• @dorothy Without pairwise, it's $n^{1/k}$, right? – Will Sawin Apr 14 '15 at 13:02