Flajolet-Martin Sketches 的错误率证明

FM-Sketch 解决的问题：估计 上 个元素中，有多少个唯一的元素 （基数估计）

本文旨在对 FM-Sketch 的错误率进行分析

解法：

1. 建立 Hash 函数 把值 映射到 区间的整数上，每个值以 位存储
2. 建立函数 , 统计 位存储的数值 ，尾部 0 的个数
3. 对整数 ，有 ， 求
4. 得到估计值

错误率分析

记 为流 上元素的个数，整数 为存储的位数 ( )， 为后缀 0 的个数， 为实际的基数， 为基数估计值

Proposition. 为任意整数，且满足 , 此时 的概率至少为 .

引理1. 引入整数 () , 有

证明1:

由于哈希函数 会把整数 映射到 位上，因此当数 后缀 0 为 个时，满足 的条件且末尾至少具有 个 0 的数有 个。因此

我们有以下辅助函数 :

根据二项分布，结合证明 1 的结果，可得：

另外定义函数 ：

易求得：

给定 与 分别满足：

• 是令 成立的最小整数
• 是令 成立的最小整数

引理2： 当且仅当 且 时，算法正确

证明2：

S 的基数集中，最大的末尾 0 长度为：

当 的值满足 时，算法结果正确

• 若 ，则存在 使得 ，算法结果超出范围
• 若 ，则存在 使得 ，算法结果超出范围

因此，当且仅当 且 时，算法结果位于正确范围内

引理3：

证明3：

根据已知的结论，易得:

根据二项分布，可知：

进一步得出：

根据上式，我们可以构造以下式子：

使用切比雪夫不等式 (Chebyshev inequality)，可得：

由于 ， 所以

引理4：

证明4：

与证明 3 类似，易得：

且由于 ， 可推得

使用马尔科夫不等式 (Markov inequality) 可得：

根据引理 3 和引理 4 ，可知，算法失败概率为:

所以落在区间内的可能性至少为 推论成立