$2$-universal family of hash functions and $\varepsilon$-good

Question

Let $V=\{0,1\}^m$ and $H\subseteq V\to V$ a $2$-universal family of hash functions. Fix two sets $A,B\subseteq V$. Call a hash function $h\in H$ $\varepsilon$-good for $A,B$ if: $$ |\Pr_{x\in V} [x\in A \cap h(x)\in B]-\rho(A)\rho(B)|\leq \varepsilon $$ where $\rho(C) = \frac{|C|}{|V|}$. Prove that for any $A,B\subseteq V, \varepsilon>0$, $$ \Pr_{h\in H} [h \space is \space not \space \varepsilon-good \space for \space A,B] \leq \frac{\rho(A)\rho(B)(1-\rho(B))}{\varepsilon^2 |V|} \leq \frac{1}{\varepsilon^2 |V|}$$ Any suggestions?

Answer 1

Note that the problem requires strong $2$-universality of $H$, i.e. pairwise independence; this implies uniformity (a key is equally likely to map to any hash).

Instead of $V$, suppose $H$ maps from an arbitrary set $M$ to an arbitrary set $N$. Define an indicator random variable $I_x$ for each key $x\in M$ that is $1$ when $x\in A$ and $h(x)\in B$.

• Because of uniformity, $\Pr(I_x)=\frac{|A|}{|M|}\cdot\frac{|B|}{|N|}$; call this probability $p$. Thus $\mathbb E\left[\sum_xI_x\right]=p|M|$.
• Because of strong $2$-universality, the $I_x$ are pairwise independent and $\mathsf{Var}\left[\sum_xI_x\right]=\sum_x\mathsf{Var}[I_x]=p(1-p)|M|$.

Apply Chebyshev's inequality: $$\Pr(h\text{ is not }\varepsilon\text{-good})=\Pr\left(\left|\sum_xI_x-p|M|\right|\ge\varepsilon|M|\right)\le\frac{p(1-p)|M|}{\varepsilon^2|M|^2}=\frac{p(1-p)}{\varepsilon^2|M|}<\frac1{\varepsilon^2|M|}$$ In the case where $M=N=V$, then: $$\Pr(h\text{ is not }\varepsilon\text{-good})\le\frac{\rho(A)\rho(B)(1-\rho(A)\rho(B))}{\varepsilon^2|V|}<\frac1{\varepsilon^2|V|}$$