rand5() 生成 rand7()：拒绝采样的一行代码

一句话结论（30s）

结论先行：只用 rand5() 也能等概率生成 1~~7，因为把两次 rand5() 组合成 25 种等概率结果后截断到 21（7 的倍数）再模 7，尾部 22~~25 拒绝重试，即可保证严格均匀。本质是拒绝采样——用重复采样（空间）换等概率（精度）。

核心原理（2min）

先放大：5*(rand5()-1)+rand5() 等概率生成 1~~25（5×5=25 种独立等概率组合）。再截断：25 不是 7 的倍数但 21 是，取 1~~21 每 3 个数映射到 rand7 的一个值，22~25 拒绝重试。关键前提是截断只去掉尾部、不改变剩余值的等概率性。拒绝率 4/25=16%，期望约 1.19 次 rand25()（即 2.38 次 rand5()）。小集合无损生成大集合不可能，必须拒绝采样。

底层深入（5-10min）

问题

只有 rand5()（等概率返回 1~~5），如何等概率返回 1~~7？

放大：用 5 进制生成 1~25

rand5() 本身只有 5 种等概率结果，不足以覆盖 7 个值。关键：把两个 rand5() 组合成 25 种等概率结果。

int rand25() {
    return 5 * (rand5() - 1) + rand5();  // 等概率生成 1~25
}

推理：5*(rand5()-1) 等概率取 0/5/10/15/20，rand5() 等概率取 1/2/3/4/5。两者独立，组合有 5×5=25 种等概率结果，覆盖 1~25。

💭 思考：为什么要把两个 rand5() 放大成 25 种，而不是直接用 5 种？——因为 5 < 7，单次 rand5() 连 7 个结果都装不下，更谈不上等概率；只有把 5×5 组合成 25（>7）种等概率结果，才有”截断到 7 的倍数”的腾挪空间。这就是”先放大、再截断”的必要性。

截断：拒绝采样

25 不是 7 的倍数，但 21 是。取 1~~21，每 3 个数映射到 rand7 的 1 个值（1/2/3→1, 4/5/6→2, …），22~~25 拒绝重试：

int rand7() {
    int x;
    do {
        x = 5 * (rand5() - 1) + rand5();  // 1~25 等概率
    } while (x > 21);  // 22~25 拒绝
    return x % 7 + 1;
}

拒绝采样的核心前提：截断后的范围（1~21）中每个值的概率完全相等。 因为 rand25() 保证等概率，截断只是去掉尾部，不改变剩余值的等概率性。

💭 思考：为什么截断到 21，而不是 25 直接模 7？——因为 25 不是 7 的倍数，直接 x % 7 会让 1~7 各值分到的原始结果数不相等（有的 4 个、有的 3 个），分布就不均匀；只有先截到 21（7 的倍数），每个目标值才恰好对应 3 个原始结果。

为什么 rand7 转 rand5 不需要拒绝采样？

int rand5() {
    int x;
    do {
        x = rand7();
    } while (x > 5);
    return x;
}

很简单，因为 7>5，直接拒绝。但如果想让性能更高（拒绝率更低），可以放大到 49（7×7），截断到 45（7 的倍数），拒绝率从 2/7（29%）降到 4/49（8%）。

拒绝采样的效率

rand25() 中 22~25 被拒绝的概率是 4/25 = 16%。每次重试是一个几何分布，期望调用次数为 $1/(1-0.16) \approx 1.19$ 次——平均每次 rand7() 调用约 1.19 次 rand25()，即 2.38 次 rand5()。

精髓

从一个小集合等概率生成大集合 → 没有无损方案，必须拒绝采样。本质是用空间（重复采样）换精度（等概率分布），拒绝采样保证了结果的严格均匀性。

章末提问

追问 1：(rand5() + rand5()) % 7 + 1 为什么不行？

回答思路：结论是不行，因为两个 rand5() 相加不是均匀分布（2~~10 各值概率呈三角分布，中间值概率更高），取模后 1~~7 的概率不相等，无法保证严格均匀。正确做法必须先用乘法组合 5*(rand5()-1)+rand5() 构造 25 种”等概率”结果，再截断。

追问 2：拒绝采样的期望调用次数怎么算？

回答思路：结论是约 1.19 次 rand25()，因为每次成功的概率是 21/25，失败即重试、服从几何分布，期望次数 = 1/(21/25) = 25/21 ≈ 1.19 次，折合约 2.38 次 rand5()。

追问 3：如果改用 rand5() 生成 rand8()，怎么改？

回答思路：结论是放大到 25、截断到 24（8 的倍数），每 3 个原始结果映射到 1 个目标值，25 被拒绝；因为 24 是 ≤25 的最大的 8 的倍数，只有截到 8 的倍数，1~8 每个值才能等概率。

Rand5生成Rand7——拒绝采样的原理与应用