消除模偏差:如何在arc4random_uniform()函数中实现？

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返回a uint8_t而不是a uint32_t,因此输出来自arc4random区间中的数字[0,256).让我们选择upper_bound7.

请注意,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)

在N区间[4,256]中生成一个数字(称之为)之后,最终的计算是

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%的模偏差.

因此,您可以选择:在重试时花费极少的时间来获得完美的分布,或者在概率分布中接受微小的错误以避免重试.