蓄水池采样的证明

  数学 概率论 抽样方法    浏览次数:918        分享
2

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

 

danny_q   2018-09-07 09:25



   1个回答 
15

我们要从数据流中抽取$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面试题库 DS面经

MangoCoke   2018-09-08 10:49

很清楚,很6,谢谢! - danny_q   2018-09-14 03:23
谢谢大佬 - 长路漫漫   2019-03-18 11:11


  相关主题

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

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

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

Jackknife vs Bootstrap   1回答

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

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

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

用一个骰子生成1到7的随机数?   5回答

对于独立正态变量X, Y ~ N(0,1),X+Y和X-Y是否独立?   1回答

柯西分布没有数学期望   1回答

什么是Jensen不等式?有什么直观的解释?   2回答

今天明天都下雨的概率   1回答



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

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

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

我们谢绝答非所问。

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

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