# generalizing ball-bin problem to k-universal family

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

• Can you make your question self-contained such that someone knowledgeable that hasn't read this book and its exact definitions can answer it?
– orlp
Mar 19 '20 at 17:55
• @orlp I added definition for $k$-universal hash function. I think rest are standard terms.
– Root
Mar 19 '20 at 18:02
• That's not the issue. The issue is, what problem are you solving? All that I've got is that you're looking to "generalize this" (I'm not sure what "this" is) to k-universal family. I suggest you provide a self-contained description of the specific ball-bin problem you're working on and what is the problem statement and what is your specific question about it.
– D.W.
Mar 19 '20 at 18:10
• @D.W. I edited for additional information. See if it self-contained now.
– Root
Mar 20 '20 at 11:42
• What is your intermediate result, i.e., the expression you are unable to simplify? Mar 21 '20 at 4:15

## 1 Answer

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