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: \Pr\limits_{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: \Pr\limits_{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
0 comments:
Post a Comment
Let us know your responses and feedback