# How does the probabilty for universal hashing work out?

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?

• That is a definition to achieve. Did you look at the Wegman-Carter Dec 12, 2020 at 18:23
• This video on the subject might clear things up. Dec 12, 2020 at 21:09