4

如果我有一个真正的随机数生成器 (TRNG)，每次调用它时都可以给我一个 0 或 1，然后生成长度等于 2 的幂的范围内的任何数字是微不足道的。对于例如，如果我想生成一个介于 0 和 63 之间的随机数，我只需轮询 TRNG 5 次，最大值为 11111，最小值为 00000。问题是当我想要一个不等于 rangle 中的数字时到 2^n。假设我想模拟掷骰子。我需要一个介于 1 和 6 之间的范围，具有相同的权重。显然，我需要三个位来存储结果，但是轮询 TRNG 3 次会引入两个错误的值。我们可以简单地忽略它们，但这会使骰子的一侧被掷出的几率要低得多。

我对ome的问题最有效地解决了这个问题。

4

4 回答 4

3

获得完全准确结果的最简单方法是拒绝抽样。例如，生成一个从 1 到 8（3 位）的随机值，当你得到 7 或 8 时拒绝并生成一个新值（3 个新位）。在循环中执行此操作。

只需生成大量位，执行 mod 6 并忍受偏差，您就可以任意接近准确。在像 32 位值 mod 6 这样的情况下，偏差会非常小，以至于几乎不可能检测到，即使在模拟了数百万次滚动之后也是如此。

于 2013-08-07T11:27:00.573 回答
2

如果您想要一个 0 .. R - 1 范围内的数字，请至少选择 n 以使 R 小于或等于 2 n。然后使用您的方法在 0 .. 2 n -1范围内生成一个随机数 r 。如果它大于或等于R，则丢弃它并重新生成。您的生成以这种方式失败的概率最多为 1/2，平均不到两次尝试，您将获得所需范围内的数字。这种方法是平衡的，不会以任何方式损害结果的随机性。

于 2013-08-07T12:09:36.713 回答
0

正如您所观察到的，您可以通过连接位将可能的随机值的范围重复加倍通过 2 的幂，但是如果您从整数位（如零）开始，那么您无法获得除素因子以外的任何范围二。

有几种方法；没有一个是理想的：

  1. 只需生成大于您需要的第一个可达范围，如果随机值超出所需范围，则丢弃结果并重新开始。
  2. 产生一个非常大的范围，并在你想要的输出中尽可能均匀地分配它，并忽略你得到的小偏差。
  3. 产生一个非常大的范围，在你想要的输出中均匀地分配你可以的东西，如果你碰到了[按比例]少数几个不在均匀分布的集合之外的值之一，那么丢弃结果并重新开始。
  4. 与 3 一样，但循环使用未转换为结果的值部分。

第一个选项并不总是一个好主意。数字 2 和 3 很常见。如果您的随机位很便宜，那么 3 通常是最快的解决方案，并且经常重复的可能性很小。

最后一个；假设您r在 [0,31] 中构建了一个随机值，并且您需要从中生成结果x[0,5]。[0,29] 中的值r可以使用 mod 6 无任何偏差地映射到所需的输出，而 [30,31] 中的值必须放在地板上以避免偏差。

在前一种情况下，您会产生一个有效的结果x，但还剩下一些随机性——范围 [0,5]、[6,11] 等之间的差异（在这种情况下有五个可能的值）。您可以使用它开始r为您需要生成的下一个随机值构建新的。

在后一种情况下，您不会得到任何东西并且将不得不再试一次，x但您不必丢弃所有. r从非法范围 [30,31] 中选择的特定值是剩余的，可以自由用作下一个r（两个可能的值）的起始值。

从那时起，您拥有的随机范围不必是 2 的幂。这并不意味着它会神奇地达到你当时需要的范围，但它确实意味着你可以尽量减少你扔掉的东西。

你做的越大r，如果溢出，你可能需要扔掉的位越多，但发生这种情况的可能性就越小。添加一位会使您的风险减半，但只会线性增加成本，因此最好使用r您可以处理的最大位。

于 2013-08-07T22:17:23.207 回答
0

让我谈谈在平均使用的随机位数方面“最佳”的随机整数生成算法。在这篇文章的其余部分，我们将假设我们有一个“真正的”随机生成器，它可以产生无偏且独立的随​​机位。

