kotlin - 如何使用随机 bool 值生成器生成均匀的随机整数生成器？

Question

我有一个基于硬件的 bool(boolean) 生成器，可以统一生成1或0。如何使用它制作统一的8位整数生成器？我目前正在使用收集的 bool(boolean) 值为8位整数创建二进制字符串。生成的整数不是均匀分布的。遵循this page上解释的分布。具有相同数量的1和0的整数，例如85(01010101)和-86(10101010)，具有最高的机会被生成，并以0的整数(00)生成整数(00) (11111111)的机会最低。

这是我为每个可能的4位整数注释的页面。我们可以看到它们不是统一的。具有相同数目的1和0的3、5、6，-7，-6和-4具有⁶/₁₆概率，而其所有位都相同的0和-1仅具有₁₆/₁₆概率。

。

这是my implementation on Kotlin

Answer 1

根据您的编辑，这里似乎存在误解。通过“统一的4位整数”，您似乎要牢记以下几点:

从0开始。

生成一个随机位。如果为1，则加1，否则减去1。

再重复步骤2 3次。

输出结果数。

尽管随机位生成器可以生成其中每个结果与其他结果可能随机生成的可能性相同的位，并且每个4位块可以与其他结果随机生成的可能性一样大，但是每个块中的位数不是均匀分布。

您想要什么整数范围？假设您要生成4位整数。您是否想要[-4，4]的范围，如问题中的4位随机游走，还是想要[-8，7]的范围，当您处理4-时得到的是位块是二进制补码整数吗？

如果是前者，则随机游走不会生成均匀分布，您将需要以其他方式解决该问题。

在这种情况下，要生成在[-4，4]范围内的统一随机数，请执行以下操作:

取随机位发生器的4位，并在[0，15)中将它们视为整数。

如果整数大于8，请转到步骤1。

从整数中减去4并将其输出。

该算法使用拒绝采样，但是是可变时间的(因此，只要可以在安全攻击中利用时序差异，就不合适了)。同样会生成其他范围内的数字，但是细节太复杂，无法在此答案中进行描述。有关详细信息，请参见我在 random number generation methods上的文章。

根据您显示给我的代码，构建 byte， int和 long的方法很容易出错。例如，构建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并非线程安全的)。

您建议的方法是将 bool(boolean) 生成器的八位组合为一个统一整数，从理论上讲是可行的。但是，实际上存在几个问题:

您没有提到它是哪种硬件。在大多数情况下，除非硬件是为此目的而设计的所谓的真正随机数生成器，否则硬件将不太可能生成统一的随机 bool(boolean) 位。例如，硬件可能会生成均匀分布的位，但具有周期性的行为。

熵表示与理想随机值相比，预测生成器生成的值有多困难。例如，具有32位熵的64位数据块与理想的随机32位数据块一样难以预测。表征硬件设备的熵(或产生不可预测值的能力)绝非易事。除其他事项外，这涉及熵测试，该熵测试必须在适合于硬件的整个操作条件范围内(例如，温度，电压)进行。

大多数硬件无法生成统一的随机值，因此通常需要执行一个附加步骤，即随机性提取，熵提取，无偏，白化或去偏斜，以将硬件生成的值转换为均匀分布的随机数。但是，如果首先表征硬件的熵，则效果最好(请参阅上一点)。

最后，您仍然必须测试整个过程是否提供了出于您的目的“足够随机”的数字。有几种统计测试试图这样做，例如NIST的统计测试套件或TestU01。

有关更多信息，请参见“ Nondeterministic Sources and Seed Generation”。

编辑完此页面后，看来您正在以错误的方式解决该问题。要产生统一的随机数，您无需添加均匀分布的随机位(例如 bit() + bit() + bit())，而是将它们连接起来(例如 (bit() << 2) | (bit() << 1) | bit())。但是，由于我上面提到的原因，这再次在理论上有效，但在实践中无效。