L0 and l1 sampling

Problem Describe

• We are given stream $a_1, a_2, … a_m \in {1, … , n}$
• After we read $a_i$, we want to maintain a random number from $a_1, … , a_i$.
• Example: Example: 1 5 1 1 1
  • $L_0$ sampling outputs 1 and 5 with equal probability
  • $L_1$ sampling outputs 1 with probability 4/5 and 5 with probability 1/5
• Do this by maintaining one number $a_j$ from the stream plus a counter $c \leq m$

L1 Algorithm

Initially, $x = a_1$. When read $a_i$, let $x = a_i$ with probability $\frac{1}{i}$.

L0 Algorithm

k=2

1. Initially, construct random hash $h:{1…n} \rightarrow {1…2}$.
2. When read $a_i$: Store $a_i$ if $h(a_i)=1$.
3. If store >1 number (among 1…n): Output TOO MUCH (fails)
4. If no number stored: Output TOO LITTLE (fails)
5. Otherwise, output the stored number.

这个 哈希函数（Hash Function） 是随机将 $N$ 个数分配成 1 或 2，因为 $k=2$，所以只会有四种情况。

假设两个数分别为 1，5，那么 4 种情况为：

1. $1 \rightarrow 1, 5\rightarrow 1$
2. $1 \rightarrow 1, 5\rightarrow 2$
3. $1 \rightarrow 2, 5\rightarrow 1$
4. $1 \rightarrow 2, 5\rightarrow 2$

其中，第 1 和第 4 种情况将会导致 FAIL，$Pr[FAIL]=\frac{1}{2}$。

在成功的 哈希函数 中，两个数被选中的概率是均等的。

Reduce Failure 降低失败率/提高成功率

通过构建不同的 hash function。例如：

1. Initially, construct random hash $h_1,h_2,…,h_{10}:{1…n} \rightarrow {1…2}$.
2. When read $a_i$: $\forall j$ store $a_i$ in set $x_j$ if $h_j(a_i)=1$.
3. Say that $h_j$ fails if $x_j$ stores >1 number or no number
4. Pick one $h_j$ not fail. Output $x_j$

• $Pr[all h_j fails]= \frac{1}{2^{10}}$

• $\forall a_i: Pr[a_i \in x_j

  h_j not fail]=\frac{1}{2}$

通过构建 10 个不同的随机 哈希函数，来提高算法的成功率。

#待整理笔记