有一个无限的整数数据流，如何从中随机地抽取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时命题成立，证毕。

参考资料