消除模偏差：如何在arc4random_uniform（）函数中实现？
模数偏差是在天真地使用模运算来获得小于给定“上限”的伪随机数时出现的问题。
因此，作为C程序员，我使用arc4random_uniform()函数的修改版本来生成均匀分布的伪随机数。
问题是我不明白这个函数是如何工作的，数学上。
这是函数的解释性注释，后跟完整源代码的链接：
/* * Calculate a uniformly distributed random number less than upper_bound * avoiding "modulo bias". * * Uniformity is achieved by generating new random numbers until the one * returned is outside the range [0, 2**32 % upper_bound). This * guarantees the selected random number will be inside * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) * after reduction modulo upper_bound. */
http://cvsweb.openbsd.org/cgi-bin/cvsweb/src/lib/libc/crypt/arc4random_uniform.c?rev=1.1&content-type=text/x-cvsweb-markup
从上面的评论我们可以定义：
-
[2^32 % upper_bound, 2^32)– 区间A. -
[0, upper_bound)– 区间B
为了工作，该函数依赖于区间A映射到区间B的事实。
我的问题是：在数学上，为什么区间A中的数字统一映射到区间B中的数字？ 这有证据吗？
有时，从一个容易理解的例子开始，然后从那里进行推广是有帮助的。 为了简单arc4random ，让我们假设arc4random返回一个uint8_t而不是uint32_t ，因此arc4random的输出是区间[0,256)中的一个数字。 让我们选择7的upper_bound 。
请注意，7不会均匀分为256
256 = 7 * 36 + 4
这意味着天真地使用模运算来获得小于7的伪随机数将导致以下概率分布
37/256 for outcomes 0,1,2,3 36/256 for outcomes 4,5,6
这就是所谓的模偏差，结果0,1,2,3比结果4,5,6更可能。
为了避免模偏差，我们可以简单地拒绝值252,253,254,255，并生成一个新数字，直到结果在区间[0,252) 。 区间[0,252)中的所有数字具有相等的概率（拒绝较高的数字不会影响较低数字的分布）。 并且由于7均匀分为252，因此得到的概率分布是均匀的
36/252 for outcomes 0,1,2,3,4,5,6,7
这基本上是arc4random_uniform所做的，除了arc4random_uniform拒绝范围底部的数字。 具体来说，区间A就是
[2^8 % 7, 2^8) which is [4, 256)
在区间[4,256]中生成一个数字（称之为N ）之后，最终的计算是
outcome = N % 7
在区间[4,256]中有252个数字，并且由于252是7的倍数，所以区间[0,7]上的每个结果具有相等的概率。
这就是arc4random_uniform的工作方式，它拒绝/重试一小部分数字，剩余范围内的数字计数是upper_bound的倍数。 （由于upper_bound与2 ^ 32相比通常是一个较小的数字，因此对单个结果进行多次重试的几率非常小。）
但你真的关心模偏？ 在大多数情况下，答案是“不”。 考虑我们的示例，其上限为7.天真模数实现的概率分布是
613566757 / 4294967296 for outcomes 0,1,2,3 613566756 / 4294967296 for outcomes 4,5,6
这是一个小于0.0000002％的模偏差。
因此，您可以选择：在重试时花费极少的时间来获得完美的分布，或者在概率分布中接受微小的错误以避免重试。