蓄水池采样

问题描述

给定一个无限的数据流，要求随机取出 k 个数。也就是说当数据流有 N 个数据时，不论 N 为多少，每个数被取出的概率都为 k/N

算法

• 先取出前 k 个数；
• 从第 k+1 开始，以 k/i 的概率取出这个数，并随机替换掉之前已经取出的 k 个数中的一个。

Init a reservoir with the size k
for i = k + 1 to N
     M = random(1, i);
     if (M < k)
         SWAP the Mth value and ith value
end for

证明

使用归纳法进行证明，其中 i 表示当前到来的数据编号。

• 当 i==k+1 时，该数以 k/(k+1) 被取出。当该数被取出时，需要替换前 k 个数中的某个数，被替换的概率为 k/(k+1) · 1/k = 1/(k+1)，这个数被保留的概率即为 1 - 被替换的概率 = 1 - 1/(k+1) = k/(k+1)。
• 假设 i==p 时符合条件，即前 p 个数都以 k/p的概率被取出。当 i==p+1 时，该数被取出概率为 k/(p+1)。对于前 p 个数，该数被取出要符合两个条件：之前被取出、没有被第 p+1 的数替代。没有被第 p+1 的数替代的概率 = 1 - 被第 p+1 的数替换。因此总概率为 k/p ·(1- k/(p+1)·1/k) = k/ (p+1) 。

综上所述，得证。