水塘抽样 (Reservoir sampling) 的合理性证明

水塘抽样的作用：

假定存在流 ；若需要对流 进行采样，其中采样数 需满足 。

本文旨在对水塘抽样的合理性作出证明。

抽样方法

• 先把 中前 个元素加入到抽样结果 中
• 若元素 到达，且满足 ，此时 存在 的概览替换 中任一随机选定的元素
• 当 时，返回抽样结果

合理性证明

情况1： 时，当遍历了 个元素时，应满足每个元素位于 中的概率为

当 时，样品 存在于 的概率为 ；

当 时，样品 可以随机替换掉 的概览为 ，则 存在于 的概率为 ；

当 时，样品 可以随机替换 或 的概率为 , 则 与 依然存在于 的概率为 ；

…

以此类推，当 时，样品 可以随机替换 的概率为： ，则 依然存在于 的概率为：

显然，当 时，则每个元素位于 中的概率为 ，要求成立

情况2: 时，当遍历了 个元素时，应满足每个元素位于 中的概率为

当 且 时，样品 会无条件进入 ，此时 存在于 的概率为 ；

当 时，样品 可以可以随机替换掉 的概率为：，此时 依然存在于 的概率为 :

当 时，样品 可以随机替换掉 的概率为：，此时 依然存在于 的概率为:

以此类推，对于任意 , 样品 可以随机替换掉 的概率为： , 此时 依然存在于 的概率为：

若 ，则每个元素位于 中的概率为 ，要求成立