提问人：roulette01 提问时间：9/7/2020 最后编辑：Peter O.roulette01 更新时间：11/18/2020 访问量：118
从 U（1,3） 生成 U（1,5） 的最佳方法？
Best way to generate U(1,5) from U(1,3)?
问：
我得到了一个统一的整数随机数生成器 ~ U 3（1,3）（含）。我想使用 U 5 生成整数 ~ U5（1,5）（含）3。最好的方法是什么？
我能想到的最简单的方法是从 U3 中采样两次，然后使用拒绝采样。也就是说，从 U3 采样两次，为我们提供了 9 种可能的组合。我们可以将前 5 个组合分配给 1、2、3、4、5，并拒绝最后 4 个组合。
这种方法期望从 U 3 9/5 * 2 = 18/5 = 3.6 倍进行采样。
另一种方法是从 U 3 中采样 3 次。这为我们提供了 27 种可能组合的样本空间。我们可以利用其中的 25 种组合并拒绝最后 2 种。这种方法预计使用 U 3 27/25 * 3.24 倍。但是这种方法写出来会有点乏味，因为我们的组合比第一种要多得多，但 U3 的预期采样数量比第一种方法要好。
有没有其他更好的方法？
我将其标记为与语言无关，但我主要研究在 Python 或 C++ 中执行此操作。
答：
2赞
Peter O.
9/7/2020
#1
对于范围 [1， 3] 到 [1， 5]，这相当于用 3 面骰子滚动 5 面骰子。
然而，如果不“浪费”随机性（或在最坏的情况下永远运行），这是不可能做到的，因为 5 的所有质因数（即 5）都不会除以 3。因此，最好的办法是使用拒绝抽样来任意接近于没有随机性的“浪费”（例如，通过批处理多卷 3 面骰，直到 3^n “足够接近”5 的幂）。换句话说，您在问题中给出的方法尽可能好。
更一般地说，用p面骰子掷出k面骰子的算法将不可避免地“浪费”随机性（并且在最坏的情况下永远运行），除非“每个素数除以k也除以p”，根据B. Kloeckner的“用骰子模拟骰子”中的引理3。例如：
- 举一个更实际的例子，p 是 2 的幂（任何随机位块都与掷出 2 面幂的骰子相同），而 k 是任意的。在这种情况下，这种“浪费”和无限期的运行时间是不可避免的，除非 k 也是 2 的幂。
- 此结果适用于使用 m 面骰子滚动 n 面骰子的任何情况，其中 n 和 m 是质数。例如，查看 n = 7 和 m = 5 的问题的答案。
另请参阅此问题：将均匀分布的随机数从一个范围转移到另一个范围。
2赞
rossum
9/7/2020
#2
您不需要组合。使用以 3 为基数的算术稍作调整，就不需要表格了。不要直接使用 1..3 结果，而是减去 1 以使其进入 0..2 范围，并将其视为以 3 为基数的数字。对于三个示例，您可以执行如下操作：
function sample3()
result <- 0
result <- result + 9 * (randU3() - 1) // High digit: 9
result <- result + 3 * (randU3() - 1) // Middle digit: 3
result <- result + 1 * (randU3() - 1) // Units digit: 1
return result
end function
这将给你一个 0..26 范围内的数字，如果你加一个，则为 1..27。您可以直接在程序的其余部分使用该数字。
评论
0赞
roulette01
9/7/2020
啊，这似乎是我在第二种方法中提到的，但写得更好。所以从本质上讲，第一个、第二个、第三个样本代表以 3 为底的整数中最高有效到最低有效位？
0赞
Severin Pappadeux
9/9/2020
#3
Peter O. 是对的，你不能逃避失去一些随机性。因此，唯一的选择是对 U（1,3） 的调用成本、代码清晰度、简单性等。
这是我的变体，从 U（1,3） 制作位并将它们组合在一起并拒绝
C/C++（未经测试！
int U13(); // your U(1,3)
int getBit() { // single random bit
return (U13()-1)&1;
}
int U15() {
int r;
for(;;) {
int q = getBit() + 2*getBit() + 4*getBit(); // uniform in [0...8)
if (q < 5) { // need range [0...5)
r = q + 1; // q accepted, make it in [1...5]
break;
}
}
return r;
}
评论