理解「为何直接映射 random7() 到 random10() 会导致概率不均」
问题背景
我们需要用 random7()（生成 1-7 均匀分布的随机整数）实现 random10()（生成 1-10 均匀分布的随机整数）。直接通过缩放或取整映射会导致概率不均，本文将详细解释其原因。
直接映射的错误示例
假设尝试直接将 random7() 的结果缩放并取整到 1-10，常见错误代码如下：
def wrong_random10():
x = random7() # x ∈ {1, 2, ..., 7}
return (x - 1) * 10 // 7 + 1 # 错误映射！步骤分解
- 将
x减 1，得到{0, 1, ..., 6}（共 7 个值）。 - 乘以 10，得到
{0, 10, ..., 60}（间隔为 10）。 - 除以 7 并向下取整（
// 7），得到{0, 1, ..., 8}（因为60 // 7 = 8）。 - 加 1 后映射到
{1, 2, ..., 9}，但无法覆盖 10，且概率不均。
概率不均的具体表现
通过具体计算每个 x 对应的映射结果，可以直观看到分布问题：
映射关系表
x（random7() 结果） | (x-1)*10 // 7 | 最终映射 y（(x-1)*10//7 + 1） |
|---|---|---|
| 1 | 0 | 1 |
| 2 | 1 | 2 |
| 3 | 2 | 3 |
| 4 | 4 | 5 |
| 5 | 5 | 6 |
| 6 | 7 | 8 |
| 7 | 8 | 9 |
问题分析
- 缺失的数字：4、7、10 从未出现（概率为 0）。
- 概率不均：1、2、3、5、6、8、9 各对应 1 个
x（概率为 71≈14.29%），而 4、7、10 概率为 0。 - 根本矛盾：7 个输入无法均匀分配到 10 个输出（7÷10=0.7，非整数）。
数学解释：均匀分布的必要条件
要从输入空间 X（大小 m）生成输出空间 Y（大小 n）的均匀分布，需满足：
m≥n且m 是 n 的整数倍（或通过拒绝采样丢弃多余部分）
本例中的矛盾
- 输入空间大小 m=7（
random7()的可能值数量）。 - 输出空间大小 n=10（
random10()的可能值数量）。 - 由于 7<10 且 7 与 10 互质（最大公约数为 1），无法将 7 个输入均匀分配到 10 个输出，必然导致部分输出概率偏高或缺失。
正确方法的简要思路：拒绝采样
为保证均匀性，需扩大输入空间，使其包含足够多的离散值（如 72=49），并拒绝多余部分：
-
调用两次
random7()生成num = (a-1)*7 + (b-1)（范围 0-48，共 49 个值）。 -
仅保留前 40 个值（40=4×10，是 10 的整数倍），映射到 1-10：
if num < 40: return num % 10 + 1 # 每个数字对应 4 个输入，概率 \( \frac{4}{49} \) -
若
num ≥ 40（剩余 9 个值），可复用或重试（进一步优化效率）。
总结
直接映射 random7() 到 random10() 会因输入与输出数量不满足整除关系，导致部分数字概率偏高或缺失。拒绝采样通过扩大输入空间并丢弃多余部分，是保证均匀性的关键方法。