# Maximum occupancy balls in bins with limited independence

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

• I think the answer should be $n^{1/k}$, but it will take me some time to formulate some rigorous justification. Till then, a sketch: The idea is that $k$-wise independence controls what happens when load sizes are $\leq k$. So consider throwing groups of $m < n$ balls at a time. Pick $m$ such that $k$-wise independence ensures the expected size of the max load size from just that group equals $k$. I think this should set $m = \Theta(kn^{1-1/k})$. Then we have $n/m$ groups, so that max-loaded bin for the whole process is at most $k\cdot n/m \approx n^{1/k}$. ... – usul Mar 23 '15 at 20:08
• ... Also note (a) $\log n/\log\log n$ comes from solving $k = n^{1/k}$, so this conjecture is tight both at the lower bound of $k=2$ and the upper bound of $k\approx \log n/\log\log n$; and (b) this latter is an upper bound because with more independence than $\log n/\log \log n$ you still get the same answer (this shouldn't be hard to show, unless I am very mixed up). – usul Mar 23 '15 at 20:18
• That's only a sketch for the upper bound (should've mentioned), but seems likely to be tight to me.... – usul Mar 23 '15 at 20:38
• @usul Thank you. That would be a really attractive and simple result. – valjarett Mar 24 '15 at 8:39
• Maybe this can be solved by combining tail bounds for $k$-wise independent random processes from mathoverflow.net/questions/59784/bound-the-tail-distribution/… with the observation on how to use Heoffding's bound for this problem in cs.cmu.edu/afs/cs/project/pscico-guyb/realworld/www/slidesS14/… ? – felix Apr 5 '15 at 11:38

Consider the probability that $k$ particular balls go into the same bin. By $k$-wise independence, this is $n^{-k}$ for each bin, or $n^{-k+1}$ when we sum over all bins. On the other hand, if we choose a random $k$-tuple of indices, the probability that these are all sent to the same bin is at least the probability that all $k$ are sent to the bin with the highest load $X_n$, so if we condition on $X_n$, the probability is at least ${X_n \choose k} / {n \choose k}$.
Unfortunately, $x \choose k$ is not always convex as a function of $x$, so we have to modify it slightly to use convexity. For $k \in \mathbb{N}, x\in \mathbb{R}$, define ${x \choose k}^+ = {\begin{cases} {x \choose k}, x \gt k-1 \newline 0, x \le k-1\end{cases}} = \frac{1}{k!}\prod_{i=0}^{k-1} \max (0,x-i).$ Since each factor $\max (0,x-i)$ is convex and nonnegative, the scaled product ${x \choose k}^+$ is convex.
By Jensen's inequality, the probability $k$ balls go to the same bin is at least ${E[X_n] \choose k}^+ / {n \choose k}$. So, $k$-wise independence implies
$$\begin{eqnarray}{E[X_n] \choose k}^+ &\le & {n \choose k}n^{-k+1} \newline &\le & \frac{n}{k!} \newline \prod_{i=0}^{k-1} \max(0,X_n-i) &\le & n \newline \max(0,E[X_n]-k+1)^k &\le & n \newline E[X_n] &\le & \sqrt[k]{n} + k-1. \end{eqnarray}$$
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})$".