2

I can't seem to get my head around a following conclusion:

Def: H is a finite set of hashing functions from U to [m] (set of size m). We'll call H universal if: $\forall x,y; x\ne y $ there exists $\frac{|H|}m$ functions $h\in H$ such that $h(x)=h(y)$.

Now, the conclusion should be that for random chosen $h\in H $ and $\forall x,y; x\ne y $ chance of collision between x,y is $\frac{1}m$.

Could anyone explain it to me, please?

My solution:

$\forall x,y;x\ne y$ is the chance that we pick $h\in H$ that causes a collision following fraction: $\frac{\text{Functions that cause collision}}{\text{All functions}}=\frac{\frac{|H|}m}{|H|}=\frac{1}m$

Is it correct?

Quimby
  • 168
  • https://cs.stackexchange.com/questions/127688/proving-that-the-two-definitions-of-universal-class-of-hash-function-are-equival This is the way I made an attempt – Abhishek Ghosh Jun 27 '20 at 05:19

0 Answers0