5
$\begingroup$

Hey for universal hashing we say the following:

Definition:
A randomized algorithm $H$ for constructing hash functions $h\colon U \to \{1,\ldots,M\}$ is universal if for all $x \neq y$ in $U$, we have $\Pr_{h\gets H} [h(x) = h(y)] \leq 1/M$

I actually just can´t understand how the probability can be $1/M$ in any case. I alway try to think about any random function mod M as example and compare it with rolling a dice, but with a dice we have for every instance a probabilty of 1/6 as we have 1/M for mod M. But when I roll a dice two times after I have at least $\frac{1}{6}^2$ but saying we have binomial probabilty it looks even worse thinking that the dice would be thrown y times.

Can you help me understand how 1/m could be reached within this context?

Improve this question
$\endgroup$
3
  • $\begingroup$ That is a definition to achieve. Did you look at the Wegman-Carter $\endgroup$
    – kelalaka
    Dec 12, 2020 at 18:23
  • 1
    $\begingroup$ This video on the subject might clear things up. $\endgroup$
    – Modal Nest
    Dec 12, 2020 at 21:09
  • 1
    $\begingroup$ Actually it's the follow up here that answers your question. $\endgroup$
    – Modal Nest
    Dec 12, 2020 at 21:34

1 Answer 1

Reset to default
4
$\begingroup$

Actualy chance of 2 dice throws to have the same value is 1\6, not 1\36. And definition also compares 2 values.

What you are asking is called https://en.wikipedia.org/wiki/Birthday_problem and it is still present even with universal hashing. Or dice throws. If more than 2 are compared.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thank you! This link made it even more clear regarding birthday problem and rolling a dice. $\endgroup$
    – OuttaSpaceTime
    Dec 14, 2020 at 7:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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