随机抽样算法：证明 RANDOM-SAMPLE 返回均匀分布的子集

设 RANDOM(1k) 是一个从 [1, k] 中随机抽取整数并返回它的过程。我们假设随机调用需要 O(1) 最坏时间。以下递归算法 RANDOM-SAMPLE 生成一个大小为 m 的 [1, n] 的子集，其中 m < n，且每个元素都有相同的概率被选中。

算法：

RANDOM-SAMPLE(m, n)
输入: 两个整数 m 和 n，其中 m 表示要抽取的元素数量，n 表示总共的元素数量
输出: 大小为 m 的随机均匀抽样的子集 S

如果 m = 0 则
    返回一个空集合
否则 如果 m > n 则
    返回错误，无法从 n 个元素中抽取超过 n 个元素
否则
    选择一个随机整数 r，范围为 [1, n]
    S = RANDOM-SAMPLE(m-1, n-1)  // 递归调用，抽取剩余元素
    如果 r 在 S 中 则
        S = S ∪ {n}  // 将 n 添加到 S 中
    否则
        S = S ∪ {r}  // 将 r 添加到 S 中
    返回 S
结束如果
结束如果

证明：

我们需要证明 RANDOM-SAMPLE 返回一个大小为 m 的随机均匀抽样的 [1, n] 的子集，即每个元素被选中的概率相等。

归纳基础： 当 m = 0 时，算法返回空集，这是正确的，因为我们需要抽取 0 个元素。
归纳假设： 假设 RANDOM-SAMPLE(m-1, n-1) 返回一个大小为 m-1 的随机均匀抽样的 [1, n-1] 的子集。
归纳步骤： 我们需要证明 RANDOM-SAMPLE(m, n) 返回一个大小为 m 的随机均匀抽样的 [1, n] 的子集。
- 算法首先选择一个随机整数 r，范围为 [1, n]。每个整数被选中的概率都是 1/n。
- 然后算法递归调用 RANDOM-SAMPLE(m-1, n-1)，根据归纳假设，它返回一个大小为 m-1 的随机均匀抽样的 [1, n-1] 的子集。
- 现在，有两种情况：
  - 如果 r 在递归调用返回的子集 S 中，这意味着 r 已经被选中了，算法将 n 添加到 S 中。
  - 如果 r 不在 S 中，算法将 r 添加到 S 中。
- 在这两种情况下，每个元素被添加到 S 中的概率都是 1/n，因为每个整数被选中的概率都是 1/n，并且在递归调用中每个元素被选中的概率都是相等的。
- 因此，RANDOM-SAMPLE(m, n) 返回一个大小为 m 的 [1, n] 的子集，其中每个元素被选中的概率都是 1/n，即随机均匀分布的。

结论： 通过归纳法，我们证明了 RANDOM-SAMPLE 算法返回一个大小为 m 的随机均匀抽样的 [1, n] 的子集，其中每个元素被选中的概率是相等的。