uck*_*man 6 random integer uniform
我有一个(均匀的)随机位流,我希望在[0,n]范围内统一生成随机整数,而不会浪费比特.(我正在考虑超出楼层(log_2(n))+ 1的比特浪费,假设它总是可以使用不超过它.)例如,如果n = 5,那么算法我是寻找应该使用不超过三位.如何才能做到这一点？
让我谈谈随机整数生成算法，它们在平均使用的随机位数方面是“最佳的”。在这篇文章的其余部分，我们将假设我们有一个“真正的”随机发生器，可以产生无偏和独立的随机位。
1976 年，DE Knuth 和 AC Yao 表明，任何只使用随机位产生具有给定概率的随机整数的算法都可以表示为二叉树，其中随机位指示遍历树的方式和每个叶子（端点）对应一个结果。Knuth 和 Yao 表明，任何用于均匀生成整数的最佳二叉树算法平均[0, n)需要至少log2(n)和最多log2(n) + 2位。（因此，即使是最佳算法也有“浪费”位的机会。）有关最佳算法的示例，请参见下文。
然而，任何同样无偏的最优整数生成器通常会在最坏的情况下永远运行，正如 Knuth 和 Yao 所示。回到二叉树，n 个结果标签中的每一个都在二叉树中离开，因此 [0, n) 中的每个整数都可以以 1/n 的概率出现。但是如果 1/n 有一个不终止的二元展开式（如果 n 不是 2 的幂就是这种情况），这个二叉树必然会——
在任何一种情况下，算法在最坏的情况下都会永远运行，即使它平均使用很少的随机位。（另一方面，当 n 是 2 的幂时，最佳二叉树将没有拒绝节点，并且在返回结果之前正好需要 n 位，因此不会“浪费”任何位。）快速掷骰子是一种使用“拒绝”事件来确保其无偏见的算法示例；请参阅下面代码中的注释。
因此，在一般情况下，一个随机整数发生器可以是任一无偏或恒定时间（或者甚至没有），但不能同时使用。二叉树的概念表明，在不引入偏差的情况下，一般没有办法“修复”不确定运行时间的最坏情况。例如，模数减少（例如，rand() % n) 相当于一个二叉树，其中拒绝叶被标记的结果替换——但是由于可能的结果比拒绝叶多，因此只有一些结果可以代替拒绝叶，从而引入偏差。如果您在一定次数的迭代后停止拒绝，则会产生相同类型的二叉树 - 以及相同类型的偏差。（但是，根据应用程序，这种偏差可能可以忽略不计。随机整数生成也有安全方面的问题，这在本答案中太复杂而无法讨论。）
在前面给出的意义上，有许多最优算法的例子。其中之一是J. Lumbroso (2013)的Fast Dice Roller（在下面实现），也许其他示例是此处其他答案中给出的算法和2004 年数学论坛中给出的算法。另一方面，M. O'Neill 调查的所有算法都不是最优的，因为它们依赖于一次生成随机位块。另请参阅我关于整数生成算法的说明。
以下是 Fast Dice Roller 的 JavaScript 实现。请注意，它使用拒绝事件和循环来确保它是无偏见的。nextBit()是一种产生独立无偏随机位的方法（例如，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 = nextBit()
y = y * 2 + randomBit
if(x > maxInclusive) {
if (y <= maxInclusive) { return y + minInclusive }
// Rejection
x = x - maxInclusive - 1
y = y - maxInclusive - 1
}
}
}
回想一下“最佳”整数生成器，例如上面的 Fast Dice Roller，平均使用至少log2(n)位（下限），或者平均在这个下限的 2 位以内。有多种技术可用于使算法（甚至不是最佳算法）更接近此理论下限，包括批处理和随机性提取。这些讨论在：