蓄水池算法证明

蓄水池算法

蓄水池算法是一种大数据随机抽样算法,对于海量流式数据,在未知数据规模(N)的情况下.对数据样本进行随机选取k个样本,来达到均匀抽样的目的:对于每个样本被选择的概率都是 P x i 被 选 择 = k n P_{x_i被选择}=\frac{k}{n} Pxi​被选择​=nk​.

算法

int a[k]={x1,x2,....,xk}  //用数据流中的前k个数来初始化一个容量为k的数组
for i = k to N:
    m=random(0,i)  //在[0,i] 之间随机
    if m < k:
        exchange a[m] and a[i] 
           

证明

对于第i个数(i>k)来说,它被选择的概率是 k i + 1 \frac{k}{i+1} i+1k​,如果它被选择替换蓄水池中的一个数,那么,对于第i+1个数来说如果要替换第i个数那么概率为 k i + 1 ∗ 1 k = 1 i + 1 \frac{k}{i+1}*\frac{1}{k}=\frac{1}{i+1} i+1k​∗k1​=i+11​,保留第i个数的概率为 1 − 1 i + 1 1-\frac{1}{i+1} 1−i+11​.以此类推,直到第N个数替换第i个数:

k i ∗ ( 1 − 1 i + 1 ) ∗ ( 1 − 1 i + 2 ) ∗ . . . ( 1 − 1 N ) = k N \frac{k}{i} *(1-\frac{1}{i+1})* (1-\frac{1}{i+2}) *...(1-\frac{1}{N})=\frac{k}{N} ik​∗(1−i+11​)∗(1−i+21​)∗...(1−N1​)=Nk​

对于第1~k个数,也可以使用类似的方式来证明具有相等的概率. 证明完毕.