1. 问题描述

首先介绍什么是蓄水池采样问题（Reservoir Sampling）。

蓄水池采样是一组随机采样算法，它们解决的是从一个包含 $ n $ 个数据的集合 $ S $ 中等概率选取 $ k $ 个数据的问题，但这里的数据量 $ n $ 是一个非常大的数。一般来说，这种问题里的数据量 $ n $ 大到无法一次性在物理内存中存下全部数据。

2. 算法细节

首先蓄水池采样的精妙之处在于它不需要把整个数据集加载到内存中算一遍数据量，再根据数据量来随机选取数据，这种方法一是像前面说的可能无法一次性把数据全部加载到内存，二是需要对如此大的数据集进行多次遍历，时间上来讲可能很慢。而蓄水池采样会动态的维护一个大小为 $ k $ 的集合，每处理一个数据就更新一次这个集合，而在任意时刻这个集合中的数据就是在已处理的子集中的等概率选取的 $ k $ 个数据。由此可推断，这种算法还可以适用于数据量不确定的数据集中的任选数据问题，例如在一个动态的数据流中随机采样。

算法过程

首先假设数据规模为 $ n $ ，需要采样的数据量为 $ k $ 。

首先构建一个可容纳 $ k $ 个数据的数组，将序列的前 $ k $ 个数据放入数组中。

然后开始处理第 $ k + 1 $个数据，首先以概率 $ \frac{k}{k + 1} $ 决定是否将第 $ k + 1 $ 个数据放入数组中，如果这个数据被选中了，则在数组中等概率选取一个数据替换。

推广到处理第 $ k + i $ 个数据的时候的场景，以概率 $ \frac{k}{k + i} $ 决定是否将第 $ k + i $ 个数据放入数组中。

当遍历完所有数据的时候，数组中的数据就是所需的结果。

证明过程

对于第 $ i $ 个数（$ i \le k $）。可知在 $ k $ 步之前被选中的概率为1。当走到第 $ k + 1 $ 步的时候，$ i $被第 $ k + 1 $ 个数据替换的概率等于 $ k + 1 $ 个元素被选中的概率乘以 $ i $ 被替换的概率，即 $ \frac{k}{k + 1} \times \frac{1}{k} = \frac{1}{k + 1} $。则第 $ i $ 个数不被替换的概率是 $ 1 - \frac{1}{k + 1} = \frac{k}{k + 1} $ 。依此类推，假设处理第 $ k + 2 $ 个数的时候 $ i $ 还在数组里，则不被第 $ k + 2 $ 个数据替换的概率是 $ 1 - \frac{k}{k + 2} \times \frac{1}{k} = \frac{k + 1}{k + 2} $ 。则运行到第 $ n $ 个数的时候，$ i $ 不被替换的概率是 $ 1 - \frac{k}{n} \times \frac{1}{k} = \frac{n - 1}{n} $ 。则可得到 $ i $ 最终仍在数组中的概率为 $ 1 \times \frac{k}{k + 1} \times \frac{k + 1}{k + 2} \times \cdots \times \frac{n - 1}{n} = \frac{k}{n} $。

对于第 $ j $ 个数（$ j > k $ ），在第 $ j $ 步被选中的概率是 $ \frac{k}{j} $ ，不被第 $ j + 1 $ 个数据替换的概率为 $ 1 - \frac{k}{j + 1} \times \frac{1}{k} = \frac{j}{j + 1} $ 。则运行到第 $ n $ 个数的时候，$ j $ 不被替换的概率是 $ 1 - \frac{k}{n} \times \frac{1}{k} = \frac{n - 1}{n} $ 。 则可得到 $ j $ 最终仍在数组中的概率为 $ \frac{k}{j} \times \frac{j}{j + 1} \times \cdots \times \frac{n-1}{n} = \frac{k}{n} $ 。

综上所述，根据蓄水池采样算法，每个数最终被选取的概率都是 $ \frac{k}{n} $ ，即等概率选取。