解法：
- 建立 Hash 函数 $h(x)$ 把值 $x$ 映射到 $[0, 2^\omega]$ 区间的整数上，每个值以 $\omega$ 位存储
- 建立函数 $r(x)$, 统计 $\omega$ 位存储的数值 $x$，尾部 0 的个数
- 对整数 $k$ ，有 $z_k = r(h(k))$， 求 $Z = \underset{k \in S}{\max} z_k$
- 得到估计值 $\tilde{F} = 2^Z$
错误率分析
记 $N$ 为流 $S$ 上元素的个数，整数 $\omega$ 为存储的位数 ( $\omega \geq log(N))$)，$z_k$ 为后缀 0 的个数，$F$ 为实际的基数，$\tilde{F}$ 为基数估计值
Proposition. $c$ 为任意整数，且满足 $c>3$, 此时 $\frac{1}{c} \leq \frac{\tilde{F}}{F} \leq c$ 的概率至少为 $1- \frac{3}{c}$.
引理1. 引入整数 $r$ ($r \in [0, \omega]$) , 有 $P[z_k \geq r] = \frac{1}{2^r}$
证明1:
由于哈希函数 $h(k)$ 会把整数 $k$ 映射到 $\omega$ 位上，因此当数 $k$ 后缀 0 为 $z_k$ 个时，满足 $z_k \geq r$ 的条件且末尾至少具有 $r$ 个 0 的数有 $2^{\omega - r}$ 个。因此
$$
P[z_k \leq r] = \frac{2^{\omega - r}}{2^{\omega}} = \frac{1}{2^r}
$$
我们有以下辅助函数 $x_k(r)$:
$$
x_k(r) = \begin{cases}
1 & \text{ if } z_k \geq r \
0 & \text{ otherwise }
\end{cases}
$$
根据二项分布，结合证明 1 的结果，可得：
$$
E[x_k(r)] = \frac{1}{2^r}
$$
$$
var[x_k(r)] = \frac{1}{2^r} (1-\frac{1}{2^r})
$$
另外定义函数 $X(r)$：
$$
X(r) = \sum_{k \in \text{distinct set of }S}{x_k(r)}
$$
易求得：
$$
E[X(r)] = \sum_{k \in \text{distinct set of }S} E[x_k(r)] = \frac{F}{2^r}
$$
$$
var[x_k(r)] = \sum_{k \in \text{distinct set of }S} var[x_k(r)] = \frac{F}{2^r} (1-\frac{1}{2^r})
$$
给定 $r_1$ 与 $r_2$ 分别满足：
- $r_1$ 是令 $r_1 \geq \frac{F}{c}$ 成立的最小整数
- $r_2$ 是令 $r_2 > cF$ 成立的最小整数
引理2： 当且仅当 $X(r_1) = 0$ 且 $X(r_2) \neq 0$ 时，算法正确
证明2：
S 的基数集中，最大的末尾 0 长度为：
$$
Z = \underset{k \in S}{\max} z_k
$$
当 $Z$ 的值满足 $r_1 \leq Z < r_2$ 时，算法结果正确
- 若 $X(r_1) \neq 0$，则存在 $k$ 使得 $Z <r_1$ ，算法结果超出范围
- 若 $X(r_2) = 0$，则存在 $k$ 使得 $Z \geq r_2$，算法结果超出范围
因此，当且仅当 $X(r_1) = 0$ 且 $X(r_2) \neq 0$ 时，算法结果位于正确范围内
引理3：$P[X(r_1) = 0] < \frac{2}{c}$
证明3：
根据已知的结论，易得:
$$
E[X(r_1)] = \frac{F}{2^{r_1}}
$$
$$
var[x_k(r_1)] = \frac{F}{2^{r_{1}}} (1-\frac{1}{2^{r_{1}}}) \Rightarrow var[x_k(r_1)] < \frac{F}{2^{r_{1}}}
$$
根据二项分布，可知：
$$
P[X(r_1) = 0] = P[X(r_1) - E[X(r_1)] = E[X(r_1)]]
$$
进一步得出：
$$
P[X(r_1) = 0] \leq P[|X(r_1) - E[X(r_1)]| = E[X(r_1)]]
$$
根据上式，我们可以构造以下式子：
$$
P[X(r_1) = 0] \leq P[|X(r_1) - E[X(r_1)]| \geq E[X(r_1)]]
$$
使用切比雪夫不等式 (Chebyshev inequality)，可得：
$$
P[|X(r_1) - E[X(r_1)]| \geq E[X(r_2)]] \leq \frac{var[X(r_2)]}{E[X(r_2)]^2} \Rightarrow P[X(r_1) = 0] < \frac{\frac{F}{2^{r_{1}}}}{(\frac{F}{2^{r_{1}}})^2} = \frac{2^{r_{1}}}{F}
$$
由于 $2^{r_1} < 2^{r_1+1} \leq \frac{2F}{c}$， 所以 $P[X(r_1) = 0] < \frac{2}{c}$
引理4：$P[X(r_2) \geq 1] < \frac{1}{c}$
证明4：
与证明 3 类似，易得：
$$
E[X(r_2)] = \frac{F}{2^{r_2}}
$$
且由于 $r_2 \leq \frac{F}{c}$， 可推得
$$
E[X(r_2)] = \frac{F}{2^{r_2}} \leq \frac{1}{c}
$$
使用马尔科夫不等式 (Markov inequality) 可得：
$$
P[X(r_2) \geq 1] \leq E[X(r_2)] \leq \frac{1}{c}
$$
根据引理 3 和引理 4 ，可知，算法失败概率为:
$P(X(r_1) = 0 \cap X(r_2) \geq 1) = \frac{3}{c}$
所以落在区间内的可能性至少为 $1 - \frac{3}{c}$ 推论成立