Reservoir Sampling Proof

http://en.wikipedia.org/wiki/Reservoir_sampling

array R[k];    // result
integer i, j;

// fill the reservoir array
for each i in 1 to k do
    R[i] := S[i]
done;

// replace elements with gradually decreasing probability
for each i in k+1 to length(S) do
    j := random(1, i);   // important: inclusive range
    if j <= k then
        R[j] := S[i]
    fi
done

 一开始有k个
每个数字被选进来的概率都是1

第k+1个，要放进去，那么前面每个被换出去的概率是 1/(k+1), 没被换出去的概率是k/(k+1)
有k-1个数字，是留下来了，留下来的概率是k/(k+1)
有1个数字，换出去了，新进来的，被选进来的概率是 k/(k+1)
所有数字留下来的概率都是k/(k+1)

然后，处理第k+2个
第k+2个，要放进去，那么前面每个被换出去的概率是 1/(k+2), 没被换出去的概率是(k+1)/(k+2),
有k-1个数字, 是留下来了, (k+1)/(k+2), 再加上上一次的概率，留下来的总概率是k/(k+1)  *   (k+1)/(k+2) = k/(k+2)
有1个数字，换出去了，那么新进来的数字被选进来的概率是 k/(k+2)
所有数字留下来的概率都是k/(k+2)


假设当前处理了n个样本，选出了k个数，并且满足条件
k个选出的样本，每个样本在n个样本中被抽出的概率都是k/n
那么处理第n+1个样本的时候
1). 第n+1个样本被选进k的概率是 k/(n+1)，即，被换进的样本的概率是 k/(n+1)
2). 对于前k个样本，留下的概率是 n/(n+1)，与之前的概率 k/n，做条件概率相乘，截止到目前该样本仍然留在k个样本中的总概率是 n/(n+1) * k/n = k/(n+1)
综合1) 2), k个样本每个留下的概率都是 k/(n+1)

以此类推，对于每个状态，即处理过的样本总量为n的时候，所有留下来的样本的全局总概率都是k/n