“每个位为1的概率算对了，把它乘k次就得到精确误报率”是一个可以检验的判断。第33篇已经给出小反例，本篇把它整理成一个完整复现项目：明确概率空间，用两个独立方法计算有限实例，保存原始结果，再说明哪个判断被否定、哪个一般结论需要证明。

研究对象是理想Bloom模型的公式，不是本系列仿射散列教学实现的实际误报率。38篇区分精确结果与测量精度，这里更进一步：全程使用有理数，不让浮点舍入成为公式差异的解释。

先写出概率空间

位数组有m个位置，m≥1，初始全为0。插入n个不同键，n≥0，每个键使用k个哈希位置，k≥1。所有kn个位置独立、均匀地取自0到m−1，允许一个键的多个位置相同。

随后查询一个固定的未插入键，它的k个位置也独立均匀，并独立于插入阶段。若查询的所有位置都已置1，就发生误报。n计不同键；重复插入同一个键会重用哈希值，不能按新的一组独立投球计算。

这个模型不自动覆盖双重散列、同一键无放回选择k个位置，或看过位数组再挑查询的对手。代码不会调用33篇的仿射Bloom来伪装这个完全独立模型；二者的随机假设不同。

精确式在条件概率之后取平均

令X为插入结束后的置位数。给定完整位数组、且置位数为x，固定查询的每次独立哈希命中已置位位置的概率为x/m，因此条件误报率为(x/m)^k。对所有可能位数组取平均，得到：

pexact=E[(X/m)k].p_{\mathrm{exact}}=\mathbb E[(X/m)^k].

单个位置未被kn次投球命中的概率为(1−1/m)^{kn}。通过指示变量的线性期望，可得EX=m(1−(1−1/m)^{kn})。把这个平均占位比例直接取k次幂，会得到经典表达式：

pclassic=(1−(1−1/m)kn)k=(EX/m)k.p_{\mathrm{classic}}=\left(1-(1-1/m)^{kn}\right)^k=(\mathbb EX/m)^k.

问题出在交换了“取期望”和“取幂”。给定位数组时，各次查询位置独立；去掉条件后，它们共享同一个随机占位环境，不能把条件独立误当成无条件命中事件独立。

由于x↦x^k在非负区间上凸，Jensen不等式给出p_classic≤p_exact。k=1时函数线性，两式相等；X退化为常量时也相等。因此一般结论是不超过，不能写成所有参数下都严格低估。

一个可以手算的否定实例

取m=2、n=1、k=2。插入的两次投球有一半概率落在同一位置，此时X=1；另一半落在不同位置，此时X=2。精确误报率为：

12(12)2+12⋅12=58.\frac12\left(\frac12\right)^2+\frac12\cdot1^2=\frac58.

经典式为(1−(1/2)²)²=9/16，差为1/16。这个合法实例足以否定“经典式对所有参数都精确”的判断。它不能单独证明任意参数下的下界方向；下界方向来自前面的凸性证明。

还有两个有用边界：n=0时从未置位，误报率为0；m=1且n>0时唯一位置必为1，误报率为1。这些退化实例既检查实现，也提醒不能把严格不等式当成默认结论。

两条相互独立的计算路径

第一条路径按投球次数动态规划。P_t(j)表示t次投球后恰有j个位置被占用的概率，初始P₀(0)=1。下一次投球或者落在已有j个位置之一，保持j；或者从j−1个占位进入一个新位置。于是：

Pt+1(j)=Pt(j)jm+Pt(j−1)m−j+1m.P_{t+1}(j)=P_t(j)\frac jm+P_t(j-1)\frac{m-j+1}{m}.

越界状态视为0。两个来源互斥且穷尽，用归纳法可知每轮分布非负、总和为1，且符合占位事件定义。运行kn轮后，累加P_kn(j)(j/m)^k得到精确误报率。经典式单独代入参数，不从DP结果反推。

第二条路径直接枚举全部插入位置和查询位置。每个组合概率相同，共m^{kn+k}个；用Python集合记录插入位置，再逐个判断查询位置是否属于该集合。误报组合数除以组合总数给出独立参照，不复用占位递推或经典公式。

直接枚举只适合很小的参数。较大矩阵行只运行DP，必须与“已独立枚举核对”的行分开记录；不能把同一公式算两次称为差分验证。两种程序都使用Fraction，输出分子分母，不用一个浮点容差掩盖差异。

计算成本与输入长度

滚动DP每轮遍历m+1个状态，共kn轮，需要O(knm)次有理数操作、O(m)个概率状态；最后再计算加权和，幂运算也有自身成本。n=0需初始化状态，因此连同边界可写O(m+knm)状态处理成本。

这是按数值参数报告的操作次数，不是按m、n、k的二进制编码长度给出的多项式时间结论。Fraction的分子、分母会增长，乘法、约分和比较都不是无条件常数时间；O(m)状态也不等于O(m)位空间。

直接枚举处理m^{kn+k}个组合，每个组合检查kn次插入位置和k次查询位置，粗略成本O((kn+k)m^{kn+k})，另计整数与集合操作。它的价值是独立性与可审计性，不是大规模求解效率。

原始结果与复跑入口

仓库根目录运行：

1
python3 examples/advanced-algorithms/check_bloom_probability.py

本次退出0、status=passed。参数m取1到4、n取0到2、k取1到3，只保留组合数不超过100000的实例，共35个实例、30600种位置配置；所有DP结果与独立枚举精确相等，另有3次非法参数拒绝检查。m=2、n=1、k=2的结果确认为5/8与9/16。

额外的(8,3,3)、(16,5,4)、(32,10,3)三组参数只计算DP，原始记录明确标为未独立枚举。它们扩展数值观察范围，不增加独立参照覆盖范围。每行保存精确式、经典式、差值和实际枚举组合数，没有把大参数行的枚举数填成理论组合数。

原始stdout位于writing-plans/advanced-algorithms/evidence/bloom-probability-results.json，实现为examples/advanced-algorithms/bloom_probability.py，独立参照为同目录check_bloom_probability.py；源码散列保存在证据目录的bloom-probability-source-hashes.json。

观察否定了“经典式总是精确”的命题，并与已证明的非严格下界方向一致。一般方向仍由条件概率与Jensen证明支持；35个有限实例不能证明无限参数范围，也不能估计某个实际哈希族的误报率。

这个项目的输出是理想概率，不是某次随机模拟的误报比例，更不是实际网络过滤器的测量。没有随机种子需要调到“更符合理论”；枚举的每一种配置都计入分母。实际哈希族、输入相关性、位数组更新与删除行为需要另一个实验设计。

练习

  1. 对m=3、n=1、k=2手算X=1与X=2的概率，分别求精确式和经典式。指出在哪一步不能把期望移入平方。
  2. 将查询改为无放回选择k个不同位置，假设k≤m。给定X=x时的误报概率应如何改变？为什么本篇原枚举程序不再直接验证这个新模型？

参考资料