data-stream-sampling

有一个无限的整数数据流，如何从中随机地抽取k个整数出来？

这是一个经典的数据流采样问题，我们一步一步来分析。

当k=1时

我们先考虑最简单的情况，k=1，即只需要随机抽取一个样本出来。抽样方法如下：

1. 当第一个整数到达时，保存该整数
2. 当第2个整数到达时，以1/2的概率使用该整数替换第1个整数，以1/2的概率丢弃改整数
3. 当第i个整数到达时，以$$\dfrac{1}{i}$$的概率使用第i个整数替换被选中的整数，以$$1-\dfrac{1}{i}$$的概率丢弃第i个整数

假设数据流目前已经流出共n个整数，这个方法能保证每个元素被选中的概率是$$\dfrac{1}{n}$$吗？用数学归纳法，证明如下：

1. 当n=1时，由于是第1个数，被选中的概率是100%，命题成立
2. 假设当n=m(m>=1)时，命题成立，即前m个数，每一个被选中的概率是$$\dfrac{1}{m}$$
3. 当n=m+1时，第m+1个数被选中的概率是$$\dfrac{1}{m+1}$$,前m个数被选中的概率是$$\dfrac{1}{m} \cdot (1-\dfrac{1}{m+1})=\dfrac{1}{m+1}$$，命题依然成立

由1，2，3知n>=1时命题成立，证毕。

当k>1时

当k > 1，需要随机采样多个样本时，方法跟上面很类似，

1. 前k个整数到达时，全部保留，即被选中的概率是100%，
2. 第i个整数到达时，以$$k/i$$的概率替换k个数中的某一个，以$$1-\dfrac{k}{i}$$的概率丢弃，保留k个数不变

假设数据流目前已经流出共N个整数，这个方法能保证每个元素被选中的概率是$$\dfrac{k}{N}$$吗？用数学归纳法，证明如下：

1. 当n=m(m<=k)时，被选中的概率是100%，命题成立
2. 假设当n=m(m>k)时，命题成立，即前m个数，每一个被选中的概率是$$\dfrac{1}{m}$$
3. 当n=m+1时，第m+1个数被选中的概率是$$\dfrac{k}{m+1}$$,前m个数被选中的概率是$$\dfrac{1}{m} \cdot [\dfrac{k}{m+1} \cdot (1-\dfrac{1}{k})+1-\dfrac{k}{m+1}]=\dfrac{1}{m+1}$$，命题依然成立

由1，2，3知n>=1时命题成立，证毕。

参考资料

• 浅谈流处理算法(1) – 蓄水池采样
• Google Interview Question: Given a stream of integers of… | Glassdoor