288 views
0 votes
0 votes
Define a family $\mathscr{H}$ of hash functions from a finite set $U$ to a finite set $B$ to be universal if for all pairs of distinct elements $k$ and $l$ in $U$,

$Pr\{h(k) = h(l)\} \leq \epsilon$

where the probability is over the choice of the hash function $h$ drawn at random from the family $\mathscr{H}$. Show that an $\epsilon-$universal family of hash functions must have

$\epsilon \geq \frac{1}{|B|} – \frac{1}{|U|}$

Please log in or register to answer this question.

Related questions

0 votes
0 votes
1 answer
3
0 votes
0 votes
0 answers
4