objective-c - Arc4random 模偏

Question

根据此文档，

arc4random_uniform()建议在结构上使用，arc4random() % upper_bound因为当上限不是 2 的幂时，它可以避免“模偏差”。

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

Answer 1

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

现在，偏差是由于使用模创建的多个子区间不完全适合随机输出范围这一事实造成的。为了清楚起见，让我们想象一个随机生成器，它创建从 0 到 198 的数字。您想要从 0 到 99 的数字，因此您计算 random() % 100，得到 0 到 99：

0 % 100 = 0
99 % 100 = 99
100 % 100 = 0
198 % 100 = 98

您会看到 99 是唯一一个只能出现一次的数字，而其他所有数字都可以在一次运行中出现两次。这意味着 99 的概率恰好减半，这也是涉及至少 2 个子区间的偏差中的最坏情况。
由于小于范围间隔的所有 2 的幂都很好地适合 2^32 间隔，因此在这种情况下偏差消失了。

其含义是模数结果集越小，随机输出范围越高，偏差越小。在您的示例中，6 是您的上限（我假设 0 是下限），因此您使用 % 7，导致 0-3 出现 613 566 757 次，而 4-6 出现 613 566 756 次。
所以 0-3 的概率是 613 566 757 / 613 566 756 = 1.0000000016298 倍于 4-6。

虽然似乎很容易忽略，但一些实验（尤其是蒙特卡洛实验）存在缺陷，正是因为这些看似不可思议的微小差异非常重要。

如果期望的输出范围大于随机目标范围，则偏差会更糟。请阅读Fisher-Yates 洗牌条目，因为许多扑克网站都经历了艰难的学习，即正常的线性同余随机发生器和糟糕的洗牌算法会导致不可能或非常可能的牌组，或者更糟糕的是，可预测的牌组。