Random Sampling

随机算法中一个很基本的问题是怎么做随机抽样。比如,如何从N个元素中等概率随机抽n个出来。(n<N)

总的来说这个问题有三种解法:选择抽样、蓄水池抽样、随机洗牌。

一. 选择抽样。

理论来说,每个元素被抽中的概率应该是p=n/N。但是,如果我们对集合的每个元素都按照固定概率p选择是不是抽中它,那么结果未必那么凑巧抽中n个。

所以这个p应该是变化的。假设已经抽中了m个,那么p应该是m的函数。通过计算可得,原数组第t个元素被抽中的概率p=(n-m)/(N-t+1)。t从1开始计数。m是从0开始计数,每抽中一个就加1。

这个算法不用遍历原数组的所有元素,抽够了就中止。

二. 蓄水池抽样。

首先,我们搞一个蓄水池,size=n。然后放水装满。也就是把前n个元素扔这个池子里去。

然后,把剩余的这些元素,每个以一定概率把它扔进蓄水池中,随机替换掉池子中一个现有的。(池子中每个元素都是以相等概率被替换掉)

蓄水池装满后接下来该处理第n+1个元素,那么显然,它被抽中的概率应该是\( \frac{n}{n+1} \) 。(因为目前是从n+1个元素中抽n个)

以此类推,第t个元素被抽空的概率是:\( \frac{n}{t} \)。其中t从1开始计数,蓄水池最开始那n个元素也要被数进去。

证明: 第t个元素被扔进池子的概率是\( \frac{n}{t} \)。它被第t+1个元素替换出去的概率是 \( \frac{n}{t+1} * \frac{1}{n} = \frac{1}{t+1} \) 。所以,在经历了第t+1个元素后,它依然留在池子里的概率是 \( \frac{n}{t} * ( 1- \frac{1}{t+1}) = \frac{n}{t+1} \) 。 以此类推,直到第N个元素后,它依然在池子里的概率是\( \frac{n}{N} \)。

三. 随机洗牌

把输入的这些元素随机打乱(比如用std::random_shuffle()函数。然后取前n个。 把代码写出来仔细看看,它跟蓄水池抽样其实是完全一样的。

此博客中的热门博文

在windows下使用llvm+clang

少写代码,多读别人写的代码

tensorflow distributed runtime初窥