蓄水池采样算法

问题叙述

常见采样方式有三种:

  1. 从 100000 份调查报告中抽取 1000 份进行统计。
  2. 从一本很厚的电话簿中抽取 1000 人进行姓氏统计。
  3. 从 Google 搜索 “Ken Thompson”，从中抽取 100 个结果查看哪些是今年的。
    对于第一种方式我们可以采用从[0,100000-1]中随机采样的方式,如果遇到已经采样的就重新采样,这样的方式如果遇到采样比例很高可能会遇到重新采样次数过多的情况.
    对于第二种表述的是我们不知道总体是多少,也就无法确定随机范围.
    对于第三种表述的是总体数据过于庞大,无法直接放到内存中.

蓄水池采样算法

为此我们引入蓄水池采样算法,该算法能够保证在$n$个数据中取$k$个,每个数据被采样的概率都是$\frac{k}{n}$。
算法语言描述:

  1. 先选取$n$个元素中的前$k$个元素，保存在集合$A$中
  2. 从第$i(k+1<=i<=n)$个元素开始，每次先以概率$\frac{k}{i}$选择是否让第个元素留下。若第$i$个元素存活，则从$A$中随机选择一个元素$j$并用该元素替换它;否则直接淘汰该元素;
  3. 重复1和2
    伪代码:
    1
    2
    3
    4
    5
    1. 取前k个数放到用来初始化数组池
    2. for i= k+1~n:
    3.     j = random(1,i)
    4.     if j<=k:
    5.        swap(j,i)

就这么简答！！！！

算法证明

证明目标:对于这$n$个元素,我们要证明算法结束之后每个元素留下的概率都是$\frac{k}{n}$,现在把数据分为两部分,$k$之前和$k$之后。
证明:
对于第$I(I<=k)$个元素,初始状态被留下的概率是1,到了第$k+1$步时,此时第$k+1$个数被留下的概率是$\frac{k}{k+1}$(代码第3、4行,也就是从(1,k+1)中取到的j是前k个),我们从当前数组池A中随机取一个用来替换第$j$个元素,正好取到$I$的概率是$\frac{1}{k}$,也就是说,该步中第$j$个数正好替换第$I$个数的概率是$\frac{k}{k+1} \times \frac{1}{k}=\frac{1}{k+1}$,其实说简单点也就是从(1,k+1)个数中正好取到第$I$个的概率.谨记我们的目标,我们要让第$I$个数留下,也就说第$k+1$步它留下的概率是$1-\frac{1}{k+1}=\frac{k}{k+1}$,同理,第$k+2$步它留下的概率是$\frac{k+1}{k+2}$,则到了第$n$步,它仍然留下的概率是:

也就是说第$1$到$k$个元素留下的概率是$\frac{k}{n}$,下面再看第$k+1~n$个元素
对于第$J(k+1,n)$个元素,在第$J$步被选中留下的概率是$\frac{k}{J}$,下面我们要在剩下的步骤中让他不被替换,不被替换的概率在上面我们已经计算过了,则在$J+1$步不被替换的概率是$\frac{j}{J+1}$,则最终到第$n$步,第$J$个元素留下的概率是:

也就是说第$k+1$到$n$个元素留下的概率仍然是$\frac{k}{n}$
证毕!!!!!