Determining the Minimum Size of a Universal Hash Family
I'm working on understanding universal hash families and encountered a problem that I'm struggling to solve. The problem is as follows:
Consider a family of hash functions $ H = \{h_1, \ldots , h_k\} $, where each function $ h_i $ maps the set ($\{a, b, c, d\}$) to ($\{0, 1\}$). I am interested in determining the minimum value of $ k $ for $ H $ to qualify as a universal hash family. To clarify, a family of functions $ H $ is defined as universal if, for every distinct pair $ u $ and $ v $, the probability $ \Pr_{h \in H} [h(u) = h(v)] $ is at most $ \frac{1}{m} $, where $ m $ is the size of the hash table.
My Attempt
I understand that the universality of a hash family is tied to the probability of collisions for distinct elements under different hash functions. However, I am not sure how to approach the calculation of the minimum number of functions needed in this particular case, especially considering the specific mapping of the elements and the size of the hash table.
Seeking Help
Could anyone provide insights or a methodological approach to solve this problem? Any guidance on how to calculate the minimum size of $ k $ in this context would be greatly appreciated.