一尘不染

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

algorithm

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

现在,假设我们要对有理数集进行运算,则其背后的数学运算是微不足道的。问题是:由于IEEE-754浮点数的所有复杂性,最终的分布实际上真的统一吗?

考虑到一个浮点数与下一个更高的浮点数之间的差距会随着它们的变大而增加,我认为这会给较小的数字带来某种偏差。


阅读 333

收藏
2020-07-28

共1个答案

一尘不染

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

为了说明这一点,下面是一些Python代码(不是J​​avaScript,抱歉,但是原理是相同的):

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的次数。如果我们统一生成那些整数,我们期望余数模3大致均匀分布,因此我们希望计数是相似的。

这是在计算机上运行此示例的结果:

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

也就是说,其余1显著 更可能出现比0,这反过来更可能比其余发生是显著2。这里的区别是 方式 太大,通过随机变化来解释。

那么出了什么问题呢?random()基于Mersenne
Twister
,Python的功能质量相对较高,因此我们不太可能看到基本随机数生成器导致的统计问题。发生的事情是random()生成2
^ 53个(大约)同等可能的结果之一-每个结果都是范围内x / 2^53某个整数形式的数字。现在,在电话会议中,我们正在有效地将这些结果映射到可能的输出。现在,该值不是随机选择的(ha!);恰好是2 ^
53的3/4。这意味着,在可能的最均匀分布下,2/53 的可能输出中的正好是2/3的可能的输出值x``[0, 2^53)``badrand``6755399441055744``badrand``random()输出值,而其他1/3被2 ^ 53个可能的输出值中的
两个 击中random()。也就是说,某些潜在产出的发生可能性是其他潜在产出的 两倍 。所以我们距离制服还有很长的路要走。

您将在JavaScript中看到相同的效果。在Chrome中的情况下,似乎只有2 ^
32个不同的结果
Math.random(),所以你应该能够找到与以上类似的效果n比(但接近)2
^ 32小。

当然,同样的效果也适用于小结果n:如果n = 5,则由于5不是除数,2^32所以我们2^32不可能Math.random()在5个所需结果之间完美地平均分配所有可能的结果:我们所希望的最好是5个结果中的4个结果显示为858993459的random()每个可能结果,而第五个random()结果出现在858993460的结果中。但是这种分布将非常接近统一,以至于几乎找不到任何统计检验来告诉您不同的统计检验。因此,出于实际目的,使用small应该很安全n

http://bugs.python.org/issue9025中有一个有趣的Python错误。通过摆脱int(random() * n)计算这些数字的方法,该错误已为Python
3解决。该错误仍然存在于Python 2中。

2020-07-28