c - 消除模偏差 : how is it achieved in the arc4random_uniform() function?

Question

模偏差是天真地使用模运算来获得小于给定“上限”的伪随机数时出现的问题。

因此，作为一名 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 中的数字？有这方面的证据吗？

Answer 1

有时，从一个易于理解的示例开始，然后从那里进行概括会有所帮助。为了简单起见，我们假设 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% 的模偏差。

因此，您可以选择:要么在重试上花费极少的时间以获得完美的分布，要么接受概率分布中的极小误差以避免重试。