In Theorem D.5 of Goldreich's Computational Complexity: A Conceptual Perspective, Goldreich states:

Let $m \leq n$ be integers, $H_n^m$ be a family of pairwise independent hash functions, and $S \subseteq \{0,1\}^n$. Then, for every $y \in \{0,1\}^m$ and every $\epsilon > 0$, for all but at most an $\frac{2^m}{\epsilon |S|}$ fraction of $h \in H_n^m$ it holds that:

$$(1-\epsilon) \frac{|S|}{2^m} < |\{ x \in S \, : \, h(x) = y \}| < (1+\epsilon) \frac{|S|}{2^m}.$$

To prove this theorem, Goldreich notes that the expected size of this set is $|S| / 2^m$. However, I do not see how this works for all $y$. For example, suppose $x = 0 \in S$, and let $y = 0$. Then, by definition the hashed set will always contain $x$, so the expected value should go to $1$ as $m \rightarrow \infty$, not $|S| / 2^m \rightarrow 0$. More generally, any time I pick a $y$ such that $y = h(x)$ for some $x \in S$, the expected value will go to $1$, not $0$. Why does this lemma hold for all $y$ if specific values will yield different expected values?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.