12
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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}$. ... $\endgroup$ – usul Mar 23 '15 at 20:08
  • 1
    $\begingroup$ ... 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). $\endgroup$ – usul Mar 23 '15 at 20:18
  • $\begingroup$ That's only a sketch for the upper bound (should've mentioned), but seems likely to be tight to me.... $\endgroup$ – usul Mar 23 '15 at 20:38
  • $\begingroup$ @usul Thank you. That would be a really attractive and simple result. $\endgroup$ – valjarett Mar 24 '15 at 8:39
  • $\begingroup$ 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/… ? $\endgroup$ – felix Apr 5 '15 at 11:38
5
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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