博客

题目：

要求从N个元素中随机的抽取k个元素，其中N无法确定

解法：

首先选择N中的前k个数加入“蓄水池”中，然后从第k+1个数开始，以k/k+i(i=1,2,3…)的概率选择这个数，然后在蓄水池中随机选择一个数，并将其替换，N个元素遍历完毕后，蓄水池中的k个数就是随机选择的。

证明：

这里即需要证明每个数出现在蓄水池中的概率都是相等的，拟采用数学归纳法

1.当i=1时，蓄水池中某个数出现的概率

第k+1个数被取出的概率是k/k+1, 这时，蓄水池中每个数出现的概率都是1，同时，一个数被选择到的概率是1/k, 因此，一个数出现在池中的概率是1-（k/k+1)*(1/k)=k/k+1

2.假设第i个数被取出的概率是k/k+i,证明在有k+i+1的样本中，一个数出现在池子里的概率是k/k+i+1

第k+i+1个数被取出的概率是k/k+i+1,  池子中每个数的出现概率都是k/k+i, 池中的数被选择到的概率是1/k, 一个数在池中的概率就是 他出现在池中的概率*他没有被替换的概率，就是（k/k+i）*(1-1/k*k/k+i+1),也就是k/k+i+1