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

5
在JavaScript中获取一个在范围[0,n)内的随机整数的标准方法 - 或任何其他只提供返回范围为[0,1)的浮点数的random()函数的语言 - 是使用Math.floor(Math.random() * n)
现在,如果我们在有理数集上操作,那么这背后的数学是微不足道的。问题是:由于IEEE-754浮点数的所有复杂性,结果分布是否真的是均匀的?
考虑到当浮点数变大时,一个浮点数和下一个更高的浮点数之间的距离增加,我认为这应该引入某种偏向较小数字的偏差。

因此,如果您随机选择一些数字,则绝大多数选定的数字将具有相同数量的数字,因为绝大多数可能的值具有相同数量的数字。 - THE AMAZING
所以,生成的分布实际上并不是真正的均匀分布。 - THE AMAZING
如果数字的数量偏向于某个数字,那就意味着存在偏差,也就是不均匀。 - THE AMAZING
1
很不可能完全均匀:在不太离谱的假设下,即 Math.random 以相等概率生成 2^53 个不同结果,我们只能得到对于 n 的精确除数为 2^53 的值的均匀结果。例如,当 n=5 时,如果我们将 2^53 个不同元素分成 5 个箱子,则无论如何放置这些元素,这些箱子都不能拥有相同数量的元素。 - Mark Dickinson
1
另请参阅 http://bugs.python.org/issue23974,了解Python 2中相关问题,当n接近2^53时存在严重偏差。 (该问题已在Python 3中修复。) - Mark Dickinson
显示剩余10条评论
5个回答

4
不,对于大多数值的 n,得到的分布不会完美地均匀。对于小的 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)))

这将在区间[0, 6755399441055744)内生成1000万个随机整数,对每个整数取模3,统计余数为0、1或2的次数。如果我们均匀地生成这些整数,我们期望模3的余数大致均匀分布,因此我们期望计数相似。
以下是在我的机器上运行此操作的示例结果:
Counter({1: 3751915, 0: 3334643, 2: 2913442})

也就是说,余数为1的发生概率比0显著地高,而0的发生概率又比余数为2显著地高。这里的差异远远超出了随机变异的范围。
那么出了什么问题呢?Python的random()函数相对较高质量,基于Mersenne Twister,因此我们不太可能看到基础随机数生成器导致的统计问题。问题在于random()生成2^53(大约)个等可能结果之一 - 每个结果都是某个整数x(范围为[0,2^53))的形式x/2^53的数字。现在,在badrand调用中,我们有效地将这些结果映射到6755399441055744个可能的输出之一。现在,该值不是随机选择的(哈!);它恰好是2^53的3/4。这意味着在最均匀的分布下,2/3的可能的badrand输出值被恰好一个2^53个可能的random()输出值命中,而另外1/3则被两个2^53个可能的random()输出值命中。也就是说,一些潜在的输出是发生的可能性是其他输出的两倍。所以我们离均匀还有很长的路要走。
你会在JavaScript中看到相同的效果。在Chrome的情况下,似乎 Math.random()只有2 ^ 32个不同的结果,因此您应该能够找到像上面那样的效果,其中 n 小于(但接近)2 ^ 32。
当然,对于小的 n 也是如此:如果 n = 5 ,那么因为 5 不是 2 ^ 32 的除数,我们无法完美地均匀分配所有 2 ^ 32 可能的 Math.random()结果之间的5个期望结果:我们所能希望的最好的结果是4个5个结果中的每一个出现在858993459个可能的 random()结果中,而第五个出现在858993460个 random()结果中。但是,该分布将非常接近均匀分布,以至于很难找到任何统计测试来告诉您不同。因此,在实际目的中,使用小的 n 应该是安全的。

这里有一个相关的 Python bug,可能会对您感兴趣,链接为http://bugs.python.org/issue9025。该 bug 在 Python 3 中已通过摒弃使用 int(random() * n) 方法计算这些数字而得到解决。然而,该 bug 在 Python 2 中仍然存在


不需要道歉 - 我觉得 Python 比 JavaScript 或 TypeScript 更有吸引力 - Python 中的“电池包含”部分让我不必考虑这样的问题,因为有一个很好的 random.randInt() 函数(正如我们所看到的并非一定)可以处理它 :-) - Voo

