抽样问题
当我们需要从 n 个元素中随机抽取 k 个元素，且 n 非常大，无法将所有数据一次性载入内存。
此时可以采用 Reservior Sampling 算法。
抽样方法
-
读取 $$k$$ 个元素，存入数组 $$R$$。
-
对于 $$x_k$$ 之后的每个元素 $$x_i$$，生成一个随机数 $$j \in [1, i]$$。
a. 如果 $$j \in [1, k]$$，则更新数组中的元素 $$R[j]$$ 为 $$x_i$$。
b. 否则丢弃 $$x_i$$。
归纳证明
-
当 $$n = k$$ 时，所有元素都会被抽取。概率为 $$1 = \frac{k}{n}$$。
-
增加 $$n$$ 至 $$n + 1$$，按照算法 $$x_{n+1}$$ 被抽中的概率为 $$\frac{k}{n + 1}$$。
对于前面的 $$n$$ 个元素，没有加入 $$x_{n+1}$$ 之前，被抽中的概率为 $$\frac{k}{n}$$。
加入 $$x_{n+1}$$ 后，被抽中的概率为 $$\frac{k}{n} \times (1 - \frac{1}{n + 1}) = \frac{k}{n + 1}$$。