蓄水池抽样算法

题目：要求从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

      

评论

2 楼 johnkeepmoving 2014-10-12  

师兄, 想不到搜蓄水池算法搜到你这来了哈...

1 楼 javaboy8282 2012-09-20  

楼主可否贴出代码  代码更直观一点