布隆过滤器的错误率推导

设 Hash 函数个数: $k$ ， 布隆过滤器大小: $n$ ( $n \gg k$ )，$S$ 流上的元素个数为: $|S|$

可得 Hash 函数 $h_i$ 应用于元素 $x$ 后，布隆过滤器上某位 $B[j]$ 是 1 的概率：

$$
P(h_i [x] = 1) = \frac{1}{n}
$$

易得， $B[j]$ 是 0 的概率：

$$
P(h_i [x] = 0) = 1 - \frac{1}{n}
$$

当所有 Hash 函数应用于元素 $x$ ， $B$ 依旧是 0 的概率：

$$
Pr(h_i[x] = 0, i \in [1,k]) = (1 - \frac{1}{n})^k
$$

当向布隆过滤器添加了 $S$ 流上的 $|S|$ 个元素后， $B[j]$ 为 0 的概率为：

$$
Pr(B[j] = 0) = (1 - \frac{1}{n})^{k|s|}
$$

可推得，$B[j]$ 为 1 的概率为：

$$
Pr(B[j] = 1) = 1 - (1 - \frac{1}{n})^{k|s|}
$$

结合：

$$
\lim_{n \to \infty} (1 - \frac{1}{n})^n = \frac{1}{e}
$$

可得到：

$$
\lim_{n \to \infty} (1 - \frac{1}{n})^{k|s|} = (1 - \frac{1}{n})^{\frac{nk|s|}{n}} = \frac{1}{e}^{\frac{k|s|}{n}}
$$

故 $Pr(B[j] = 1)$ 有近似值:

$$
Pr(B[j] = 1) \approx 1 - e^{-\frac{k|s|}{n}}
$$

因此误报的可能性为:

$$
P_{false} = (Pr(B[j] = 1))^k \approx (1 -e^{-\frac{k|s|}{n}})^k
$$

寻找函数个数的最优值

根据：

$$
P_{false} = (Pr(B[j] = 1))^k \approx (1 -e^{-\frac{k|S|}{n}})^k
$$

令 $x = e^{-\frac{|S|}{n}}$，可知：

$$
P_{false} = (1-x^k) ^k
$$

令 $f(x) = P_{false}$，有：

$$
f(x) = (1-x^k) ^k
$$

若存在 $g(x) = ln(f(x))$， 则 $g(x)$ 的导数为：

$$
g’(x) = [ln((1-x^k)^k)]’
$$

求解得：

$$
g’(x) = ln(1-x^k) + (1-x^k)’ \cdot \frac{1}{1-x^k} \cdot k = ln(1-x^k) - \frac{x^k \cdot ln(x^k)}{1-x^k}
$$

同时，由于：

$$
g’(x) = \frac{f’(x)}{f(x)}
$$

由 $x = e^{-\frac{|S|}{n}}$ 可证 $f(x) > 0$, 因此，当 $f’(x) = 0$ 时，存在：

$$
ln(1-x^k) - \frac{x^k \cdot ln(x^k)}{1-x^k} = 0
$$

化简得

$$
(1-x^k)ln(1-x^k) = x^kln(x^k)
$$

当且仅当 $1-x^k = x^k$ 时，上式成立，因此可知：

$$
x^k = \frac{1}{2}
$$

由于 $x = e^{-\frac{|S|}{n}}$, 因此：

$$
e^{-\frac{k|S|}{n}} = \frac{1}{2}
$$

可得：

$$
k_{opt} = \frac{nln(2)}{|S|}
$$

此时误报概率 $P_{false}$ 为：

$$
P_{false} \approx (1-\frac{1}{2})^{\frac{n}{|S|}ln(2)} = 0.6185 ^ {\frac{n}{|S|}}
$$