0

我对 Reservoir Sampling 算法非常熟悉，我在想如果N给出总大小会怎样。在这种情况下我们能得到什么好处？结果，这是算法：

Let n be the total size of data
Let k be the total size of sample
for each element from data
    if random(0,1) <= k/n
        put this element into sample
        -- k
    -- n
done

乍一看似乎是正确的，但我发现很难证明。任何人都可以帮助我以正式的方式证明这个算法吗？

4

2 回答 2

1

这是Dave 修复的正确性证明。不失一般性地假设流是1..n。我们归纳证明，在m in {0..n}循环迭代之后，样本分布为 的1..m均匀随机k组合的交集1..n。

基本情况m = 0是微不足道的：样本和交集始终为空。给定一个特定的归纳假设m，我们现在证明它m+1。设S是表示迭代后集合的随机变量， 设m是S'表示迭代后集合的随机变量m+1。设&交点。对于所有k-combinations T，我们写

Pr(S' = T & {1..m+1})
    = Pr(S = T & {1..m}) Pr(S' = T & {1..m+1} | S = T & {1..m}),

因为S' = T & {1..m+1}意味着S = T & {1..m}. 通过归纳假设和一些计数，

(n choose k) Pr(S = T & {1..m})
    = ((n - m) choose (k - |T & {1..m}|)).

结合这两个方程，我们得到

(n choose k) Pr(S' = T & {1..m+1})
    = ((n - m) choose (k - |T & {1..m}|)) Pr(S' = T & {1..m+1} | S = T & {1..m}).

通过检查戴夫的程序，

Pr(m+1 in S' | S) = (k - |S|) / (n - m).

现在有两种情况。第一种情况是m+1 in T。

Pr(S' = T & {1..m+1} | S = T & {1..m})
    = Pr(m+1 in S' | S = T & {1..m})
    = (k - |T & {1..m}|) / (n - m)
(n choose k) Pr(S' = T & {1..m+1})
    = ((n - m) choose (k - |T & {1..m}|)) (k - |T & {1..m}|) / (n - m)
    = (n - m - 1) choose (k - |T & {1..m}| - 1)
    = (n - (m+1)) choose (k - |T & {1..m+1}|).

第二种情况是m+1 not in T。

Pr(S' = T & {1..m+1} | S = T & {1..m})
    = Pr(m+1 not in S' | S = T & {1..m})
    = (n - m - (k - |T & {1..m}|)) / (n - m)
(n choose k) Pr(S' = T & {1..m+1})
    = ((n - m) choose (k - |T & {1..m}|)) (n - m - (k - |T & {1..m}|)) / (n - m)
    = (n - m - 1) choose (k - |T & {1..m}|)
    = (n - (m+1)) choose (k - |T & {1..m+1}|).

在这两种情况下，我们都证明Pr(S' = T & {1..m+1})具有正确的值。

于 2014-10-07T14:56:20.077 回答
0

如果你想要 K 个样本：让 K 是所需的样本，k 是到目前为止获得的样本。设 N 是数据的总大小， n 是到目前为止采样的集合。然后检查是否随机（0,1）<=（Kk）/（Nn）。

您还可以获取流的每个 (N/K)'th 元素，或者将流划分为 K 个子流并从每个子流中随机获取一个元素。

于 2014-10-07T11:58:03.627 回答