蓄水池采样的证明

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

证毕