generalizing ball-bin problem to k-universal family

Question

I am trying to solve a question in the book on Probability and Computing by Michael Mitzenmacher, Eli Upfal. The question asks to generalize ball-bin problem for 2-universal hashing to $k$-universal hashing.

In the standard bin-ball problem setup there are $n$ bins and $n$ balls. These $n$ balls are randomly thrown (independently) in $n$ boxes and we try to find maximum occupancy in any bin. This can be done by considering a hash function $h: [n] \to [n]$. We say that ball $i$ goes in bin $h(i)$. In this case hash function comes from a 2-universal family. It is shown that for 2-universal hash family, max occupancy is $l_{\max}=1+2\sqrt n$ with probability greater than $\frac{1}{2}$. It follows with usual application of Markov's inequality. Now we try to generalize this to hash $h$ coming from a $k$-universal family and find $l_{\max}$ so that max occupancy is less than that with probability $\frac{1}{2}$.

I tried to do following: First set up indicator variable as in previous case for 2-universal problem

$X_{ij}=1$ if ball i goes in bin $j$. Now load for bin $i$ is $X=\sum_{j=1}^{n}X_{ij}$.

Since hash is now $k$-universal we try to go for Markov on $k^{\text{th}}$ moment instead of Markov (which comes from 1-st moment) to get probability bound of $\frac{1}{2n}$. In the end we apply union bound. But I am unable to simplify expression for $k$-th moment in this context to get an answer.

Definition of $k$-universal hash function

$\mathrm{Pr}(h({i_{1}})=h({i_{2}})=\cdots=h({i_{k}}))= \frac{1}{n^{k-1}}$ for any $k$ distinct elements $i_1,\ldots,i_k$.

Answer 1

Let $B_j$ be the number of balls in the $j$'th bin. Then $$ \mathbb{E}\left[\sum_{j=1}^n \binom{B_j}{k}\right] = \sum_{i_1 < \cdots < i_k} \Pr[h(i_1) = \cdots = h(i_k)] = \frac{\binom{n}{k}}{n^{k-1}} \leq \frac{n}{k!}. $$ Let $C_j = B_j - (k-1)$. Then $$ \mathbb{E}\left[\sum_{j=1}^n C_j^k\right] \leq k! \mathbb{E}\left[\sum_{j=1}^n \binom{B_j}{k}\right] \leq n, $$ and so with probability at least $1/2$, $$ \max_j C_j^k \leq \sum_{j=1}^n C_j^k \leq 2n, $$ hence $C_j \leq (2n)^{1/k}$, implying that $l_{\max} \leq (2n)^{1/k} + k-1$.