蓄水池抽样

了解了一下蓄水池抽样。
它可以在O(n)的时间内对n个数据进行等概率的随机抽取k个样本,并且适用于n不断增长(就是n未知的情况下),或者n很大(不能放入内存的情况)。
算法的步骤就是:
假设要等概率的抽取样本数为k。那么首先把n个数列中的前k个元素放入到一个长度为k的数组中,称为蓄水池。然后对于之后的第k+1个元素到第n个元素中,第i个元素的时候,生成一个在[1,i]之间的随机数j,如果j小于k,就把蓄水池中的第j个元素换成第i个。
通过数学归纳法证明这样做可以让每个元素都有k/n的概率进入蓄水池。
首先,对于任意的 i,第 i 个元素进入蓄水池的概率为 k / i;而在蓄水池内每个元素被替换的概率为 1 / k; 因此在第 i 轮第j个元素被替换的概率为 (k / i ) * (1 / k) = 1 / i。
那么假设在第(i-1)轮,任意一个元素进入蓄水池的概率均为k/(i-1)。那么在第i轮其被替换概率为1/i,那么继续留在蓄水池的概率为k/(i-1)*(1-1/i)=k/i。得证。
写了个做实验的代码,的确可以说是非常随机了.

发表评论

电子邮件地址不会被公开。 必填项已用*标注