抽样方法

• 先把 $S$ 中前 $s$ 个元素加入到抽样结果 $R$ 中
• 若元素 $S_j$ 到达，且满足 $j > s$ ，此时 $S_j$ 存在 $\frac{s}{j}$ 的概览替换 $R$ 中任一随机选定的元素
• 当 $j = n$ 时，返回抽样结果 $R$

合理性证明

情况1： $s=1$ 时，当遍历了 $n$ 个元素时，应满足每个元素位于 $R$ 中的概率为 $\frac{1}{n}$

当 $j=1$ 时，样品 $S_1$ 存在于 $R$ 的概率为 $p_1= 1$ ；

当 $j=2$ 时，样品 $S_2$ 可以随机替换掉 $S_1$ 的概览为 $p_2 = \frac{s}{j} = \frac{1}{2}$ ，则 $S_1$ 存在于 $R$ 的概率为 $1 - p_2 = \frac{1}{2}$；

当 $j = 3$ 时，样品 $S_3$ 可以随机替换 $S_1$ 或 $S_2$ 的概率为 $p_3 = \frac{s}{j} = \frac{1}{3}$, 则 $S_1$ 与 $S_2$ 依然存在于 $R$ 的概率为 $\frac{1}{2} \times (1-p_3) = \frac{1}{3}$；

…

以此类推，当 $j = n$ 时，样品 $S_n$ 可以随机替换 $S_1, S_2, … , S_{n-1}$ 的概率为：$p_n= \frac{s}{j} = \frac{1}{n}$ ，则 $S_1, S_2, … , S_{n-1}$ 依然存在于 $R$ 的概率为：

$$
\frac{1}{n-1} \times (1 - \frac{1}{n}) = \frac{1}{n}
$$

显然，当 $s=1$ 时，则每个元素位于 $R$ 中的概率为 $\frac{1}{n}$，要求成立

情况2: $s > 1$ 时，当遍历了 $n$ 个元素时，应满足每个元素位于 $R$ 中的概率为 $\frac{s}{n}$

当 $j \geq 1$ 且 $j \leq s$ 时，样品 $S_j$ 会无条件进入 $R$，此时 $S_j$ 存在于 $R$ 的概率为 $p_1 = p_2 = … = p_s= 1$ ；

当 $j = s + 1$ 时，样品 $S_j$ 可以可以随机替换掉 $S_1, S_2, … , S_s$ 的概率为：$p_j= \frac{s}{j} = \frac{s}{s+1}$，此时 $S_1, S_2, … , S_s$ 依然存在于 $R$ 的概率为 :

$$
(1-p_j) + p_j(1- \frac{1}{s}) = \frac{1}{s+1} + \frac{s}{s+1} \times \frac{s-1}{s} = \frac{s}{s+1}
$$

当 $j = s + 2$ 时，样品 $S_j$ 可以随机替换掉 $S_1, S_2, … , S_{s+1}$ 的概率为：$p_{j}= \frac{s}{j} = \frac{s}{s+2}$，此时 $S_1, S_2, … , S_{j-1}$ 依然存在于 $R$ 的概率为:

$$
p^{\prime}_j = p^{\prime}_{j-1} [ (1-p_j) + p_j(1- \frac{1}{s})] = \frac{s}{s+1} \times [\frac{2}{s+2} + \frac{s}{s+2} \times \frac{s-1}{s}] = \frac{s}{s+2}
$$

以此类推，对于任意 $k > s + 1$, 样品 $S_j$ 可以随机替换掉 $S_1, S_2, … , S_{k-1}$ 的概率为：$p_{k}= \frac{s}{k}$ , 此时 $S_1, S_2, … , S_{k-1}$ 依然存在于 $R$ 的概率为：

$$
p^{\prime}_k = p^{\prime}_{k-1}[(1-p_k) + p_k(1-\frac{1}{s})] = \frac{s}{k-1} \times [\frac{k-s}{k} + \frac{s}{k} \times \frac{s-1}{s}] = \frac{s}{k}
$$

若 $k = n$，则每个元素位于 $R$ 中的概率为 $\frac{s}{n}$，要求成立