蓄水池抽样算法（Reservoir Sampling）的原理、证明与应用
字数 2190 2025-12-15 00:09:55

蓄水池抽样算法（Reservoir Sampling）的原理、证明与应用

1. 问题描述

蓄水池抽样算法用于解决这样一个问题：

  • 给定一个数据流（数据长度未知或非常大，无法一次性存入内存），
  • 要求等概率随机选取 k 个样本（k ≥ 1），其中每个样本被选中的概率相同。

例如：从持续不断到达的搜索查询日志中，实时等概率抽取 100 条查询记录用于分析。

2. 核心思想

算法核心是动态调整已选中样本的概率，使得在任意时刻，已处理过的数据中每个样本被保留在蓄水池（即选中集合）的概率均等。

3. 算法步骤（k=1 的情况）

我们先从 k=1 开始理解，再推广到 k>1。

场景：从数据流中等概率随机抽取 1 个样本。
算法流程：

  1. 初始化结果变量 reservoir，用于存放最终选中的样本。
  2. 当处理到第 i 个元素时（i 从 1 开始计数）：
    • 如果 i == 1，直接选中该元素，reservoir = 当前元素。
    • 如果 i > 1，以 1/i 的概率用当前元素替换 reservoir 中的值，否则保留原值。

举例：
数据流为 [a, b, c]：

  • i=1，reservoir = a（概率 1）。
  • i=2，以 1/2 概率用 b 替换 a。
    • 最终为 a 的概率 = 第一次选中 a 且第二次没被替换 = 1 * (1 - 1/2) = 1/2。
    • 最终为 b 的概率 = 第二次被选中 = 1/2。
  • i=3，以 1/3 概率用 c 替换当前 reservoir。
    • 最终为 a 的概率 = 前两次是 a 且第三次没被替换 = 1/2 * (1 - 1/3) = 1/3。
    • 最终为 b 的概率同理 = 1/2 * (1 - 1/3) = 1/3。
    • 最终为 c 的概率 = 1/3。

可看出每个元素被选中的概率均为 1/3。

4. 数学归纳法证明（k=1）

假设前 n 个元素中，每个元素被选中的概率均为 1/n。
当第 n+1 个元素到达时：

  • 以 1/(n+1) 概率替换当前选中元素。
  • 对于前 n 个元素中的任意一个，它最终被选中的概率 = 它在前 n 步时被选中的概率 * 在第 n+1 步不被替换的概率 = (1/n) * (1 - 1/(n+1)) = 1/(n+1)。
  • 第 n+1 个元素被选中的概率 = 1/(n+1)。
    由归纳法可知，任意时刻每个元素被选中的概率相等。

5. 推广到 k ≥ 1 的情况

算法步骤：

  1. 初始化大小为 k 的数组 reservoir[0..k-1]，将前 k 个元素存入。
  2. 对于第 i 个元素（i 从 k+1 开始计数，注意：i 是当前总元素序号，从 1 开始）：
    • 随机生成一个整数 r ∈ [0, i-1]。
    • 如果 r < k，则用当前元素替换 reservoir[r]，否则丢弃当前元素。

等价理解：

  • 对当前第 i 个元素，以 k/i 的概率将其放入蓄水池。
  • 若决定放入，则从蓄水池的 k 个位置中等概率随机选一个替换。

6. 概率证明（k>1）

我们要证明：处理完 n 个元素后，任意一个元素被保留在蓄水池中的概率 = k/n。

分情况讨论：

  • 对于前 k 个元素（i ≤ k）：

    • 一开始它们肯定在蓄水池中。
    • 当第 i 个元素到来（i > k）时，这个元素有 k/i 的概率进入蓄水池，并随机替换一个位置。
    • 因此，对于前 k 个元素中的某个元素，它在第 i 步被替换的概率 = (k/i) * (1/k) = 1/i。
    • 它在第 i 步保留下来的概率 = 1 - 1/i。
    • 从第 k+1 步到第 n 步，它一直保留的概率 = ∏_{i=k+1}^n (1 - 1/i) = k/n。

  • 对于第 m 个元素（m > k）：

    • 当它到达时，被选入蓄水池的概率 = k/m。
    • 之后第 i 步（i > m）不被替换的概率 = 1 - 1/i。
    • 从第 m+1 步到第 n 步，它一直保留的概率 = ∏_{i=m+1}^n (1 - 1/i) = m/n。
    • 因此最终被保留的概率 = (k/m) * (m/n) = k/n。

结论：所有元素被选中的概率均为 k/n，满足等概率要求。

7. 算法示例（k=3）

数据流：A, B, C, D, E, F, ...

步骤：

  1. 初始化 reservoir = [A, B, C]（i=1,2,3 直接放入）。
  2. i=4（元素 D）：
    • 随机生成 r ∈ [0,3]。
    • 若 r < 3（例如 r=1），则 reservoir[1] = D。
  3. 重复直到结束。

最终 reservoir 中每个位置是等概率的，且每个元素被选中的概率 = 3/n。

8. 时间复杂度与空间复杂度

  • 时间复杂度：O(n)，每个元素处理一次，只需生成随机数并进行可能的替换。
  • 空间复杂度：O(k)，只需存储 k 个样本。

9. 应用场景

  1. 大规模日志抽样。
  2. 在线随机播放（从未知长度的播放列表随机选取）。
  3. 数据库查询结果的随机抽样（当结果集太大时）。
  4. 机器学习中从数据流中构建随机样本集。

