Arc4random模偏

Question

据this documentation称，

arc4random_uniform()比arc4random() % upper_bound这样的构造更可取，因为它避免了当上界不是二次方时的“模偏”。

偏见有多严重？例如，如果生成上界为6的随机数，那么使用arc4random与%和arc4random_uniform()有什么区别？

Answer 1

arc4random()返回一个无符号的32位整数，这意味着值介于0到2^32-1 =4 294 967 295之间。

现在，偏差的产生是因为用模创建的多个子区间不完全符合随机输出范围。为了清晰起见，让我们设想一个随机生成器，它创建从0到198包含的数字。您需要从0到99之间的数字，因此可以计算出随机()% 100，得到0到99：

0% 100 =0

99 % 100 = 99

100 % 100 =0

198 % 100 = 98

您可以看到，99是唯一只能发生一次的数字，而所有其他的数字都可以在一次运行中发生两次。这意味着99的概率被精确地减半，这也是在至少有2个子区间的偏倚中最坏的情况。

当所有两个小于范围间隔的幂都与2^32间隔很好地吻合时，偏置在这种情况下消失了。

结果表明，模的结果集越小，随机输出范围越大，偏差越小。在您的示例中，6是您的上限(我假设0是下限)，所以您使用% 7，结果是0-3发生613 566 757次，而4-6发生613 566 756次。

所以0-3是613,566,757 / 613,566,756 = 4-6的1.0000000016298倍.

虽然这似乎很容易被忽视，但有些实验(特别是蒙特卡罗实验)却有缺陷，因为这些看似不可思议的微小差异非常重要。

更糟糕的是，如果期望的输出范围大于随机目标范围，则偏差更大。请阅读Fisher-Yates shuffle条目，因为许多扑克网站都很难理解正常的线性同余随机生成器和糟糕的洗牌算法导致不可能的或非常可能的甲板或更糟的、可预测的甲板。