1

我无法理解储层采样所涉及的概率。下面是我在几乎所有地方都看到过的示例代码：

    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 并且 input = [100, 200, 300, 400, 500] 并且 i 目前处于 500 索引。500 替换 300 在水库中的概率（大小为 3）= 在水库中选择 300 的概率 * 选择 500 的概率只有当随机函数返回的索引小于或等于 3 时才有可能5 个选择 = 1/3 * 3/5 = 1/5

4

1 回答 1

-1

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

您应该查看gfg 链接。“这是如何运作的？” 部分，其中规定了以下内容：

案例 1：对于最后 nk 个流项目，即对于 stream[i]，其中 k <= i < n 对于每个这样的流项目 stream[i]，我们选择一个从 0 到 i 的随机索引，如果选择的索引是以下之一前 k 个索引，我们将选取索引处的元素替换为 stream[i]

为了简化证明，让我们首先考虑最后一项。最后一个项目在最终存储库中的概率 = 为最后一个项目选择前 k 个索引之一的概率 = k/n（从大小为 n 的列表中选择 k 个项目之一的概率）

现在让我们考虑倒数第二项。倒数第二个项目在最终存储库中的概率[] = [在迭代中为流 [n-2] 选取前 k 个索引之一的概率] X [在迭代中为流 [n-1] 选取索引的概率] 与为 stream[n-2] ] = [k/(n-1)]*[(n-1)/n] = k/n 选取的索引不同。

类似地，我们可以考虑从 stream[n-1] 到 stream[k] 的所有流项的其他项，并推广证明。

情况 2：对于前 k 个流项目，即对于 stream[i]，其中 0 <= i < k ]。来自 stream[0..k-1] 的项目在最终数组中的概率 = 当项目 stream[k]、stream[k+1]、...时未选择该项目的概率。考虑流[n-1] = [k/(k+1)] x [(k+1)/(k+2)] x [(k+2)/(k+3)] x … x [ (n-1)/n] = k/n

于 2017-09-03T15:32:50.640 回答