<p>Here's how to do it.</p>

<p>First, choose a random $k$ between 1 and $n$ to be the "crowded bin".
Next, choose a random permutation $\pi$ of $1,2,\ldots, n-1$.</p>

<p>Now, for $1 \leq i \leq n-1$,<br>
$$ \mbox{put ball } i \mbox{ into bin } 
\begin{cases} k \ \ \ \ \ \ \ \ \ \ \ \ \mbox{with probability }\ \frac{1}{\sqrt{n}}, \\
k + \pi(i) \mbox{ with probability }1 - \frac{1}{\sqrt{n}},
\end{cases}$$
where the sum is taken mod $n$.  </p>

<p>Put ball $n$ into a random bin.</p>

<p>Consider balls $i,j$ where $1 \leq i &lt; j \leq n-1$. The bins these two balls fall into are independent. They both go into the crowded bin with probability $\frac{1}{n}$, and the crowded bin is equally likely to be any of the $n$ bins. And if they don't both go into the crowded bin, by symmetry they are equally likely to be in any two different bins. Thus, the bins these two balls are placed into are independent.</p>

<p>Since ball $n$ is placed into a random bin, it is independent of the other balls. </p>

<p>The expected max load here is essentially the expected number of balls in the crowded bin, which is
$$\frac{n-1}{\sqrt{n}}+\frac{1}{n} = \sqrt{n} + o(1).$$</p>

CC BY-SA 3.0
2015-04-11T08:51:38.920Z
Thank you very much. This is a really nice and clear answer.
Simd
CC BY-SA 3.0
2015-04-11T15:55:48.647Z
I suppose you don't literally mean "the sum is taken mod $n$" as that would mean you sometimes place in bin $0$ which doesn't exist.
Simd
CC BY-SA 3.0
2015-04-11T16:50:30.863Z
@felix: not quite literally: $0 \equiv n$ (mod $n$).
Peter Shor 
CC BY-SA 3.0
2015-04-11T18:51:31.663Z
I am sorry if this is a dim question, but say I want to throw $m>n$ balls into $n$ bins with the same distribution. That is uniform for every throw, pairwise independent choice of bins and the expected max load being $\Theta(\sqrt{m})$. The method you describe has a special role for the last ball. What do we do then?
Simd
CC BY-SA 3.0
2015-04-11T19:03:30.517Z
In my case I would like to throw $2n$ balls into $n$ bins. I could just run your process twice with the second run completely independent of the first but that doesn't seem right.
Simd
CC BY-SA 3.0
2015-04-11T19:58:03.683Z
Instead of a random permutation $\pi$, use a random reordering of the sequence $1,1,2,2, 3,3,\ldots,n-1,n-1$. And instead of probability $1/\sqrt{n}$, figure out which probability makes the first $2n-2$ balls pairwise independent. And just toss the last two balls into random bins. (There's undoubtedly a better way of dealing with the last two balls, but it won't make a substantial difference in the expected max load and it will make everything more complicated.)
Peter Shor 
CC BY-SA 3.0
2015-04-11T01:05:14.210Z
2015-04-11T01:22:51.917Z
2015-04-11T01:22:51.917Z
Peter Shor 
<p>This question was previously posted at <a href="https://math.stackexchange.com/questions/1220292/example-of-pairwise-independent-random-process-with-expected-max-load-sqrtn">https://math.stackexchange.com/questions/1220292/example-of-pairwise-independent-random-process-with-expected-max-load-sqrtn</a> where it has no answers. I now realise this is relevant to hashing so I am reposting it here.</p>

<p>Throw $n$ balls into $n$ bins.  Each bin is selected uniformly at random but the process is only pairwise independent.  Call the maximum number of balls in any bin the <strong>max load</strong>.</p>

<p>Lemma 2 in these <a href="http://www.cs.cmu.edu/afs/cs/project/pscico-guyb/realworld/www/slidesS14/load-balancing.pdf" rel="nofollow noreferrer">notes</a> tells us that the max load is at most $\sqrt{2n}$ with probability at least $1/2$. </p>

<blockquote>
  <p>Can we give an explicit uniform but only pairwise independent random process for selecting the next bin to put a ball into which gives the
  expected max load to be $\Theta(\sqrt{n})$ asymptotically?</p>
</blockquote>

