Algorithm R蓄水池采样算法原理及实现合理性技术咨询

嘿，我来帮你把这个迭代替换的部分讲透彻——核心其实是确保每个元素最终留在蓄水池里的概率都是k/N（N是总体规模），不管它是前k个元素还是后面的。咱们一步步拆解：

单个新元素的选中概率 #

当处理到第i个元素（i > k）时，算法生成一个范围是1到i的随机数j：

• 如果j ≤ k，就用S[i]替换蓄水池里的R[j]；
• 这意味着S[i]被选进蓄水池的概率是k/i——因为在i个可能的随机数里，有k个会触发替换。

蓄水池原有元素的存活概率 #

假设蓄水池里现在有某个元素X，在处理第i个元素时，X能留在池子里的概率是多少？分两种情况：

1. S[i]根本没被选中：概率是1 - k/i；
2. S[i]被选中了，但没替换X：S[i]被选中的概率是k/i，且它替换的是池子里除X外的k-1个位置之一，概率是(k-1)/k，所以这种情况的概率是k/i * (k-1)/k = (k-1)/i。

把两种情况的概率相加：(1 - k/i) + (k-1)/i = (i - k + k -1)/i = (i-1)/i——这就是原有元素在本轮迭代中存活的概率。

最终所有元素的选中概率都是k/N #

咱们用前k个元素里的某一个（比如S[1]）验证：

• 它一开始就被放进蓄水池（概率1）；
• 然后要躲过从k+1到N每一轮的替换，每一轮存活的概率分别是k/(k+1)、(k+1)/(k+2)、...、(N-1)/N；
• 把这些概率相乘：1 * k/(k+1) * (k+1)/(k+2) * ... * (N-1)/N = k/N。

再看后面的元素（比如S[m]，m > k）：

• 它被选进蓄水池的概率是k/m；
• 之后每一轮（从m+1到N）都存活的概率是m/(m+1) * (m+1)/(m+2) * ... * (N-1)/N = m/N；
• 总概率就是k/m * m/N = k/N。

不管是前k个还是后面的元素，最终留在池子里的概率都是k/N，这就保证了采样的公平性！

直观小例子辅助理解 #

假设k=2，N=5：

• 前两个元素先放进蓄水池；
• 处理第3个元素时，选中概率是2/3，原有元素存活概率是2/3；
• 处理第4个元素时，选中概率是2/4=1/2，原有元素存活概率是3/4；
• 处理第5个元素时，选中概率是2/5，原有元素存活概率是4/5；

计算第一个元素最终存活的概率：1 * 2/3 * 3/4 *4/5 = 2/5 = k/N；
计算第三个元素最终存活的概率：2/3 * 3/4 *4/5 = 2/5 = k/N；
完全一致！

引用自维基百科的示例实现代码：

(* S为待采样数据集，R为结果集 *)
ReservoirSample(S[1..n], R[1..k])
    // 填充蓄水池数组
    for i = 1 to k
        R[i] := S[i]
    // 以逐渐降低的概率替换元素
    for i = k+1 to n
        j := random(1, i) // 注意：范围包含两端
        if j <= k
            R[j] := S[i]

内容的提问来源于stack exchange，提问作者BMBM