2
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Consider the hash family $\mathcal{H} = \{h_i : i \in N\}$ where $h_i$ is the constant function $h_i(x) = i$ for all $x \in U$. $\endgroup$ – arnab Mar 11 '13 at 0:13
  • 1
    $\begingroup$ Also, "independent" is a technical term. The variables $x$, $y$, $z_1$, and $z_2$ are not "completely independent"; they're not even random. Those values are chosen by an all-powerful malicious adversary who wants to break your code; hence the devil horns on the quantifer. $\endgroup$ – JeffE Mar 11 '13 at 3:06
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, that makes sense. I am quite new to probability theory as well, so your example helped me. $\endgroup$ – Andreas T Mar 11 '13 at 10:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.