0
$\begingroup$

The problem is:

Consider the universal hash function: $h(x, r) = x_1 r_1 + ... + x_d r_d \mod m$, with $m$ prime, where for an integer dimension d>0 you break up the key $x=(x_1,x_2, . . .,x_d), 0 \leq x_i < m$ into a sequence. Fix random coefficients $0 \leq r_i < m, i=1, . . .,d$.

Show an example of $m$ different items $x^{(1)}, . . .,x^{(m)}$ such that $P(h(x^{(1)}, r) = ... = h(x^{(m)}, r)) = \frac{1}{m}$. In other words, with probability $\frac{1}{m}$ not only two of these items map to the same bucket but all $m$ of them.

I'm not sure how this would be possible. Since the $h(x, r)$ is a universal hash function, we know $P(h(x,r) = h(y, r)) \leq \frac{1}{m}$. I imagine then that we need a set of $x^{(1)}, ..., x^{(m)}$ that all map to the same bucket. How would I construct such a set and prove the appropriate probability?

$\endgroup$
0
$\begingroup$

Hint: Consider $x^{(i)} = (i,0,0,\ldots,0)$. Then for what random $r$ do we have that all $x^{(i)}$'s get hashed to the same bucket?

$\endgroup$
  • $\begingroup$ If $r_1 = 0$, then I imagine these would all map to $0$, correct? $\endgroup$ – user484876 Nov 15 '17 at 16:54
  • $\begingroup$ @dr_seuss, precisely. And what is the probability that $r_1 = 0$? $\endgroup$ – Marcus M Nov 15 '17 at 16:55
  • $\begingroup$ It's $\frac{1}{m}$. Can't believe I missed that. Thank you! $\endgroup$ – user484876 Nov 15 '17 at 16:57

Your Answer

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