证明 RANDOM-SAMPLE 算法返回大小为 m 的均匀随机子集

为了证明 RANDOM-SAMPLE 返回一个大小为 m 的均匀随机抽样的子集，我们需要证明两件事： \u000a\u000a1. 大小为 m 的每个可能子集被返回的概率相等。 \u000a2. 算法终止并返回一个有效的子集。 \u000a\u000a证明： \u000a1. 为了证明大小为 m 的每个可能子集被返回的概率相等，我们将使用数学归纳法。 \u000a\u000a基本情况：当 m = 0 时，算法立即返回一个空集，这是一个大小为 0 的有效子集。由于大小为 0 的空集只有一个可能的选择，它以概率 1 被返回。 \u000a\u000a归纳步骤：假设当 m = k 时，大小为 k 的每个可能子集被返回的概率相等。 \u000a\u000a现在考虑当 m = k + 1 的情况。算法首先以 m-1 和 n-1 调用 RANDOM-SAMPLE，它从集合 {1, 2, ..., n-1} 中均匀随机地返回一个大小为 k 的子集 S。接下来的步骤是从 {1, 2, ..., n} 中选择一个随机整数 i。 \u000a\u000a如果 i 不在 S 中，算法返回 S ∪ {i}，它是一个大小为 k + 1 的子集。选择 i 的概率是 1/n，由于 S 是从 {1, 2, ..., n-1} 中均匀随机选择的，i 不在 S 中的概率是 (n-1)/n。因此，返回 S ∪ {i} 的概率是 (k/n) * ((n-1)/n) = k/(n(n-1))。 \u000a\u000a如果 i 在 S 中，算法返回 S，它是一个大小为 k 的子集。选择 i 的概率是 1/n，由于 S 是从 {1, 2, ..., n-1} 中均匀随机选择的，i 在 S 中的概率是 1/n。因此，返回 S 的概率是 (k/n) * (1/n) = k/(n^2)。 \u000a\u000a这些概率的总和是 (k/(n(n-1))) + (k/(n^2)) = k/n * (1/(n-1) + 1/n) = k/n，这是返回大小为 k + 1 的子集的概率。 \u000a\u000a根据数学归纳法原理，我们可以得出结论：对于任何 m ≤ n，大小为 m 的每个可能子集被返回的概率相等。 \u000a\u000a2. 为了证明算法终止并返回一个有效的子集，我们需要考虑递归调用和基本情况。 \u000a\u000a算法使用 m-1 和 n-1 进行递归调用。由于每次递归调用中 m 都减少 1，算法最终将达到 m = 0 的基本情况。此时，算法立即返回一个空集，这是一个有效的子集。 \u000a\u000a在每个递归调用中，算法还调用 RANDOM(1,n) 来选择一个随机整数 i。由于 RANDOM 的最坏情况时间复杂度为 O(1)，这一步不会影响算法的终止。 \u000a\u000a因此，我们可以得出结论：算法终止并返回一个有效的子集。 \u000a\u000a总之，RANDOM-SAMPLE 从集合 {1, 2, ..., n} 中均匀随机抽取大小为 m 的子集。