蓄水池抽样

接口与更新规则 ​

输入是长度事先未知的 append-only 数据流公理库数据流算法模型Data-stream model · Streaming algorithm输入顺序到达且不能保存全文，以扫描趟数、工作空间、处理时间和输出保证评价算法。，目标是在任意时刻 (t) 用 (k) 个槽返回已见位置的均匀无放回样本。前 (k) 项直接入槽；第 (t>k) 项以 (k/t) 概率进入。

等价实现是均匀生成 (j\in{1,\ldots,t})：若 (j\le k)，就用新项替换槽 (j)，否则状态不变。状态包含 (k) 条记录、已见计数 (t) 和随机数生成器，空间为 (O(k))，单项更新时间为最坏 (O(1))。

联合均匀性证明 ​

归纳假设处理 (t-1) 项后，每个 (k) 元位置子集概率都是 (1/\binom{t-1}{k})。对不含新位置 (t) 的目标子集，它只有在新项不进入时保留，概率为 [ \frac{1}{\binom{t-1}{k}}\left(1-\frac{k}{t}\right) =\frac{1}{\binom tk}. ]

对包含 (t) 的目标子集，先前 reservoir 必须包含其余 (k-1) 个位置和某个将被替换的位置。把 (t-k) 种可能的旧位置相加，再乘进入概率 (k/t) 与均匀替换概率 (1/k)，同样得到 (1/\binom tk)。因此保证是完整的无放回分布，不只是每项边缘概率 (k/t)。

只证明边缘相等不足以排除相关偏置：一个错误算法可能让每个位置边缘概率正确，却总是成对选择相邻位置。需要联合子集归纳才能支持“均匀无放回”的接口承诺。

容量三的状态轨迹 ​

前 3 项 A、B、C 全收。第 4 项 D 以 (3/4) 进入；若随机到槽 2，状态变成 A、D、C，否则可能替换别的槽或保持不变。第 5 项 E 以 (3/5) 进入，并再次只替换一个均匀槽。

以 A 为例，它经过第 4 步的留存概率是 [ 1-\frac34\cdot\frac13=\frac34, ] 再乘第 5 步不被替换的 (1-1/5=4/5)，得到 (3/5)。轨迹展示槽如何变化；联合分布则由上一节对子集的归纳负责，不需再以这五项重新证明一次。

随机数与合并 ​

固定宽随机整数直接对 (t) 取模，在随机范围不能被 (t) 整除时会产生偏差；应使用拒绝采样或提供均匀有界整数的库接口。计数 (t) 溢出也会让进入概率失真，因此长寿命服务需要足够宽的计数器。

两段长度 (m,n) 的 reservoir 合并时，最终样本来自第一段的数量服从超几何分布。若两段各保留一个样本而长度分别为 1000 与 10，再等概率二选一，会让短段获得 (1/2) 权重，而正确概率是 (10/1010)。一般 (k) 不能固定各取一半；需要段长加权的合并算法，或从一开始为元素生成全局可比较的随机优先级并保留最优 (k) 项。

对象边界 ​

重复记录按出现位置抽样，出现十次的 key 有十个被选机会；若希望对 distinct key 均匀，必须使用去重摘要或另一种采样定义。加权 reservoir 通过经证明的随机优先级按权抽样，也不是把 (k/t) 机械换成权重比。

删除流与滑动窗口会让旧位置失效，经典 reservoir 没有足够信息补回被淘汰候选。并行合并、带权与带删除版本都应分别声明算法和分布保证，不能沿用本页证明。

参考资料

• Jeffrey Vitter, “Random Sampling with a Reservoir,” TOMS, 1985.
• Donald Knuth, TAOCP, Vol. 2, 3rd ed.