# 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. Feb 16, 2021 at 22:45