3
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Can you make your question self-contained such that someone knowledgeable that hasn't read this book and its exact definitions can answer it? $\endgroup$
    – orlp
    Mar 19 '20 at 17:55
  • $\begingroup$ @orlp I added definition for $k$-universal hash function. I think rest are standard terms. $\endgroup$
    – Root
    Mar 19 '20 at 18:02
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Mar 19 '20 at 18:10
  • $\begingroup$ @D.W. I edited for additional information. See if it self-contained now. $\endgroup$
    – Root
    Mar 20 '20 at 11:42
  • 1
    $\begingroup$ What is your intermediate result, i.e., the expression you are unable to simplify? $\endgroup$
    – xskxzr
    Mar 21 '20 at 4:15
1
$\begingroup$

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

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