`
handspeaker
  • 浏览: 64419 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

有关蓄水池抽样(Reservoir Sampling)和自己的一些思考

阅读更多

最近在校论坛上看到了一个叫蓄水池(Reservoir Sampling )抽样的问题,感觉很有趣,记录如下:

 

题目:要求从N个元素中随机的抽取k个元素,其中N无法确定。


解法:

 

Init : a reservoir with the size: k
        for    i= k+1 to N
            M=random(1, i);
            if( M < k)
                 SWAP the Mth value and ith value
       end for

 

上述伪代码的意思是:先选中第1到k个元素,作为被选中的元素。然后依次对第k+1至第N个元素做如下操作:

每个元素都有k/x的概率被选中,然后等概率的(1/k)替换掉被选中的元素。其中x是元素的序号。

 

网上找到的证明,用数学归纳法证的:

 

每次都是以 k/i 的概率来选择
例: k=1000的话, 从1001开始作选择,1001被选中的概率是1000/1001,1002被选中的概率是1000/1002,与我们直觉是相符的。

接下来证明:
假设当前是i+1, 按照我们的规定,i+1这个元素被选中的概率是k/i+1,也即第 i+1 这个元素在蓄水池中出现的概率是k/i+1
此时考虑前i个元素,如果前i个元素出现在蓄水池中的概率都是k/i+1的话,说明我们的算法是没有问题的。

对这个问题可以用归纳法来证明:k < i <=N
1.当i=k+1的时候,蓄水池的容量为k,第k+1个元素被选择的概率明显为k/(k+1), 此时前k个元素出现在蓄水池的概率为 k/(k+1), 很明显结论成立。
2.假设当 j=i 的时候结论成立,此时以 k/i 的概率来选择第i个元素,前i-1个元素出现在蓄水池的概率都为k/i。
证明当j=i+1的情况:
即需要证明当以 k/i+1 的概率来选择第i+1个元素的时候,此时任一前i个元素出现在蓄水池的概率都为k/(i+1).
前i个元素出现在蓄水池的概率有2部分组成, ①在第i+1次选择前得出现在蓄水池中,②得保证第i+1次选择的时候不被替换掉
①.由2知道在第i+1次选择前,任一前i个元素出现在蓄水池的概率都为k/i
②.考虑被替换的概率:
首先要被替换得第 i+1 个元素被选中(不然不用替换了)概率为 k/i+1,其次是因为随机替换的池子中k个元素中任意一个,所以不幸被替换的概率是 1/k,故
前i个元素(池中元素)中任一被替换的概率 = k/(i+1) * 1/k = 1/i+1
则(池中元素中)没有被替换的概率为: 1 - 1/(i+1) = i/i+1
综合① ②,通过乘法规则
得到前i个元素出现在蓄水池的概率为 k/i * i/(i+1) = k/i+1
故证明成立

 

自己的思考:

很多人都会想,问什么这么做呢?这种方法是怎么想到的呢?我刚开始也很困惑,后来仔细想了一遍问题,就豁然开朗了。题目中明确规定N无法确定 ,这就意味着,无论N或大或小,这N个元素都要被等概率的抽取出来。那么,可以这么考虑,N是一个动态增加的数字,例如:先让你从100个元素中等概率抽取出10个元素。后来又向集合中添加了20个元素,变成了120个元素等概率抽取10个,怎么样才能随着N的动态改变而让N无论等于多少时这N个元素都等概率被抽取呢?

其实很简单,再看一眼上面的算法,第x个元素被选中的概率为k/x,这个可以等价为有x个元素,等概率抽取k个元素,每个元素被抽中的概率。也就是说,每当元素数量增加1的时候,就要对所有元素等概率抽取一次,这样当然能保证目前元素数量下是等概率抽取,这也是元素数量增加后,下次概率计算的先决条件。

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics