Problem Detail: I am currently learning how randomised Hashing works. So, you have a class (aka family) $H$ of hash functions, each of which maps the universe $U$ to the hash table $N$. That class is called “strongly universal” or “pairwise independent” if $forall x,y in U, x neq y: forall z_1,z_2 in N: Prlimits_{h in H}[h(x) = z_1 land h(y) = z_2] leq frac{1}{|N|^2}$. In words: pick any two elements from the universe and two from the hash table. If you pick a hash function from the hash class at random, the probability that these two elements are mapped to each other by $h$ is less or equal than $frac{1}{|N|^2}$. Now, what is confusing me is that, since $x$, $y$, $z_1$ and $z_2$ are all completely independent, it looks to me like you could just “remove” one pair from the equation and still get the same result. That would be $forall x in U: forall z in N: Prlimits_{h in H}[h(x) = z] leq frac{1}{|N|}$. This, however, is called “uniformity” of a hash class. Could someone explain to me why these two attributes are different from one anoter?
Asked By : Andreas T
Answered By : Yuval Filmus
Arnab provided the answer. The family $mathcal{H} = {h_i : i in N}$, where $h_i(x) = i$ for all $x in U$, is uniform but not pairwise independent. Similarly you can come up with families which are pairwise but not $3$-wise independent, and so on. To give a simple example, let $X,Y$ be two independent uniformly random coin tosses. Each of the possibilities $(H,H),(H,T),(T,H),(T,H)$ has the same probability. Now let $X’$ be a uniformly random coin toss, and let $Y’ = X’$. Now it is not true that each of the four possibilities of $(X’,Y’)$ has the same probability, but each of $X’,Y’$ by itself is a uniformly random coin toss.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/10447 Ask a Question Download Related Notes/Documents
