蓄水池算法證明

蓄水池算法

蓄水池算法是一種大資料随機抽樣算法,對于海量流式資料,在未知資料規模(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個數,也可以使用類似的方式來證明具有相等的機率. 證明完畢.