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$?
> 
> 
> 



Maximum occupancy balls in bins with limited independence
I think <https://arxiv.org/abs/1502.05729> might be at least a partial answer to my question. It shows "a $k$-independent family of functions that imply [heaviest loaded bin] size is $\Omega(n^{1/k})$".


