蓄水池抽样.md

蓄水池抽样

1. 单机

（1）维护一个大小为 M 的数组. 记当前接收的是第 N 个数据（这里从 1 开始，代码中从 0 开始）

（2）如果 N<=M, 直接插入（对于前 M 个元素，全部留下）

（3）如果 N>M, 就取一个 1N 之间的随机数 index。 如果 index 在 1M 之间, 则用新接收的数据替换第 index 个数据; 否则丢弃

for(int i = 0; i < M; ++i)
  R[i] = L[i];
for(int i = M; i < N; ++i) {
  // 该函数返回区间为[0,n)，不包括右边界，故需要增1
  j = rand.nextInt(i+1);
  if(j < M)
    R[j] = L[i];
}
return R;

证明

（1）假设当前是第 M+1 个元素, 它被丢弃的概率是 1/(M+1), 留下的概率就是 M/(M+1). 对于已经在集合中的 M 个元素, 每个以 1/(M+1)的概率被丢弃, 留下的概率也是 M/(M+1).

（2）假设当前是第 M+2 个元素, 它被丢弃的概率是 2/(M+2), 留下的概率是 M/(M+2). 对于前 M+1 个元素, 它们在集合中的概率是 M/(M+1)(见上一个分析). 这一次, 它们每个被以 1/(M+2)的概率被丢弃, 留下的概率就是 M/(M+1) * (M+1)/(M+2) = M/(M+2)

（3）依次类推, 到接受第 N 个元素时, 每个元素被抽取的概率就是 M/N.

2. 分布式

（1）假设有K个机器, 每个机器维护大小为M的数组, 并记录该机器接受的数据总数Ni
（2）当机器获取新数据时, 进行单机的蓄水池抽样.
（3）当进行采样时, 重复M次以下操作:
（3.1）取随机数d在[0,1)之间, 记N=Sum(Ni | i=1...K)
（3.2）若d<N1/N则从第一个机器上等概率抽取一个元素.
（3.3）若N1/N<=d<(N1+N2)/N则从第二个机器上等概率抽取一个元素
（3.4）依此类推.

证明

（1）假设 Ni>M

因为第 i 个机器上数据的留存概率为 M/Ni, 而采样时又以 Ni/N 的概率抽取该机器, 又以 1/M 的概率等概率不放回地选取一个元素, 所以第 i 个机器上一个数据被抽中的概率为 M/Ni _ Ni/N _ 1/M = 1/N. 这样重复 M 次, 每个元素被抽取到的概率就是 M/N.

（2）假设 Ni<=M

第 i 个机器上数据的留存概率为 1, 采样时以 Ni/N 的概率抽取该机器, 又以 1/Ni 的概率等概率不放回地选取一个元素, 所以第 i 个机器上一个数据被抽中的概率为 1/N. 同样, 重复 M 次让每个元素被抽取到的概率为 M/N.

作者：柳正来 链接：https://www.jianshu.com/p/eea05fb27e3f 来源：简书 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。