蓄水池抽样算法（Reservoir Sampling）

问题描述

给定一个数据流，数据流长度N很大，且长度不可预知。问如何在仅遍历一次数据的情况下，如何等概率 抽取m个样本。

问题分析

首先明确概念：等概率抽样是一种抽样方法，是指总体中的每个个体被抽中的概率相等。
关键点：

1. N很大且不可预知，故无法一次性读入内存；
2. 抽样的时间复杂度为O(N)；
3. m个样本，每个样本被选取的概率为m/n；

代码实现

int[] reservoir = new int[m];//reservoir中存放m个样本

for (int i = 0; i < reservoir.length; i++)
{
    reservoir[i] = dataStream[i];//dataStream代表未知长度的数据流
}

for (int i = m; i < dataStream.length; i++)
{
    // 随机获得一个[0, i]内的随机整数
    int d = rand.nextInt(i + 1);
    // 如果随机整数落在[0, m-1]范围内，则替换蓄水池中的元素
    if (d < m)
    {
        reservoir[d] = dataStream[i];
    }
}

算法的直观理解：

初始化蓄水池，容量为给出的m

读取数据流中的前m个数，放入蓄水池中

从第m+1个数开始遍历数据流，对于每次循环都有：
	1.根据当前遍历的序号，创建一个不大于这个序号的随机数；
	2.如果随机数 < m（即该随机数落入蓄水池中），则将该随机数对应的蓄水池中的数替换为当前序号对应的数

难以想象，简短地几行代码，就能够实现一次遍历抽样后，蓄水池中的每个元素都以m/N的概率被选取。

数学证明

明白了问题，也了解了代码的实现，接下来就是分析其中的数学原理了。
不妨采用数学归纳法。
一、考查m=1时的情况
不难看出，当N=1和N=2时，结论是正确的。
当N=3时，分别讨论第i号元素（i∈[1,3]）最终被抽取到蓄水池中的概率：
假设i=1，蓄水池默认存放的就是i；
当数据流遍历到第2号元素时，i存活的概率为1/2；
当数据流遍历到第3号元素时，i存活的概率为1/22/3。这里的2/3就是由上面代码中if (d < m)计算而来的。即，当遍历到第3号元素时，从[1,3]之间抽取一个小于3的数字的概率，就等于2/3。故i存活的概率为1/22/3=1/3。
同理，可证i=2和i=3时，i存活的概率分别都是1/3。
不失一般性的，可令N=k。则对任意i（i∈[1,3]），P(i)存活的概率为1/22/33/4*…*(N-1)/N=1/N

二、考查m>1时的情况
初始的前m个元素先放在蓄水池中，该m个元素被抽样的概率均为m/N。
对于m之后的元素，令其为k（k∈[m+1,N]），则第k个元素存活的概率为
P(k)=选择k的概率 * (对于其后的每一个元素：不被选择的概率+被选择的概率*不替换第m个对象的概率），即

不妨添加我的微信公众号，每日精品原创干货不容错过。