Arc4random模数偏差

Question

根据这个文档,

arc4random_uniform()建议使用结构,arc4random() % upper_bound因为当上限不是2的幂时,它避免了"模偏差".

偏见有多糟糕？例如,如果我生成上限为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 ^ 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 shuffle条目,因为许多扑克网站都学会了正常的线性同余随机生成器和糟糕的改组算法导致不可能或非常可能的套牌或更糟糕的,可预测的套牌的困难方式.