14
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Can you clarify the pairwise independence selection process you speak of? $\endgroup$
    – cardinal
    Apr 10, 2015 at 11:25
  • $\begingroup$ A curiously related question posted on math.SE at about the same time. $\endgroup$
    – cardinal
    Apr 10, 2015 at 11:26
  • $\begingroup$ @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? $\endgroup$
    – Simd
    Apr 10, 2015 at 13:02

2 Answers 2

3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ This is really nice and clear. Thank you. $\endgroup$
    – Simd
    Apr 16, 2015 at 10:40
3
+50
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Simd
    Apr 13, 2015 at 17:42
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Will Sawin
    Apr 13, 2015 at 17:49
  • $\begingroup$ Ah yes. I misread what you wrote originally. Thank you. $\endgroup$
    – Simd
    Apr 13, 2015 at 17:59
  • $\begingroup$ 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. $\endgroup$
    – Simd
    Apr 14, 2015 at 12:41
  • $\begingroup$ @dorothy Without pairwise, it's $n^{1/k}$, right? $\endgroup$
    – Will Sawin
    Apr 14, 2015 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.