蓄水池采样的证明

  数学 概率论 抽样方法    浏览次数: 273
2

蓄水池方法是可以对数据流进行等概率采样的,问题为什么这个抽样方法是等概率的呢?

 

danny_q   2018-09-07 09:25



   1个回答 
10

我们要从数据流中抽取$k$个数据点,那对于第$n$个样本$X_n$,($n\geq k$),它有$k/n$的概率被选进池子中;如果被选中了,我们随机从池子中的$k$个样本中挑选一个$X_i$被$X_n$取代。这个就是蓄水池算法的基本思想。


---------------------------

下面开始证明

---------------------------


用数学归纳法证明,每个样本被选中的概率的都是相等的。

初始情况是,当前只有$k$个样本,此时每个样本都被选中进入池子,也就是$k /k=1$的概率。

如果我们一共有$n$个数据点,假设每个数据点被选进入池子的概率相等,都是$k / n$。

根据数学归纳法的思想,下面我们只要证明如果一共有$n+1$个数据点,每个数据进入池子中的概率都是$k/(n+1)$。

对于第$n+1$个样本$X_{n+1}$,它进入池子的概率显然是$k/(n+1)$。

对于第$j$个样本$X_j$,$j\leq n$,它在前一轮中已经在池子里的概率为$k/n$。

下面我们分两种情况讨论:第一种情况,$X_{n+1}$没被选中,所以$X_j$依然留在池子中。这种情况的概率为

$$P_1=1-\frac{k}{n+1}=\frac{n+1-k}{n+1}$$

第二种情况,$X_{n+1}$被选中但是$X_j$没有被替换。这种情况发生的概率为

$$P_2=\frac{k}{n+1}\frac{k-1}{k}=\frac{k-1}{n+1}$$

两者相加

$$P_1+P_2=\frac{n}{n+1}$$

所以$X_j$此时在池子中的概率为

$$\frac{k}{n}(P_1+P_2)=\frac{k}{n}\frac{n}{n+1}=\frac{k}{n+1}$$

证毕

SofaSofa数据科学社区 DS面经 问答 实战

MangoCoke   2018-09-08 10:49

很清楚,很6,谢谢! - danny_q   2018-09-14 03:23


  相关主题

滚雪球抽样算法的实现   0回答

bootstrap 一般用在哪些方面   1回答

parametric bootstrap和nonparametric bootstrap的区别是什么?   1回答

蓄水池抽样算法的问题   1回答

自助法(bootstrap)的0.632是怎么来的?   1回答

Jackknife vs Bootstrap   1回答

两阶段抽样和分层抽样是一回事吗?   0回答

python对给定的集合进行有放回抽样?   2回答

python产生一个随机置换?   1回答

SMOTE对于categorical feature如何处理?   2回答

什么是SMOTE sampling方法?   3回答

如何对流数据(stream data)进行无差别抽样   1回答



回答问题时需要注意什么?

我们谢绝在回答前讲“生动”的故事。

我们谢绝“这么简单,你自己想”、“书上有的,你认真看”这类的回答;如果你认为对方的提问方式或者内容不妥,你可以直接忽略该问题,不用进行任何作答,甚至可以对该问题投反对票。

我们谢绝答非所问。

我们谢绝自己不会、硬要回答。

我们感激每一个用户在编写答案时的努力与付出!