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