最近做数据库作业，需要对几个 G 的数据进行抽样，比如抽 100 万行，需要边扫边抽样，不能存储所有的行之后再抽样。

那如何进行抽样才能让每行抽到的概率相等呢？

做法很简单，假设一共需要抽样 $s$ 行，当前扫描到了第 $n$ 行（$n$ 从 1 开始），那么

1、若 $n \le s$，则直接加入到抽样数组中
2、否则以 $s / n$ 的概率，随机替换掉抽样数组中的某个元素

为什么这是正确的呢？

我们直接来分析每个元素被抽到的概率（不妨假设总行数 $t$ 大于等于 $s$）

第 $n \ (n < s)$ 行最终抽到的概率为

$\begin{aligned}
& \prod_{m = s +1}^{t} \left[ (1 - \frac{s}{m}) + \frac{s}{m}  \left(1 - \frac{1}{s} \right) \right]
\\ = & \prod_{m = s +1}^{t} \frac{m - 1}{m}
\\ = & \frac{s}{s+1} \frac{s+1}{s+2} \cdots \frac{t-1}{t}
\\ = & \frac{s}{t}
\end{aligned}$

第 $n \ (n \ge s)$ 行最终抽到的概率为

$\begin{aligned}
& \frac{s}{n} \prod_{m = n +1}^{t} \left[ (1 - \frac{s}{m}) + \frac{s}{m}  \left(1 - \frac{1}{s} \right) \right]
\\ = & \frac{s}{n} \prod_{m = n +1}^{t} \frac{m - 1}{m}
\\ = & \frac{s}{n} \frac{n}{n+1} \frac{n+1}{n+2} \cdots \frac{t-1}{t}
\\ = & \frac{s}{t}
\end{aligned}$