蓄水池抽样算法和证明

蓄水池抽样是一个online sampling问题,还有更复杂的带权重的蓄水池抽样算法,可以参考:Weighted Random Sampling (2005; Efraimidis, Spirakis)

问题描述

问题:有个n行的流式文件,n很大而且不知道大小,如何一行一行得读,并最终随机采样k行,k是一个有限的数字。需要保证n行读完之后保留下来的这k行 每一行都是完全随机出现的。(流式文件很大只能读一次 one pass)

说明:所谓的蓄水池抽样还是很形象的,蓄水池就是这个k容量的池子,新来的第i号元素总是以k/i的概率替换掉池子里的元素,可以证明最后的k个元素是以等概率k/m留在池子里(当然,如果最终流失文件从头到全部读完,即m=n,则等概率为k/n)。

注意:问题的表述,必须是整个文件从头到位n行都读完,才能保证蓄水池里的留下来的元素是等概率k/n。如果是完全没有头尾的流式数据,那么只能保证你读取过数据里是等概率的,比如读取了m行,那么就是等概率k/m。理解了这个样本总体的概念才能理解证明。

算法伪码

i = 0
reservoir[]
for ( filestream >> x)
    i++
    if i<=k
        do reservoir.push(x)
    else
        r = rand(1, i) // get a uniform random number between [1,i]
        if (r<=k)
            swap(reservoir[r], x)

算法证明

我们需要证明的是上述算法 “对每一个最终在reservoir中的元素出现的概率都相同, 即 k/n”

先把读到的前k个对象放入“水库”,对于第k+1个对象开始,以k/(k+1)的概率选择该对象,以k/(k+2)的概率选择第k+2个对象,以此类推,以k/m的概率选择第m个对象(m>k)。如果m被选中,则随机替换水库中的一个对象。最终每个对象被选中的概率均为k/n。

第m个对象被选中的概率=选择m的概率*∏(其后元素不被选择的概率+其后元素被选择的概率*不替换第m个对象的概率)

用概率语言描述,这里其实是n次选择事件,第m个对象被选择的概率,由第m次选择事件到第n次选择事件决定的,所以求解第m个对象最终被选中的概率,其实是在求这n-m+1次事件的联合概率。

P(第m次选择选中m对象)=k/m P(第m+1次选择没有把m对象丢掉)=P(第m+1次选择没有选中m+1对象)+P(第m+1次选择选中m+1对象 且 没有把池子里的m对象替换掉) 【注】该步骤根据概率公理3,互斥事件任一发生的概率等于各自概率之和。 P(第m+1次选择没有选中m+1对象)=1-P(第m+1次选择选中m+1对象)=1-k/(m+1)=(m+1-k)/m P(第m+1次选择选中m+1对象 且 没有把池子里的m对象替换掉 ) = P(第m+1次选择选中m+1对象) * P(没有把池子里的m对象替换掉) = k/(m-1) * (k-1)/k 【注】该步骤其实也对应两个事件:选择m+1对象,然后再替换池子里的m对象。 … P(第n次选择没有把m对象丢掉)=P(第n次选择没有选择n对象)+P(第n次选择选中n对象 且 没有把池子里的m对象替换掉) P(第n次选择没有选择n对象) = 1-k/n = (n-k)/n P(第n次选择选中n对象 且 没有把池子里的m对象替换掉)=P(第n次选择选中n对象)*P(没有把池子里的m对象替换掉) = k/n * (k-1)/k

把上面的所有概率乘起来,得到第m个对象最终被选中的联合概率:

后记:另一个证明见这里,利用了后验概率证明,感觉搞复杂了。

一个变种

问题:在不知道文件总行数n的情况下,如何从文件中随机的抽取一行?

说明:这其实是蓄水池抽样的退化问题,此时蓄水池容量k=1。

解法:我们总是选择第一个对象,以1/2的概率选择第二个,以1/3的概率选择第三个,以此类推,以1/m的概率选择第m个对象。当该过程结束时,每一个对象具有相同的选中概率,即1/n。

证明:第m个对象最终被选中的概率P=选择m的概率*其后面所有对象不被选择的概率,同上面的蓄水池算法,这也是一个联合概率。