CS170 Efficient Algorithms and Intractable Problems Section12

课程主页：

https://cs170.org/

https://inst.eecs.berkeley.edu/~cs170/fa18/

课程视频：

https://www.bilibili.com/video/BV1wK411g7ck

这次回顾Section 12。

1. 2-Universal Hashing

(a)

$$\begin{aligned} \mathrm{Pr}_{h\in \mathcal H}[h(x)=h(y)] &=\sum_{i=0}^{m-1} \mathrm{Pr}_{h\in \mathcal H}[(h(x),h(y))=(i, i)]\\ &=\sum_{i=0}^{m-1} \frac{1}{m^2}\\ &=\frac 1 m \end{aligned}$$

(b)

(i)

参考了习题解答。

考虑下表：

	$x$	$y$	$z$
$h_1$	$0$	$0$	$1$
$h_2$	$1$	$0$	$1$

假设$x,y,z$选择$h_1,h_2$的概率为$\frac 1 2$，那么显然该函数族为Universal Hashing。

另一方面，假设选择了$x$，那么

$$h(x)=0\Rightarrow h =h_1$$

此时取$y=y$即可。

否则

$$h(x)=1\Rightarrow h =h_2$$

此时取$y=z$即可。

所以概率可能大于$\frac 1 m$。

备注：

这里的区别在于$h$是固定的，而Universal Hashing中$h$是变动的。

(ii)

$$\begin{aligned} \mathrm{Pr}_{h\in \mathcal H}[h(y)=h(x)] &= \sum_{ i=0}^{m-1}\mathrm{Pr}_{h\in \mathcal H}[(h(x),h(y))=(i,i)]\\ &=m\times \frac 1 {m^2}\\ &=\frac 1 m \end{aligned}$$

即概率不可能大于$\frac 1 m$。

2. Markov Bound Review

$$\begin{aligned} E[X] &= E[X| X\ge a] + E[X| X< a]\\ &\ge E[X| X\ge a]\\ &\ge aPr(X\ge a)\\ Pr(X\ge a) &\le \frac{E[X]}{a} \end{aligned}$$

3. Document Comparison with Streams

使用流算法统计不同元素数量即可，空间复杂度为$O(\log(|A|+|B|))$，具体做法如下（利用三个计数器即可）：

• 统计$A$的不同元素数量$a_1$；
• 统计$B$的不同元素数量$a_2$；
• 统计$A\cup B$的不同元素数量$a_3$。

那么结果为

$$p=\frac{a_1 + a_2 -a_3}{a_3}$$

假设真实值分别为$b_1,b_2,b_3$，那么真实的比例为

$$p'=\frac{b_1 +b_2 -b_3}{b_3}$$

注意到$a_i\in [(1-\epsilon)b_i, (1+\epsilon)b_i]$，$\epsilon $为任意小的正数，所以

$$\begin{aligned} p&\le \frac{(1+\epsilon) (b_1 + b_2)-(1-\epsilon) b_3}{ (1-\epsilon) b_3}\\ &= \frac{(1+\epsilon) (b_1 + b_2-b_3)+2\epsilon b_3}{ (1-\epsilon) b_3}\\ &=\frac{1+\epsilon}{1-\epsilon} p' +\frac{2\epsilon}{1-\epsilon}\\ p&\ge \frac{(1-\epsilon) (b_1 + b_2)-(1+\epsilon) b_3}{ (1+\epsilon) b_3}\\ &=\frac{(1-\epsilon) (b_1 + b_2-b_3)-2\epsilon b_3}{ (1+\epsilon) b_3}\\ &=\frac{1-\epsilon}{1+\epsilon} p' -\frac{2\epsilon}{1+\epsilon} \end{aligned}$$

由于$\epsilon$可以任意小，从而$p$可以和$p’$任意逼近。

4. Lower Bounds for Streaming

感觉这一题有点问题，略过。