Throw $n$ balls into $n$ bins and let $X_n$ be the maximum occupancy. That is the maximum number of balls found in any bin.

If you throw the balls uniformly and independently it is known that $\mathbb{E}(X_n) = \Theta(\log{n}/\log{\log{n}})$. If the process is merely pairwise independent (but still uniform) then it is known that $\mathbb{E}(X_n)$ can grow as quickly as $\Theta(\sqrt{n})$.

If the random process is $k$-wise independent, then for each $k$ there will be some tight asymptotic upper bound for $\mathbb{E}(X_n)$.

How do the asymptotics of a tight upper bound for $\mathbb{E}(X_n)$ depend on $k$?

This question may be hard to answer precisely but approximate answers and even conjectures would be very helpful too. Sometimes $k=4$ is a transition point as you can then use more powerful moment methods but I am not sure how to do that usefully here.

What are the asymptotics for a tight upper bound for $\mathbb{E}(X_n)$ when $k=4$?

1more comments