在长度未知的数据流中，要如何采样k个样本，使得这k个样本被采样的概率是相同的？
面试中被问到的一个问题，当时没有很好地理解题目。仔细一想这个问题的应用还是很广泛的，比如要在大量级的点击事件数据流中采样点击事件，从而从事件中获得一些特征，那么为了保证采样的公平性，使得获得的特征更加客观，就需要采样时所有的样本被获取的概率是一样的。
问题描述
设定一个长度为k的数组，目的是为了保证这k个数据在数据流不断流入的情况下，他们被选中到这个数组里的概率是一样的。
对于前k个流入的数据，都会被直接选中，所以直接放到数组里，它们的概率是1。
为了保证数据流抽样的概率相等，数组中的数据随时可能被替换，即我们要保证新来的数据n被选中的概率和池子里的数据保留的概率都是$\frac{k}{n}$。
对于前k个数据，他们在数据量小于k时会一直存在于数组中，若数据量一旦大于k，则它们有可能被替换。当第k+1个数据流入时，新数据被采样到数组里的概率是$\frac{k}{k+1}$，这也是一旦数组中某个元素被选中，它就以这个概率被替换；那么数组中某个元素被选中的概率自然是$\frac{1}{k}$，所以某个元素被选中且替换的概率是$\frac{1}{k}*\frac{k}{k+1}=\frac{1}{k+1}$，则它留下来的概率是$\frac{k}{k+1}$。同理，当第k+2个数据流入时，它被留下来的概率是$\frac{k+1}{k+2}$。那么当有n个数据流入时，它依然还在数组中的概率是：
$$1*\frac{k}{k+1}\frac{k+1}{k+2}\cdots\frac{n-1}{n}=\frac{k}{n}$$
对于k之后的数据j，它被选中到数组里的概率是$\frac{k}{j}$，若它被选中了，则它不被下一个数据替换的概率是$1-\frac{k}{j+1}*\frac{1}{k}=\frac{j}{j+1}$，同理，若其没有被替换，则第j+2个数据流入时没有被替换的概率是$\frac{j+1}{j+2}$，那么它被保留的概率是：
$$\frac{k}{j}\frac{j}{j+1}\cdots*\frac{n-1}{n}=\frac{k}{n}$$
所以所有数据被保留的概率都是$\frac{k}{n}$。
对于实现来说，当有一个新数据时，在当前数据长度的范围内随机选择一个数m，若它小于等于k，则数组中m位置的数字会被新数字替换。
参考资料
[用Python写算法 | 蓄水池算法实现随机抽样](