CC BY-SA 3.0
2015-04-10T19:07:39.530Z
http://mathoverflow.net/a/202583
Emil Jeřábek
CC BY-SA 3.0
2015-04-11T17:27:40.383Z
As @EmilJeřábek implies, it seems that you can do it more generally for $k$-independence too, using theorem 1 of http://fr.arxiv.org/abs/1502.05729.
The paper points out that for pairwise independence you can use theorem 8 of http://www.brics.dk/RS/97/16/BRICS-RS-97-16.pdf, but it seems false (i think that the universal hash family used there is not 2-independent).
didest
CC BY-SA 3.0
2015-04-11T20:03:35.073Z
@DiegodeEstrada Thank you. It is also certainly very interesting if there indeed such an error in that paper.
Simd
<pr.probability><randomness><hash-function>
Example of pairwise independent random process with expected max load $\sqrt{n}$
Simd
# Example of pairwise independent random process with expected max load $\sqrt{n}$

(Asked by: username_0 on 2015-04-10)

This question was previously posted at <https://math.stackexchange.com/questions/1220292/example-of-pairwise-independent-random-process-with-expected-max-load-sqrtn> where it has no answers. I now realise this is relevant to hashing so I am reposting it here.

Throw $n$ balls into $n$ bins. Each bin is selected uniformly at random but the process is only pairwise independent. Call the maximum number of balls in any bin the **max load**.

Lemma 2 in these [notes](http://www.cs.cmu.edu/afs/cs/project/pscico-guyb/realworld/www/slidesS14/load-balancing.pdf) tells us that the max load is at most $\sqrt{2n}$ with probability at least $1/2$.

> Can we give an explicit uniform but only pairwise independent random process for selecting the next bin to put a ball into which gives the
> expected max load to be $\Theta(\sqrt{n})$ asymptotically?

**Tags:** pr.probability, randomness, hash-function
> **Comments:**
> **username_1**: http://mathoverflow.net/a/202583  
> **username_2**: As @EmilJeřábek implies, it seems that you can do it more generally for $k$-independence too, using theorem 1 of http://fr.arxiv.org/abs/1502.05729. The paper points out that for pairwise independence you can use theorem 8 of http://www.brics.dk/RS/97/16/BRICS-RS-97-16.pdf, but it seems false (i think that the universal hash family used there is not 2-independent).  
> **username_0**: @DiegodeEstrada Thank you. It is also certainly very interesting if there indeed such an error in that paper.  

---

## 1 answers

### Answer by username_3 on 2015-04-11. Score: 8 | Accepted answer

Here's how to do it.

First, choose a random $k$ between 1 and $n$ to be the "crowded bin".
Next, choose a random permutation $\pi$ of $1,2,\ldots, n-1$.

Now, for $1 \leq i \leq n-1$,  
$$ \mbox{put ball } i \mbox{ into bin }
\begin{cases} k \ \ \ \ \ \ \ \ \ \ \ \ \mbox{with probability }\ \frac{1}{\sqrt{n}}, \\
k + \pi(i) \mbox{ with probability }1 - \frac{1}{\sqrt{n}},
\end{cases}$$
where the sum is taken mod $n$.

Put ball $n$ into a random bin.

Consider balls $i,j$ where $1 \leq i < j \leq n-1$. The bins these two balls fall into are independent. They both go into the crowded bin with probability $\frac{1}{n}$, and the crowded bin is equally likely to be any of the $n$ bins. And if they don't both go into the crowded bin, by symmetry they are equally likely to be in any two different bins. Thus, the bins these two balls are placed into are independent.

Since ball $n$ is placed into a random bin, it is independent of the other balls.

The expected max load here is essentially the expected number of balls in the crowded bin, which is
$$\frac{n-1}{\sqrt{n}}+\frac{1}{n} = \sqrt{n} + o(1).$$

> **Comments:**
> **username_0**: Thank you very much. This is a really nice and clear answer.  
> **username_0**: I suppose you don't literally mean "the sum is taken mod $n$" as that would mean you sometimes place in bin $0$ which doesn't exist.  
> **username_3**: @felix: not quite literally: $0 \equiv n$ (mod $n$).  
> **username_0**: I am sorry if this is a dim question, but say I want to throw $m>n$ balls into $n$ bins with the same distribution. That is uniform for every throw, pairwise independent choice of bins and the expected max load being $\Theta(\sqrt{m})$. The method you describe has a special role for the last ball. What do we do then?  
> **username_0**: In my case I would like to throw $2n$ balls into $n$ bins. I could just run your process twice with the second run completely independent of the first but that doesn't seem right.  
> **username_3**: Instead of a random permutation $\pi$, use a random reordering of the sequence $1,1,2,2, 3,3,\ldots,n-1,n-1$. And instead of probability $1/\sqrt{n}$, figure out which probability makes the first $2n-2$ balls pairwise independent. And just toss the last two balls into random bins. (There's undoubtedly a better way of dealing with the last two balls, but it won't make a substantial difference in the expected max load and it will make everything more complicated.)  

---