2
如果Math.random(或等效物)生成的是在浮点数范围[0,1)内对应的比特模式之一,则它将产生极度偏倚的样本。在[0.25,0.5)和[0.5,1.0)中有同样数量的可表示浮点数,这也是在[0.125,0.25)中可表示值的数量。依此类推。简而言之,均匀分布的比特模式将导致只有一千个值在0.5和1.0之间。(假设双精度浮点数。)
幸运的是,这不是Math.random所做的。获得均匀分布的一个简单方法(而不是比特模式)是在[1.0,2.0)中生成均匀分布的比特模式,然后减去1.0;这是一个相当常见的策略。
无论如何,Math.floor(Math.random() * n)的最终结果不是完全均匀分布的,除非n是2的幂,因为存在量化偏差。可能由Math.random返回的浮点值的数量是2的幂次方,如果n不是2的幂次方,则不可能将可能的浮点值完全均匀地分布在[0,n)中的所有整数值上。如果Math.random返回双精度浮点数且n不是很大,则此偏差很小,但确实存在。

0
根据http://es5.github.io/x15.8.html#x15.8.2.14,Math.random的功能是返回一个带有正号的数字值,大于或等于0但小于1,使用实现相关算法或策略,随机或伪随机地选择该范围内具有近似均匀分布。此函数不接受任何参数。
看看这篇文章:https://stats.stackexchange.com/questions/40384/fake-uniform-random-numbers-more-evenly-distributed-than-true-uniform-data 这已经超出了我的能力范围,抱歉我没有什么可以贡献的了。

这会产生高斯分布(也称为正态分布)。均匀分布要简单得多:每个数字应该出现的频率相同。 - Voo

0
假设random()返回0..1之间的数字。
如果结果是单精度浮点数,则基于尾数只有23位熵。
如果结果是双精度浮点数,则基于尾数只有52位熵。
因此,当N小于2^24或2^53时,floor(random() * N)将仅均匀地分布。 编辑这里有一些关于浮点数连续最大整数的信息http://www.mathworks.com/help/matlab/ref/flintmax.html

对于双精度浮点数,熵为53位:通常的方法是生成形如x / 2^53的数字,其中x是在[0, 2^53)范围内(大致)均匀分布的整数。是的,如果不考虑隐藏位,尾数只有52位,但您还需要考虑指数。 - Mark Dickinson
@MarkDickinson - 当你发表评论时,我正在编辑并添加最大连续整数参考。 - Louis Ricci
我应该表述得更清楚:确实,在最好的情况下,这只能在双精度可以表示每个数字的情况下工作。我想知道的是,在此之下是否实际上是均匀的。 - Voo

0

我假设你提到“随着浮点数增大,相邻两个浮点数之间的差距也会增大”是基于以下原因:

在IEEE-754中,你有一个固定大小的尾数,它允许在范围[1,2)内均匀生成“随机”值,并且在[2,4)中有相同数量的可能值,这是一个两倍大的范围,因此我们得到了可能值之间的两倍间隔,在[4,8)中再次扩大两倍,以此类推。

现在,我没有检查过技术细节,关于“使用实现相关的算法或策略”时,当他们谈论[0,1)范围内生成的随机数的属性时,但由于上述考虑是如此微不足道,我认为随机生成器程序员已经意识到了这一点,并用“实现相关的算法”来解决了这个问题。

因此,作为一个天真的人,我相信对于(我对)你怀疑的原因,没有什么可担心的。事实上,如果你可以为尾数生成均匀和随机的值,那么设置始终相同的指数,使得值属于[1,2),你从所有值中减去1,并且对于[0,1)有一个适当的分布。


问题是关于在假设[0,1)均匀分布的情况下,应用该变换后[0,n)上的分布是否会是均匀的。 - Voo
是什么让你怀疑“简单”地乘以n会破坏均匀性?当然,四舍五入可能会影响精确的“复制”,但是这种四舍五入也可以预期是相当均匀的,例如,如果n是2的倍数,则整个过程只涉及指数的移位,均匀性将不会受到任何影响。 - Bert te Velde
阅读Mark的答案,了解为什么会发生这种情况,包括显示偏差的代码。如果n是2的倍数,则不会有问题,但在其他情况下会出现问题。这里的洞察力是,这只是一个整数随机生成器,其周期为[0,2^(k+1)),其中k是浮点数的有效位数,并且所有相同的限制都适用。 - Voo

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