蓄水池采样的证明

  数学 概率论 抽样方法    浏览次数:6132        分享
3

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

 

danny_q   2018-09-07 09:25



   1个回答 
19

我们要从数据流中抽取$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


  相关讨论

证明马尔可夫不等式

柯西分布没有数学期望

什么函数族满足关于最值函数封闭?

今天明天都下雨的概率

概率统计里的iid是什么意思?

概率论问题 求(X+Y)/(X-Y)的分布

条件概率证明P(a,b|c) > P(a,b)

超几何概率问题

一个骰子平均扔多少回才能把六个数字都扔出来至少一次

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

  随便看看

条件概率证明P(a,b|c) > P(a,b)

deep learning中的pooling是什么意思?

yolo v4和yolo v3的主要区别是什么?

z test和t test什么区别?

sklearn中的predict_proba方法的返回值的意义