Fisher–Yates · reservoir

均匀随机抽样：洗牌与蓄水池

数一批对象有多少个，与在其中等概率取一个，是同一个问题的两面。前者给出 $n!$ 、 $C(n, k)$ 这些计数，后者要求每个对象出现的概率都精确等于计数的倒数。洗牌是最小的例子： $n$ 张牌的排列有 $n!$ 种，正确的洗牌算法必须让每种排列的概率都是 $1/n!$ ，一种都不能多、一种都不能少。

1 · 洗牌算法与选择序列的双射

Fisher–Yates 洗牌（Fisher–Yates shuffle）从后往前扫：对 $i = n-1, n-2, \dots, 1$ ，在 $[0, i]$ 里取一个随机下标 $j$ ，交换第 $i$ 位与第 $j$ 位。

均匀性不必逐个排列去算概率，数一数算法自己有多少种走法就够了。它读入 $n-1$ 个随机数，第 $i$ 步的取值范围有 $i+1$ 个，选择序列共 $n \cdot (n-1) \cdots 2 = n!$ 条。每条序列跑出一个排列，且不同序列跑出的排列必不相同：末位上的元素由第一步唯一决定，倒数第二位由第二步唯一决定，逐位反推即可从结果恢复出整条序列。于是这是 $n!$ 条序列到 $n!$ 个排列的双射（见双射与双计数）。既然每条序列等概率，每个排列也就等概率。

这条论证把随机性问题化归成了计数问题，用的还是排列 P(n, k) 那一套： $n$ 个位置逐格收缩相乘。区别只在于，排列的枚举要逐个列出全部 $n!$ 个排列，而洗牌只在其中取一个。

2 · 每步与全体交换的偏差

nⁿ 条选择序列摊不平 n! 个排列

有一种写起来更顺手的版本：对 $i = 0, 1, \dots, n-1$ ，在整个 $[0, n-1]$ 里取随机下标 $j$ 并交换。它的选择序列有 $n^n$ 条。若各排列等概率， $n^n$ 必须被 $n!$ 整除，而 $n \ge 3$ 时这不可能。 $n$ 为奇素数时 $n^n$ 是奇数、 $n!$ 是偶数； $n$ 为合数时取伯特兰素数 $p \in (n/2, n)$ ，它整除 $n!$ ，却大于 $n$ 的任何素因子，故不整除 $n^n$ 。整除性一旦失败， $n^n$ 条等概率序列就摊不成 $n!$ 份相等的概率。

偏差有多大可以直接穷举。 $n = 4$ 时把 $256$ 条序列逐条跑完：排列 $1032$ 占 $15/256 \approx 5.86\%$ ，排列 $3012$ 只占 $8/256 = 3.125\%$ ，而理想值是 $1/24 \approx 4.17\%$ ，最高与最低相差 $1.875$ 倍。固定种子 $12345$ 、 $n = 4$ 、 $24$ 万次实测与之吻合： $1032$ 出现 $13985$ 次（理想值的 $1.40$ 倍）， $3012$ 出现 $7595$ 次（ $0.76$ 倍），拟合优度 $\chi^2 = 7195$ ；同一组种子下 Fisher–Yates 的 $\chi^2 = 24.3$ ，与自由度 $23$ 相称。

图 2-1 · 两种洗牌在同一组种子下的排列频次对照。可调

n

与试验次数观察两排柱状图相对参考线的偏离，虚线是

1/n!

对应的理想频次，开启叠加后错误版本每根柱上的横杠是穷举全部选择序列得到的精确期望。

警示 · 流传较广的说法是错误版本「偏向恒等排列」，穷举给出的却是相反的结果。恒等排列的占比在 $n = 3, 4, 5$ 分别为理想值的 $0.889$ 、 $0.938$ 、 $0.998$ 倍，一直低于理想值，到 $n = 6$ 才升到 $1.173$ 倍。被压得最狠的始终是轮转 $(n-1, 0, 1, \dots, n-2)$ ：命中它的选择序列数在 $n = 3$ 到 $7$ 依次为 $4, 8, 16, 32, 64$ ，即 $2^{n-1}$ 。这条式子本页没有找到文献出处，只做到穷举验证 $n \le 7$ 。

3 · 随机的 k 子集

取一个大小为 $k$ 的随机子集，不必洗完整副。部分洗牌只跑前 $k$ 步，第 $i$ 步在 $[i, n-1]$ 里取一位换到第 $i$ 位，取完前 $k$ 位即止，时间是 $O(k)$ ；把被换走的位置记在一张稀疏表里，空间也是 $O(k)$ ，不必先物化长度 $n$ 的数组。

另一条路更短： $k$ 子集共 $C(n, k)$ 个，取一个 $[0, C(n, k))$ 内的随机整数，再把它解码成对应的子集即可，见组合对象的编号。两者的代价不同——部分洗牌只做 $k$ 次交换，解码要算 $O(nk)$ 个组合数，但后者只消耗一个随机数，在随机数昂贵或需要按编号复现某次抽样时更合用。

4 · 蓄水池抽样

第 i 个元素以 k/i 的概率入池

数据流的长度事先未知，甚至大到装不进内存，此时无法先数出总数再抽。蓄水池抽样（reservoir sampling）只扫一遍：前 $k$ 个元素直接进池；此后第 $i$ 个元素以 $k/i$ 的概率进池，进池时随机踢掉池中的一个。

定理 4.1 处理完流中前 $i$ 个元素后，这 $i$ 个元素中的每一个留在池中的概率都是 $k/i$ （ $i \ge k$ ）。

证明对 $i$ 归纳。 $i = k$ 时全部入池，概率为 $1$ 。设结论对 $i$ 成立，考察第 $i+1$ 个元素到达后的池。新元素入池的概率按算法就是 $k/(i+1)$ 。对任一旧元素，它此刻在池中当且仅当此前在池中，且没有在这一步被踢出。此前在池中的概率是 $k/i$ ；这一步被踢出，要求新元素入池（概率 $k/(i+1)$ ）且踢中的恰是它（概率 $1/k$ ），合为 $1/(i+1)$ 。两事件独立于旧元素的身份，故它留下的概率为

\frac{k}{i} \left(1 - \frac{1}{i+1}\right) = \frac{k}{i} \cdot \frac{i}{i+1} = \frac{k}{i+1}

与新元素一致，归纳成立。∎

结论对流的每个前缀都成立，因此在流的任何一个位置中断，池中都是一份合格的均匀样本。这一点是蓄水池抽样与部分洗牌的实质差别：后者要先知道 $n$ 。

图 4-1 · 流中各位置的元素最终留在池里的频次。可调流长

N

与池大小

k

观察首尾位置有无系统性偏差，虚线是

k/N

对应的理想频次。

5 · 参考文献

Fisher–Yates shuffle. Wikipedia. 洗牌算法的现代形式、复杂度与常见错误变体。https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
Reservoir sampling. Wikipedia. 流式等概率抽样与 Algorithm R 的描述。https://en.wikipedia.org/wiki/Reservoir_sampling
Vitter, J. S. (1985). Random sampling with a reservoir. ACM Transactions on Mathematical Software, 11(1), 37–57.