总结：蓄水池抽样算法通过动态调整概率，在只遍历一次数据流且无需知道总长度的情况下，实现了严格的等概率随机抽样，是大数据处理中经典的随机化算法。

蓄水池抽样算法（Reservoir Sampling）的原理、证明与应用 1. 问题描述 蓄水池抽样算法用于解决这样一个问题： 给定一个 数据流 （数据长度未知或非常大，无法一次性存入内存）， 要求 等概率 随机选取 k 个样本 （k ≥ 1），其中每个样本被选中的概率相同。 例如：从持续不断到达的搜索查询日志中，实时等概率抽取 100 条查询记录用于分析。 2. 核心思想 算法核心是 动态调整 已选中样本的概率，使得在任意时刻，已处理过的数据中每个样本被保留在蓄水池（即选中集合）的概率均等。 3. 算法步骤（k=1 的情况） 我们先从 k=1 开始理解，再推广到 k>1。 场景 ：从数据流中等概率随机抽取 1 个样本。 算法流程 ： 初始化结果变量 reservoir ，用于存放最终选中的样本。 当处理到第 i 个元素时（i 从 1 开始计数）： 如果 i == 1，直接选中该元素， reservoir = 当前元素 。 如果 i > 1，以 1/i 的概率用当前元素替换 reservoir 中的值，否则保留原值。 举例 ： 数据流为 [ a, b, c ]： i=1， reservoir = a （概率 1）。 i=2，以 1/2 概率用 b 替换 a。 最终为 a 的概率 = 第一次选中 a 且第二次没被替换 = 1 * (1 - 1/2) = 1/2。 最终为 b 的概率 = 第二次被选中 = 1/2。 i=3，以 1/3 概率用 c 替换当前 reservoir。 最终为 a 的概率 = 前两次是 a 且第三次没被替换 = 1/2 * (1 - 1/3) = 1/3。 最终为 b 的概率同理 = 1/2 * (1 - 1/3) = 1/3。 最终为 c 的概率 = 1/3。 可看出每个元素被选中的概率均为 1/3。 4. 数学归纳法证明（k=1） 假设前 n 个元素中，每个元素被选中的概率均为 1/n 。 当第 n+1 个元素到达时： 以 1/(n+1) 概率替换当前选中元素。 对于前 n 个元素中的任意一个，它最终被选中的概率 = 它在前 n 步时被选中的概率 * 在第 n+1 步不被替换的概率 = (1/n) * (1 - 1/(n+1)) = 1/(n+1)。 第 n+1 个元素被选中的概率 = 1/(n+1)。 由归纳法可知，任意时刻每个元素被选中的概率相等。 5. 推广到 k ≥ 1 的情况 算法步骤 ： 初始化大小为 k 的数组 reservoir[0..k-1] ，将前 k 个元素存入。 对于第 i 个元素（i 从 k+1 开始计数，注意：i 是当前总元素序号，从 1 开始）： 随机生成一个整数 r ∈ [ 0, i-1 ]。 如果 r < k，则用当前元素替换 reservoir[r] ，否则丢弃当前元素。 等价理解 ： 对当前第 i 个元素，以 k/i 的概率将其放入蓄水池。 若决定放入，则从蓄水池的 k 个位置中等概率随机选一个替换。 6. 概率证明（k>1） 我们要证明：处理完 n 个元素后，任意一个元素被保留在蓄水池中的概率 = k/n。 分情况讨论 ： 对于前 k 个元素（i ≤ k）： 一开始它们肯定在蓄水池中。 当第 i 个元素到来（i > k）时，这个元素有 k/i 的概率进入蓄水池，并随机替换一个位置。 因此，对于前 k 个元素中的某个元素，它在第 i 步被替换的概率 = (k/i) * (1/k) = 1/i。 它在第 i 步保留下来的概率 = 1 - 1/i。 从第 k+1 步到第 n 步，它一直保留的概率 = ∏_ {i=k+1}^n (1 - 1/i) = k/n。 对于第 m 个元素（m > k）： 当它到达时，被选入蓄水池的概率 = k/m。 之后第 i 步（i > m）不被替换的概率 = 1 - 1/i。 从第 m+1 步到第 n 步，它一直保留的概率 = ∏_ {i=m+1}^n (1 - 1/i) = m/n。 因此最终被保留的概率 = (k/m) * (m/n) = k/n。 结论 ：所有元素被选中的概率均为 k/n，满足等概率要求。 7. 算法示例（k=3） 数据流：A, B, C, D, E, F, ... 步骤： 初始化 reservoir = [ A, B, C ]（i=1,2,3 直接放入）。 i=4（元素 D）： 随机生成 r ∈ [ 0,3 ]。 若 r < 3（例如 r=1），则 reservoir[ 1 ] = D。 重复直到结束。 最终 reservoir 中每个位置是等概率的，且每个元素被选中的概率 = 3/n。 8. 时间复杂度与空间复杂度 时间复杂度：O(n)，每个元素处理一次，只需生成随机数并进行可能的替换。 空间复杂度：O(k)，只需存储 k 个样本。 9. 应用场景 大规模日志抽样。 在线随机播放（从未知长度的播放列表随机选取）。 数据库查询结果的随机抽样（当结果集太大时）。 机器学习中从数据流中构建随机样本集。 总结 ：蓄水池抽样算法通过动态调整概率，在 只遍历一次数据流 且 无需知道总长度 的情况下，实现了严格的等概率随机抽样，是大数据处理中经典的随机化算法。