蓄水池抽样 | Codeboy's Blog

形式陈述

接口与更新规则

输入是长度事先未知的 append-only 数据流，给定整数容量 $k\ge0$ ，目标是在任意时刻 $t$ 返回已见位置中大小为 $\min(k,t)$ 的均匀无放回样本。容量为零时始终返回空集；下文设 $k\ge1$ 。这是一个随机化算法：前 $k$ 项直接入槽；第 $t>k$ 项以 $k/t$ 概率进入。

等价实现是均匀生成 $j\in\{1,\ldots,t\}$ ：若 $j\le k$ ，就用新项替换槽 $j$ ，否则状态不变。状态包含至多 $k$ 条记录、已见计数 $t$ 和所需随机状态。在记录、计数器均占常数个字，且均匀有界整数作为单位成本原语的模型下，空间为 $O(k+1)$ 个字，单项更新时间为最坏 $O(1)$ 。若从独立随机位实现拒绝采样，采样轮数只有期望常数界，不能据此声称最坏常数时间；计数器和一次随机整数还各需 $\Theta(\log(t+1))$ 位。

联合均匀性证明

当 $t\le k$ 时保留全部位置。对 $t>k$ ，归纳假设处理 $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$ 。

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

直觉

第 $t$ 个元素以 $k/t$ 的概率进入样本，恰好补偿它此前没有入选机会；一旦进入，后续每轮又以对称概率被替换。归纳后每个历史元素在最终 $k$ 个槽中的边缘与联合分布都保持均匀，而不需要预先知道流长。

容量三的蓄水池在第四项到达时以四分之三概率进入，并按随机槽替换 — 随机槽替换与进入概率

例子与边界

容量三的状态轨迹

前 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$ 机械换成权重比。

若目标是不同键集合的相似度，MinHash为同一键固定共享排列名次，重复到达不改变最小者；Bottom-k不同键摘要保留前k个不同键，以候选内去重和单调阈值处理重放。它们估计集合交并比例，不能把reservoir对出现位置的均匀性原封不动移到不同键上。

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

若抽样机会需要随已知规模变化，可读规模比例抽样。它重点区分每抽概率和至少一次纳入概率，这一区别在有放回重复抽取与去重后的加权分析之间尤其重要。

抽样用于隐私时，还必须匹配邻接与观察范围。子抽样隐私放大的标准 Poisson 公式假设每条记录独立入样，并隐藏参与身份；reservoir 产生固定大小、无放回的均匀样本，属于另一种采样律。两者都可以具有隐私放大分析，但不能因为样本比例相同就共用未经核对的参数公式。

参考资料

Jeffrey Vitter, “Random Sampling with a Reservoir,” TOMS, 1985.
Donald Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed., Addison-Wesley, 1997.

形式陈述 ​

接口与更新规则 ​

联合均匀性证明 ​

容量三的状态轨迹 ​

随机数与合并 ​