algorithm - 河流水库取样证明

Question

我非常熟悉 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

乍一看似乎正确，但我发现很难证明。谁能帮我正式证明这个算法？

Answer 1

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

基本情况 m = 0 很简单:样本和交集始终为空。给定特定 m 的归纳假设，我们现在针对 m+1 证明它。设 S 是表示 m 次迭代后集合的随机变量，令 S' 是表示 m+ 后集合的随机变量1 迭代。设 & 为交集。对于所有k-组合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}).

通过检查 Dave 的程序，

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不在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}) 具有正确的值。