objective-c - Arc4random 模偏置

Question

根据 this documentation ,

arc4random_uniform() is recommended over constructions like arc4random() % upper_bound as it avoids "modulo bias" when the upper bound is not a power of two.

偏差有多严重？例如，如果我生成上限为 6 的随机数，使用 arc4random 和 % 和 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区间，此时偏差消失。

其含义是，取模后的结果集越小，越高 随机输出范围越大，bias越小。在您的示例中，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 shuffle入口 因为许多扑克网站通过艰难的方式学会了正常的线性 全等随机生成器和糟糕的改组算法导致 不可能或非常可能的套牌或更糟的是，可预测的套牌。