# How to show independence and uniform distribution of hash codes from k-wise independent hash functions?

Most definitions of a $$k$$-wise independent family of hash functions I have encountered state that a family $$H$$ of hash functions from $$D$$ to $$R$$ is k-wise independent if for all distinct $$x_1, x_2,\dots, x_k \in D$$ and $$y_1, y_2,\dots, y_k \in R$$,

$$\mathbb{P}_{h \in H}(h(x_1) = y_1, h(x_2) = y_2, \dots, h(x_k) = y_k) = \frac{1}{|R|^k}$$

The Wikipedia article on k-wise independent hash functions (which uses the above definition) claims that the definition is equivalent to the following two conditions:

(i) For all $$x \in D$$, $$h(x)$$ is uniformly distributed in $$R$$ given that $$h$$ is randomly chosen from $$H$$.

(ii) For any fixed distinct keys $$x_1, x_2,\dots, x_k \in D$$, as $$h$$ is randomly drawn from $$H$$, the hash codes $$h(x_1), h(x_2), \dots, h(x_k)$$ are independent random variables.

It is not obvious to me how one proves (i) from the above definition without explicitly assuming (ii) in the definition as well (and vice-versa). How is the definition sufficient for proving both (i) and (ii)?

Throughout, we assume that $$|D| \geq k$$.
Suppose that $$H$$ satisfies, for all distinct $$x_1,\dots,x_k \in D$$ and all $$y_1,\ldots,y_k \in R$$, $$\Pr_{h \in H}[h(x_1)=y_1,\ldots,h(x_k)=y_k] = \frac{1}{|R|^k}.$$ Now let $$x \in D$$ be arbitrary. Since $$|D| \geq k$$, we can find $$x_2,\ldots,x_k \in D$$ such that $$x,x_2,\ldots,x_k$$ are distinct. For each $$y \in R$$, $$\Pr_{h \in H}[h(x)=y] = \sum_{y_2,\ldots,y_k \in R} \Pr_{h \in H}[h(x)=y,h(x_2)=y_2,\ldots,h(x_k)=y_k] = \\ \sum_{y_2,\ldots,y_k \in R} \frac{1}{|R|^k} = \frac{|R|^{k-1}}{|R|^k} = \frac{1}{|R|}.$$ This proves (i). To see (ii), let $$x_1,\ldots,x_k \in D$$ be distinct. Then for all $$y_1,\ldots,y_k$$, $$\Pr_{h \in H}[h(x_1)=y_1,\ldots,h(x_k)=y_k] = \frac{1}{|R|^k} = \prod_{i=1}^k \frac{1}{|R|} = \prod_{i=1}^k \Pr_{h \in H}[h(x_i) = y_i].$$
In the other direction, suppose that (i) and (ii) hold. Then for all distinct $$x_1,\ldots,x_k \in D$$ and $$y_1,\ldots,y_k \in R$$, $$\Pr_{h \in H}[h(x_1)=y_1,\ldots,h(x_k)=y_k] = \prod_{i=1}^k \Pr_{h \in H}[h(x_i) = y_i] = \prod_{i=1}^k \frac{1}{|R|} = \frac{1}{|R|^k} .$$
• Nice, many thanks! How did it occur to you to view the event ${h(x) = y}$ as the union of events $\{h(x) = y, h(x_2) = y_2, ..., h(x_k) = y_k\}$ for all $(y_2, ..., y_k) \in R^{k-1}$? While I can understand and appreciate your proof, I'm concerned something crucial in my understanding of basic probability theory is missing for me to have this kind of intuition for such problems.