使用浮点源的整数均匀分布

Question

在 JavaScript 中获取 [0, n) 范围内的随机整数的标准方法 - 或任何其他仅提供 random() 函数返回 [0,1) 范围内浮点数的语言 - 是使用Math.floor(Math.random() * n).

现在，假设我们正在对一组有理数进行运算，那么这背后的数学是微不足道的。问题是：由于 IEEE-754 浮点数的所有复杂性，结果分布实际上真的是均匀的吗？

考虑到一个浮点数和下一个更高的浮点数之间的差距随着它们变大而增加，我认为这应该会引入某种对较小数字的偏见。

Answer 1

不，对于 的大多数值，所得分布不会完全均匀n。对于较小的值，它会非常接近均匀，以至于您很难检测到与均匀分布的任何差异，但随着n数值变大，偏差就会变得明显。

为了说明这一点，这里有一些 Python 代码（抱歉，不是 JavaScript，但原理是相同的）：

from collections import Counter
from random import random

def badrand(n):
    return int(random() * n)

print(Counter(badrand(6755399441055744) % 3 for _ in range(10000000)))

这将在 范围内生成 1000 万个随机整数[0, 6755399441055744)，将每个整数以 3 为模进行减少，并计算余数为 0、1 或 2 的次数。如果我们统一生成这些整数，我们会期望余数modulo 3 大致均匀分布，因此我们预计计数会相似。

这是在我的机器上运行此命令的示例结果：

Counter({1: 3751915, 0: 3334643, 2: 2913442})

也就是说， 的其余部分比 的其余1部分更有可能发生，而 的其余部分又比 的其余部分更有可能发生。这里的差异太大，无法用随机变化来解释。02

那么到底出了什么问题呢？Python 的random()函数基于Mersenne Twister ，质量相对较高，因此我们不太可能看到基本随机数生成器导致的统计问题。发生的情况是生成 2^53（大致）同样可能的结果之一 - 每个结果都是范围 中某个整数random()的形式的数字。现在，在电话会议中，我们正在有效地将这些结果映射到可能的输出。现在这个值不是随机选择的（哈！）；它正好是 2^53 的 3/4。这意味着在尽可能最均匀的分布下，2/3 的可能输出值恰好被 2^53 种可能输出值之一命中，而另外 1/3 则被2^53 种可能输出值中的两个命中输出值。也就是说，某些潜在输出发生的可能性是其他输出的两倍。所以我们距离制服还有很长的路要走。x / 2^53x[0, 2^53)badrand6755399441055744badrandrandom()random()

您将在 JavaScript 中看到相同的效果。对于 Chrome，似乎只有 2^32 个不同的结果，Math.random()因此您应该能够找到类似于上面的n小于（但接近）2^32 的效果。

当然，同样的效果n也适用于小 ：如果n = 5，那么 因为5不是 的约数2^32，所以我们无法在 5 个期望的结果之间完美均匀地分配所有2^32可能的Math.random()结果：我们所能希望的最好结果是 5 个中的 4 个每个结果出现 858993459 个可能random()结果，而第五个出现则出现 858993460 个结果random()。但这种分布将非常接近均匀，几乎不可能找到任何统计测试来告诉你不同的结果。因此，出于实际目的，使用小n.

http://bugs.python.org/issue9025上有一个相关的 Python 错误，您可能会感兴趣。Python 3 通过放弃int(random() * n)计算这些数字的方法解决了这个错误。不过，该错误在 Python 2 中仍然存在。