随机数生成器的NextBytes方法是否存在偏差？

Question

根据.NET参考源代码，NextBytes（）方法的实现如下：

for (int i=0; i<buffer.Length; i++)
{
    buffer[i]=(byte)(InternalSample()%(Byte.MaxValue+1)); 
}

InternalSample 提供了一个处于 [0，int.MaxValue) 的值，这一点可以从它的文档注释以及 Next() 方法的文档中得到证明，后者被记录为返回该范围，只是直接调用了 InternalSample 方法。

我的担忧是，由于 InternalSample 可以产生 int.MaxValue 种不同的值，并且这个数字不能被 256 整除，因此我们应该在生成的字节中存在一些轻微的偏差，其中一些值（在本例中仅为 255）发生的频率比其他值低。

我的问题是：

1. 这个分析是正确的，还是方法实际上是无偏的？
2. 如果存在偏差，是否足够强大以影响任何真实的应用程序？

提醒：我知道 Random 不应该用于加密目的；我考虑的是它的有效用途（例如模拟）。

- ChaseMedallion

---

嗯，不，这是一种有偏见的分析。该操作仅获取值的低8位。范围为0..int.maxvalue的值有256的整数倍个数，共8388608个。没有偏见，Donald 确保了这一点。 - Hans Passant

@AndrewMorton Random.Next()的文档似乎表明int.MaxValue永远不会被返回。因此，我们有int.MaxValue值，而不是int.MaxValue + 1值，对吗？ - ChaseMedallion

@HansPassant 您的范围是否包括 int.MaxValue 或者不包括？我假设（根据文档和源代码中的注释），InternalSample 不能返回 int.MaxValue。请查看防止此情况发生的两个 if 语句在 InternalSample source 中。 - ChaseMedallion

实际上，我认为 MS 实现中存在可能的偏差，特别是在 InternalSample() 的实现中的这一行代码：if (retVal == MBIG) retVal--;，其中 MBIG 是 int.MaxValue。 - Matthew Watson

@MatthewWatson 我同意那行代码看起来相当可疑，很可能会使 int.MaxValue - 1 出现的概率增加一倍。虽然我不太了解减法生成器，但我不能确定。我在参考实现（第283页）中没有看到那行代码。 - ChaseMedallion

Answer 1

你的分析确实正确。但是这个缺陷只占两十亿分之一的比例，即1/2^31，因此相对较小。

人们应该问的问题是，它是否可以被检测到？例如，需要多少样本N才能以99%的置信度确定偏差。根据我所知道的，有N > s^2 z^2 / epsilon^2，其中

• z = 2.58，
• epsilon = 1 / 2^32，和
• s^2 = p - p^2，
• p = 1/2^8 - 1/2^31。

这将需要4.77x10^17个样本，这个数量非常大，因此这个缺陷几乎不可能被发现。

- Samuel Vidal

Answer 2

请参考 Knuth 第二卷 3.2.1.1 节“模数的选择”。实际上，您需要一个不等于 256 的模数；使用 256，结果字节的低 4 位比使用 257（第 12 页）获得的随机性要少得多。

257 也是质数，这有助于减少偏差并延长伪随机序列。

任何伪随机序列都不是真正的随机。对于非加密应用程序来说，什么样的偏差才算是足够小呢？如果有疑问，我的建议是按照应用程序绘制它们的方式对生成的数字进行采样并进行一些统计分析。现成的随机数生成器对许多应用程序来说已经足够好了，但对于您的应用程序来说可能还不够好。

- S. Rojak

---

就“足够公正”而言，我的希望是像 Next() 方法一样，派生的方法（如 NextBytes()）不会增加任何偏差或不均匀性。例如，Java 的 Random 方法 nextInt(bound) 声明，如果随机源的基础完全随机（但它并不是），结果将是完全随机的。 - ChaseMedallion

不完全是文档所说的，如果你要引用一个来源，请确保引用准确。"will"和"would"有很大的区别。 - zaph