蓄水池抽样 | Codeboy's Blog

形式陈述

接口与更新规则

输入是长度事先未知的 append-only 数据流，目标是在任意时刻 $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$ 。

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

直觉

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

删除流与滑动窗口会让旧位置失效，经典 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.

形式陈述 ​

接口与更新规则 ​

联合均匀性证明 ​

容量三的状态轨迹 ​

随机数与合并 ​