data-stream-sampling
有一个无限的整数数据流，如何从中随机地抽取 k 个整数出来？
这是一个经典的数据流采样问题，我们一步一步来分析。
当 k=1 时
我们先考虑最简单的情况，k=1，即只需要随机抽取一个样本出来。抽样方法如下：
- 当第一个整数到达时，保存该整数
- 当第 2 个整数到达时，以 1/2 的概率使用该整数替换第 1 个整数，以 1/2 的概率丢弃改整数
- 当第 i 个整数到达时，以$$\dfrac{1}{i}$$的概率使用第 i 个整数替换被选中的整数，以$$1-\dfrac{1}{i}$$的概率丢弃第 i 个整数
假设数据流目前已经流出共 n 个整数，这个方法能保证每个元素被选中的概率是$$\dfrac{1}{n}$$吗？用数学归纳法，证明如下：
- 当 n=1 时，由于是第 1 个数，被选中的概率是 100%，命题成立
- 假设当 n=m(m>=1)时，命题成立，即前 m 个数，每一个被选中的概率是 $$\dfrac{1}{m}$$
- 当 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，需要随机采样多个样本时，方法跟上面很类似，
- 前 k 个整数到达时，全部保留，即被选中的概率是 100%，
- 第 i 个整数到达时，以$$k/i$$的概率替换 k 个数中的某一个，以$$1-\dfrac{k}{i}$$的概率丢弃，保留 k 个数不变
假设数据流目前已经流出共 N 个整数，这个方法能保证每个元素被选中的概率是$$\dfrac{k}{N}$$吗？用数学归纳法，证明如下：
- 当 n=m(m<=k)时，被选中的概率是 100%，命题成立
- 假设当 n=m(m>k)时，命题成立，即前 m 个数，每一个被选中的概率是 $$\dfrac{1}{m}$$
- 当 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 时命题成立，证毕。