-2

我的问题与此链接的“算法 R”部分中的示例代码有关https://en.m.wikipedia.org/wiki/Reservoir_sampling

我从该部分复制了以下代码片段。为什么这段代码用逐渐降低的概率替换元素？根据问题，输入中的每个项目都应该具有相同的概率，对吧？

for i = k+1 to n
    j := random(1, i) 
    if j <= k
        R[j] := S[i]

例如，将以下三个输入的随机函数调用与我的水库大小 10 进行比较

  • 随机 (1,15) 获得低于 10 的随机数的机会很高
  • random (1, 100) 获得低于 10 的随机数的机会非常低
  • random (1, 1000) 获得低于 10 的随机数的机会非常低

因此，随着输入的增长，替换项目的机会非常少，那么我们怎么能说水库采样算法是在每个项目上以相等概率选择随机样本的解决方案呢？也许我错过了一些东西，请解释一下。

4

1 回答 1

3

它在算法后面的段落中进行了解释，但关键观察是：R 中的样本候选可以被多次覆盖，但您只会看到最后一次 write 的结果。

因此，当i较小时，您有更高的机会用新样本替换样本，但出于同样的原因，当您到达循环结束时，新样本仍然存在的机会很小。

而如果i接近n，一个值进入的机会就会更R小，但如果它到达那里，它可能不会在以后被覆盖。

如果你把所有的概率加起来，这将是k/n每个元素。

于 2016-08-03T11:05:05.160 回答