1976 年，DE Knuth 和 AC Yao 表明，任何仅使用随机位以给定概率生成随机整数的算法都可以表示为二叉树，其中随机位指示遍历树和每个叶子（端点）的方式对应一个结果。他们还给出了给定算法执行此任务所需的平均位数的下限。在这种情况下，均匀生成整数的最佳[0, n)算法平均需要最多log2(n) + 2位。在这个意义上，有很多优化算法的例子。其中一个是 J. Lumbroso (2013) 的Fast Dice Roller（在下面实现），另一个可能是数学论坛中给出的算法在 2004 年（另请参阅“用于缩放随机数生成器的位回收”）。另一方面，M. O'Neill 调查的算法都不是最优的，因为它们都依赖于一次生成随机比特块。

然而，任何同样无偏的最优整数生成器通常会在最坏的情况下永远运行，正如 Knuth 和 Yao 所展示的那样。回到二叉树，n 个结果标签中的每一个都留在二叉树中，因此 [0, n) 中的每个整数都可以以 1/n 的概率出现。但是如果 1/n 有一个非终止的二元展开式（如果 n 不是 2 的幂就是这种情况），这棵二叉树必然要么——</p>

  • 具有“无限”深度，或
  • 在树的末端包括“拒绝”叶子，

在任何一种情况下，算法都会在最坏的情况下永远运行，即使它平均使用很少的随机位。（另一方面，当 n 是 2 的幂时，最佳二叉树将具有有限深度且没有拒绝节点。）快速骰子滚轮是使用“拒绝”事件来确保其无偏性的算法示例；请参阅下面代码中的注释。

因此，一般来说，随机整数生成器可以是无偏的或恒定时间的（甚至两者都不是），但不能两者兼而有之。特别是，没有办法在不引入偏差的情况下“修复”不确定运行时间的最坏情况。例如，模减少（例如，Random64Bits() % n) 相当于一棵二叉树，其中拒绝叶被标记的结果替换——但由于可能的结果比拒绝叶多，因此只有一些结果可以代替拒绝叶，从而引入偏差。如果您在一定次数的迭代后停止拒绝，则会产生相同类型的二叉树 - 以及相同类型的偏差。（但是，根据应用程序，这种偏差可能可以忽略不计。随机整数生成也有安全方面的问题，在这个答案中讨论太复杂了。）

快速骰子滚子实施

以下是快速骰子滚轮的 JavaScript 实现。请注意，它使用拒绝事件和循环来确保它是公正的。RandomBit()是一种产生独立无偏随机位的方法（例如，(Math.random() < 0.5 ? 1 : 0)在 JavaScript 中，即使这个习惯用法在它最终依赖的随机位方面不一定有效）。

function randomInt(minInclusive, maxExclusive) {
 var maxInclusive = (maxExclusive - minInclusive) - 1
 var x = 1
 var y = 0
 while(true) {
    x = x * 2
    var randomBit = Math.random()<0.5 ? 1 : 0
    y = y * 2 + randomBit
    if(x > maxInclusive) {
      if (y <= maxInclusive) { return y + minInclusive }
      // Rejection
      x = x - maxInclusive - 1
      y = y - maxInclusive - 1
    }
 }
}

以下版本返回 BigInt，这是最新版本的 JavaScript 支持的任意精度整数：

function randomInt(minInclusive, maxExclusive) {
 minInclusive=BigInt(minInclusive)
 maxExclusive=BigInt(maxExclusive)
 var maxInclusive = (maxExclusive - minInclusive) - BigInt(1)
 var x = BigInt(1)
 var y = BigInt(0)
 while(true) {
    x = x * BigInt(2)
    var randomBit = BigInt(Math.random()<0.5 ? 1 : 0)
    y = y * BigInt(2) + randomBit
    if(x > maxInclusive) {
      if (y <= maxInclusive) { return y + minInclusive }
      // Rejection
      x = x - maxInclusive - BigInt(1)
      y = y - maxInclusive - BigInt(1)
    }
 }
}
于 2020-04-14T23:09:50.483 回答