如何从随机布尔值生成器生成均匀分布的随机整数生成器?

3
我有一个基于硬件的布尔生成器,可以均匀地生成1或0。如何利用它制作均匀的8位整数生成器?我目前正在使用收集到的布尔值来创建8位整数的二进制字符串。生成的整数不是均匀分布的。它们遵循此页面所解释的分布。具有相同数量的1和0(例如85(01010101)和-86(10101010))的整数具有最高的生成概率,而具有大量重复位(例如0(00000000)和-1(11111111))的整数具有最低的生成概率。
这是我注释了每个可能的4位整数的概率的页面。我们可以看到它们不是均匀的。具有相同数量的1和0(如3、5、6、-7、-6和-4)的整数具有⁶/₁₆的概率,而所有位都相同的0和-1只有¹/₁₆的概率。
这里是我的Kotlin实现。 (点击此处查看)

我建议您将该信息编辑到您的问题中。好问题。 - jonspaceharper
如果您的位源存在偏差,那么您需要考虑一种去偏技术。RFC 4086提供了一些建议。冯·诺伊曼技术(请参见RFC的第4.2节)很简单,但也有其他技术。在某种程度上,您必须将去偏技术适应于您的位源的特定偏差。 - rossum
这是一个有趣的问题,但描述仍不清楚。您应该明确说明如何从位构造整数。您还应该具体说明生成的整数的分布 - 链接页面上有很多内容,因此不能指望其他人尝试弄清您可能正在谈论的几件事情中的哪一件。 - Robert Dodier
为什么得到01010101的概率比得到00000000的概率高?这对我来说毫无意义。 - Martin Wickman
@MartinWickman,01010101和00000000的概率相等。然而,在八个位中得到四个1的概率比得到零个1的概率更大。 - pjs
显示剩余4条评论
1个回答

2
根据您的编辑,这里似乎存在一个误解。通过“统一的4位整数”,您似乎想到了以下内容:
  1. 从0开始。
  2. 生成一个随机位。如果是1,则加1,否则减1。
  3. 重复第2步三次。
  4. 输出结果数字。
尽管随机位生成器可能会生成每个结果都有同样可能性的位,每个4位块也可能像任何其他块一样具有同样的可能性来进行随机生成,但每个块中的位数并不是均匀分布的。
您需要什么范围的整数?假设您正在生成4位整数。您是否希望获得[-4, 4]的范围,就像问题中的4位随机游走一样,还是希望获得[-8, 7]的范围,这是当您将4位比特块视为二进制补码整数时所得到的?
如果是前者,则随机游走不会生成均匀分布,并且您需要以不同的方式解决该问题。
在这种情况下,要在范围[-4, 4]内生成均匀分布的随机数,请执行以下操作:
  1. 获取随机比特发生器的4位,并将其视为[0,15)中的整数;
  2. 如果整数大于8,请执行步骤1。
  3. 从整数中减去4并输出它。
此算法使用拒绝抽样,但是是可变时间的(因此不适用于任何可以利用安全攻击中的时间差异的情况)。其他范围的数字也是以类似的方式生成的,但详细信息过于复杂,无法在此答案中描述。请参阅我的文章随机数生成方法了解详情。
根据您向我展示的代码,您构建byteintlong的方法容易出错。例如,构建8位字节以实现您想要的结果的更好方法如下所示(请记住,我对Kotlin不是很熟悉,因此语法可能有误):
val i = 0
val b = 0
for (i = 0; i < 8; i++) {
   b = b << 1; // Shift old bits
   if (bitStringBuilder[i] == '1') {
      b = b | 1; // Set new bit
   } else {
      b = b | 0; // Don't set new bit
   }
}
value = (b as byte) as T

此外,如果MediatorLiveData不是线程安全的,那么使用StringBuilder收集位的方法也不是线程安全的(特别是因为StringBuilder不是线程安全的)。
您建议的方法,将布尔发生器的八个位组合成一个统一的整数,在理论上是可行的。但是,在实践中存在几个问题:
  • 您没有提到它是什么类型的硬件。在大多数情况下,除非硬件是所谓的真随机数生成器,否则硬件不太可能生成均匀的随机布尔位。例如,硬件可能会生成均匀分布的位,但具有周期性行为。
  • 熵表示预测生成器产生的值相对于理想随机值有多难。例如,具有32位熵的64位数据块与理想随机32位数据块一样难以预测。表征硬件设备的熵(或产生不可预测值的能力)远非易事。除其他事项外,这涉及必须在适用于硬件的操作条件的全部范围内进行的熵测试(例如,温度、电压)。
  • 大多数硬件不能产生均匀的随机值,因此通常需要执行额外的步骤,称为随机性提取、熵提取、去偏、白化或去斜,将硬件生成的值转换为均匀分布的随机数。但是,如果先表征硬件的熵(请参见上一个问题),则效果最佳。
  • 最后,您仍然需要测试整个过程是否为您的目的提供了“足够随机”的数字。有几种统计测试试图这样做,例如NIST的统计测试套件或TestU01。

更多信息,请参见“非确定性来源和种子生成”。


在您编辑此页面之后,似乎您正在错误的方法解决问题。要生成均匀的随机数,您不应该添加均匀分布的随机位(例如,bit() + bit() + bit()),而应该连接它们(例如,(bit() << 2) | (bit() << 1) | bit())。但是,同样地,由于我上述提到的原因,这在实践中并不可行。


是的,我将位拼接在一起而不是相加。随机性来自于手机相机上一个像素的 shot noise,因此从技术上讲它是量子 RNG。它的香农熵为0.99916596。它还通过了所有114个 dieharder 测试。其中一个被认为是弱的。我不确定我的方法是否足够好,因为有些数字生成的频率比其他数字高。如果我生成标准的32位整数,0和1永远不会被生成,因为我的布尔生成器永远不会重复生成同一个位32次。你建议使用什么样的无偏方法? - Andika Wasisto
1
为了生成随机数,最小熵比香农熵更合适。此外,有许多去偏差的技术可用:von Neumann、HMAC-SHA512和其他技术。(例如,Cliff/Boyd/Gonzalez在2009年对HMAC作为随机性提取器进行了评估。)还要注意,尽管底层的比特生成器可能是均匀的,但从该生成器得到的随机游走分布远非均匀。 - Peter O.
另一方面,正如您所希望的那样,“均匀随机游走”也被称为“白噪声”。对于这种类型的游走,只需从随机位生成器中获取8位块,并将每个块视为8位整数的二进制补码形式即可。 - Peter O.
我不对比特进行加/减运算。 我将它们连接起来,它们不是均匀的。 当具有相同数量的1和0的整数具有更高的概率时,它们怎么可能是均匀的? 这是我使用Kotlin的实现:https://gist.github.com/awasisto/ea60b86bf0c619bfe689a461e0fd7f1f#file-rng-kt-L49-L75 - Andika Wasisto
我的代码和你的代码返回相同的输出,但是你的代码在生成字节时需要更多的转换,因为JVM语言不能对byte进行位运算。我认为生成的数字不太均匀也没关系,因为在大多数情况下,我们只需要生成有界的数字。 - Andika Wasisto
显示剩余8条评论

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接