储集层采样了解概率

Question

我在理解水库采样所涉及的概率时遇到了困难。下面是我见过的几乎所有地方都使用过的示例代码：

    1/*
    2  S has items to sample, R will contain the result, K number of items to select
    3*/
    4ReservoirSample(S[1..n], R[1..k])
    5  // fill the reservoir array
    6  for i = 1 to k
    7      R[i] := S[i]
    8
    9 // replace elements with gradually decreasing probability
    10  for i = k+1 to n
    11    j := random(1, i)   // important: inclusive range
    12    if j <= k
    13        R[j] := S[i]

我的理解是正确的吗(？)：假设我们有k=3，输入= 100,200,300,400,500，而我目前在500索引。500替换水库中300的概率(大小为3)=在水库中选择300的概率*选择500的概率，只有当随机函数返回的指数小于或等于5个选择中的3个时才可能= 1/3 * 3/5 = 1/5

Answer 1

你的理解似乎不正确。500被选中的概率与300被选中的概率没有任何关系。

您应该查看gfg link for the same. "How How this work?“部分，该部分说明了以下内容：

情况1:对于最后的n-k个流项，即对于streami，其中k <= i为了简化证明，让我们首先考虑最后一项。最后一项在最终库中的概率=为最后一项挑选前k个索引之一的概率= k/n (从大小为n的列表中挑选k项之一的概率) 现在让我们考虑倒数第二项。倒数第二项在最终reservoir[]中的概率=[在streamn n-2的迭代中挑选前k个索引之一的概率]X[在streamn n-1的迭代中挑选的索引与streamn 2的索引不同的概率]= k/(n-1)*(n-1)/n = k/n。 类似地，我们可以考虑从streamn-1到streamk的所有流项目的其他项目，并推广证明。 情况2:对于前k个流项，即对于streami，其中0 <= i