第九周作业
1. 证明The Matrix Method是Universal Hashing
满足Universal Hashing，即$\text{Pr}[h(\vec{x})=h(\vec{y}) | \vec{x}\neq \vec{y}] \leq \frac{1}{M}$，即令$\vec{z}=\vec{x}-\vec{y}\neq\vec0, \text{Pr}[A\vec{z}=\vec0]\leq\frac{1}{M}$
矩阵$A$每一位$a_{ij}$的选择都是随机独立的，矩阵乘法求和相当于从$\vec{z}$中随机选几项相加，相当于随机序列求和，和为奇数或偶数的概率均为$\frac12$，也就是$h(\vec{x})$每一位为$0$或$1$的概率均为$\frac{1}{2}$
那么$\text{Pr}[h(\vec{x})=\vec0]=\left(\frac{1}{2}\right)^m=\frac{1}{M}\leq\frac{1}{M}$
得证
2. 证明The Dot-product Method是Universal Hashing
同理，需要满足$\text{Pr}[\langle\vec{z}, \vec{r}\rangle \mod M=0]\leq\frac{1}{M}$
由于$\vec{r}$的$k$项随机独立选取，可以认为在模$M$下，$\langle\vec{z}, \vec{r}\rangle$在$\left\{0,1,2,\cdots,M-1\right\}$上均匀分布
那么$\text{Pr}[\langle\vec{z}, \vec{r}\rangle \mod M=0]=\frac{1}{M}\leq\frac{1}{M}$
得证
3. 2-wise Universal Hashing
a.
由于$\vec{b}$固定，所以并不会影响$h(\vec{x})$的分布方式，取到某一特定值的概率仍然是$\left(\frac{1}{2}\right)^m=\frac{1}{M}$，而且独立。所以$\text{Pr}[h(\vec{x_1})=\alpha_1\land h(\vec{x_2})=\alpha_2]=\frac{1}{M^2}$，得证。
b.
依然可以认为$A\vec{x}$第$i$列的值为从$\vec{z}$的$z_0$到$z_{n-i-1}$序列中随机选取求和，仍然满足是$h(\vec{x})$每一位为$0$或$1$的概率均为$\frac{1}{2}$。
那么和a.中一样，取到某一特定值的概率仍然是$\left(\frac{1}{2}\right)^m=\frac{1}{M}$，而且独立，$\text{Pr}[h(\vec{x_1})=\alpha_1\land h(\vec{x_2})=\alpha_2]=\frac{1}{M^2}$，得证。
