algorithm - 水库取样问题

Question

这篇 MSDN 文章证明了Reservoir Sampling 算法的正确性如下：

---

1. 基本情况是微不足道的。对于第 k+1 种情况，位置 <= k 的给定元素 i 在 R 中的概率为 s/k。

2. i 被替换的概率是第 k+1 个元素被选择的概率乘以 i 被选择被替换，即：s/(k+1) * 1/s = 1/(k+1)，并且概率 i没有被替换的是 k/k+1。

3. 所以任何给定元素在 k+1 轮后持续的概率是：（在 k 步中选择，而不是在 k 步中删除）= s/k * k/(k+1)，即 s/(k+1)。

4. 因此，当 k+1 = n 时，任何元素都以概率 s/n 出现。

---

关于第 3 步：

• k+1 rounds提到了什么？

• 是什么chosen in k steps, and not removed in k steps？

• 为什么我们只计算第一步R之后已经存在的元素的这个概率s？

Answer 1

你熟悉归纳证明吗？ k只是算法的中间步骤，证明不变量自始至终都是正确的，在这种情况下，k-th项目将具有s/k为所有人选择的概率的概率k。

Answer 2

• “k+1 轮”表示“在考虑了输入序列中的第 (k+1) 项之后”
• s/k 是给定项目在 k 步后（通过归纳）进入水库的概率，k/(k+1) 是第 (k+1) 个项目不会被替换的概率步
• 我们要确保每个输入项以相同的概率保留在水库中。因此，在我们的计算中，我们只对每一步中保留在水库中的项目感兴趣。

Answer 3

我们从 k 项流中采样 s 项（其中 k 非常大，因此我们逐项处理流）。

处理流中的每个项目称为“回合”。

在一轮中，我们可能会用新项目替换已经存在的元素之一。

“在 k 步中选择”意味着在该项目出现在流中的那轮期间，我们选择用它替换其他一些项目（我们没有忽略它）。“未在 k 步中删除”意味着从那一刻起，我们没有选择用流中的一些新项目替换该项目。