logo标签列表

如何在不浪费比特的情况下，从随机位流中生成一个在[0，n]范围内的随机整数？

random
13

我有一串（均匀）随机比特流，想要生成在区间[0,n]内均匀分布的随机整数，同时尽量节省比特。 （假设总能使用不超过floor(log_2(n))+1个比特，那么多余的比特视为浪费）例如，如果n = 5，则我要寻找的算法应该使用不超过3个比特。如何实现？

1
你确定这可以做到吗？ - Snowbear
我既没有证明它是可能的，也没有证明它是不可能的。如果 ceil(log_2(n)) 位不是最小上界，那么仍然存在其他比特数的上界；无论最小值是多少，我都不想超过它。 - uckelman
2
如果 n 不是2的幂，则我怀疑使用固定位数的情况下获得均匀分布是不可能的。可能存在可以更快地（使用更少的位）到达目标的算法，但我怀疑是否能找到一种能够使用固定位数完成此任务的算法。 - Snowbear
1
我的直觉是，对于非2的幂次方的n，在二进制计算机上根本无法满足均匀性要求，尽管我认为你可以通过使用更多的位数来获得任意小的误差。 - uckelman
如果您真的想使用固定数量的位，则可以考虑最小化均匀性误差。 - Snowbear
难道不应该是 floor(log_2(n)) + 1 吗？ - John Cromartie
5个回答
13
让我来谈谈随机整数生成算法，这些算法在平均使用的随机位数方面是“最优”的。在本文的其余部分中，我们将假设有一个“真正的”随机生成器，它可以产生无偏和独立的随机位。
1976年，D.E. Knuth和A.C. Yao证明了任何使用随机位生成具有给定概率的随机整数的算法都可以表示为二叉树，其中随机位指示遍历树的方式，每个叶子（端点）对应一个结果。（Knuth和Yao，“The complexity of nonuniform random number generation”，收录于《Algorithms and Complexity》，1976年。）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年的Math Forum中给出的算法。另一方面，所有M. O'Neill调查的算法都不是最优的，因为它们依赖于一次生成多个随机位块。请参阅我的有关integer generating algorithms的说明。
以下是快速掷骰子的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
    }
 }
}

以下版本返回一个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)
    }
 }
}

减少位数浪费

回想一下，“最优”的整数生成器（例如上面的快速掷骰子）平均使用至少log2(n)位（下限），或者平均接近这个下限的2位。有各种技术可以用来使算法（即使是不太优化的算法）更接近这个理论下限，包括批处理和随机抽取。这些在以下文献中讨论：

3

这相当于在两个不同（有限）基数集之间找到一个双向函数，这是不可能的。

是的，这个想法是我骑自行车回家时想到的。现在我感觉有点傻。 - uckelman
2
尽管您的问题描述指定了每个随机数生成的固定位数，但标题没有。因此，在此我要补充一点：平均而言，您可以生成一个随机数，其位数为您指定的位数加上半个位。下面的算法对于不可被2整除的n值需要可变数量的位数，但它将消耗的平均位数是floor(log_2(n)) + 1.5。
在范围内生成整数的函数的标准实现使用大型随机数的%（模）运算。这会浪费位并且不会产生数学上精确的随机分布，除非它针对某些大型随机数的值重新运行。以下算法生成真正的随机分布，并且不会浪费位。（或者说我没有看到减少它消耗的位数的明显方法。也许可以从“数字过大”的情况中恢复一些熵。）
# Generate a number from 0 to n inclusive without wasting bits.
function RandomInteger(n)
    if n <= 0
        error
    else
        i = Floor(Log2(n))
        x = i
        r = 0
        while x >= 0
            r = r + (2 ^ x) * NextRandomBit()
            if r > n 
                # Selected number too large so begin again.
                x = i 
                r = 0
            else
                # Still in range. Calculate the next bit.
                x = x - 1
        return r

上述算法是为了清晰易懂而编写的，而不是追求速度。如果重写以同时处理多个位，则速度将非常快。

如果我理解正确的话，当你生成一个r > n时，你就重新开始了。这让我不清楚你如何得出平均比特消耗量，因为有限次重启每次都有非零概率。这是否是一个收敛序列，以便你可以对其求和？ - uckelman
@uckelman 如果我们将n转换为二进制数，它将具有Floor(Log2(n))+1个位和最高位将为1。我们的第一个随机位不能生成太大的数字。如果第一个随机位是0，则随后的任何随机位序列都不会太大。因此，第一位有50％的概率使任何位都不被浪费。如果第一个随机位是1，我们需要检查下一个位。然后有50％的几率从n中取出下一个位为1，因为我们正在计算所有n的值，再次给出50％的概率不浪费任何位。就像这样。 - soid
0
似乎你可以每次取x=ceil(log_2(n))位，将其作为随机数。但是你会遇到一个问题，如果你收到的数字大于你的限制（例如5），那么你需要进行一些操作使它小于5，但是仍然均匀分布。在这种情况下，最合理的做法是再取x位，但由于你已经规定不能浪费位数，所以我们需要更有创意。我建议使用右旋或左旋，但这并不总能让你摆脱困境（考虑当你想要n=5时，字符串为111的情况）。我们可以进行多达x次旋转，看看是否有一个旋转可以让我们进入正确的范围，或者我们可以翻转所有位并加1（二进制补码）。我相信这样可以使它均匀分布。
例如，如果你有以下字符串（最右边的位是你收到的第一个位）：
101001111010010101
并且你使用n=5，则ceil(log2(n)) = 3，因此你将每次使用三位，并且以下是你的结果（每个时间步骤）：
t=0 : 101 = 5
t=1: 010 = 2
t=2: 010 = 2
t=3: 111 = 7 -> too large, rotates won't work, so we use 2's complement: 001 = 1
t=4: 001 = 1
t=5: 101 = 5
1
这不符合一致性要求：对于 n = 5，p(1) = 1/4，而应该是 1/6。 - uckelman
0

首先确定您想要生成的可能值的数量。对于范围在0..5之间的整数，这是6个值。它们可以用ceil(log(6)/log(2))位表示。

// in C++
std::bitset< 3 > bits;
// fill the bitset

// interpret as a number
long value = bits.to_ulong();

然后找到从n位到最终表示格式的转换：它需要从范围[0..2N]缩放到范围[from,to]：

double out_from=-1, out_to=5;
double in_from=0, in_to = std::bitset<3>().flip().to_ulong();

double factor   = (out_to-out_from)/(in_to-in_from)
double constant = out_from - in_from;

double rescaled = in_value * scale + constant;
long out = floor( rescaled );
1
这违反了一致性要求：当n = 5时，p(3) = 1/4，但实际上应该是1/6。 - uckelman
随机化...从来不像看起来那么简单 :( - xtofl
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接