问题 以N为模的随机数的均匀性


选择随机数的一种常用方法 [0,n) 是取结果的 rand() 模 ñrand() % n。但是,即使结果由可用返回 rand() 实施是完全统一的,不应该产生均匀性的问题 [0,n) 数字时 RAND_MAX + 1 不均匀分配 ñ?例如。假设 RAND_MAX 是2,和 ñ 是2.然后有3个可能 rand() 输出:0,1和2,当我们使用模数时,我们分别得到0,1和0 ñ。因此输出将根本不均匀。

这在实践中是一个真正的问题吗?什么是选择随机数的更好方法 [0,n) 统一来源于 rand() 输出,最好没有任何浮点运算?


6184
2017-10-27 21:46


起源

可能重复 在一个范围内生成无偏随机整数的最优算法是什么? - hammar
不完全重复,因为偏见问题被认为是理所当然的,问题是“这在实践中真的是一个问题吗?”我试图量化我的答案中的偏见。 - slashingweapon
看到: eternallyconfuzzled.com/arts/jsw_art_rand.aspx - Alex Reynolds
你找到答案了吗? - Murilo Vasconcelos
@MuriloVasconcelos:是的,我刚刚接受了一个。 - dragonroot


答案:


你是对的, rand() % N 并不是精确均匀分布的。确切地说,重要的是多少取决于你想要的数字范围和你想要的随机程度,但如果你想要足够的随机性,你甚至不关心它,你不想使用它 rand() 无论如何。获得一个真正的随机数生成器。

也就是说,要得到一个真正的随机分布,mod到下一个2的幂并进行采样,直到你得到一个你想要的范围(例如0-9,使用 while(n = rand()%0x10 > 10);)。


7
2017-10-27 22:03



+1的解决方法,但通常是低位 rand() 熵很差。使用高位会更聪明。 - R..
@Kevin:你判断rand()的任何特定实现,即在现代glibc中发现的那个吗? - dragonroot
@ToddLehman在我的系统(OSX 10.10)中,低位肯定不一致。在命令行上运行此命令以获得实时更新计数: pastebin.com/D5r7we3H - Kevin
@ToddLehman:我的意思是我怀疑大多数实现都使用原始LCG输出,而不仅仅是LCG“在核心”。 - R..
@ToddLehman:我认为你的希望是错误的。 rand 是绝望的坏(它最多可以产生 UINT_MAX 由于的可能序列 srand(签名)并试图让它“更好”只鼓励人们使用它。滚动你自己的体面(非加密)PRNG只是几行而且这正是你应该做的 - 超出序列质量,它给你有用的属性,如缺乏全局状态,可恢复性和跨平台相同序列 - 相同-种子。 - R..


这取决于:

  • RAND_MAX的值
  • 你的N值

我们假设你的RAND_MAX是2 ^ 32。如果N相当小(假设为2)那么偏差是1/2 ^ 31 - 或者太小而不能注意到。

但是如果N相当大,比如2 ^ 20,那么偏差是1/2 ^ 12,或者在4096中约为1。更大,但仍然很小。


4
2017-10-27 21:55



相反,我认为答案恰到好处。我们假设PRNG生成具有完美分布的数字。问题是,我们是否关心偏见?我试图提供量化偏见的方法,因此提问者可以自己确定是否可以容忍他。这是非语言非特定的。 - slashingweapon
有些系统有 RAND_MAX 的 0xffff,导致一个 许多 更大的偏见。 - Kevin
更差。 Visual C ++实现具有RAND_MAX == 0x7FFF,在MS-DOS上从16位MSC 3.0遗留下来。 - Mike Housky
@slashingweapon你可以指导我链接/资源以正式计算偏差吗? - themanwhosoldtheworld


您可以采取的一种方法如下:

知道的价值 N,你做 R_MAX = ((RAND_MAX + 1) / N) * N; 为了均匀。

所以你可以做你的自定义 rand() 功能:

int custom_rand(int mod) {
    int x = rand();
    const int R_MAX = ((RAND_MAX + 1) / mod) * mod;    

    while (x > R_MAX) { // discard the result if it is bigger
        x = rand();
    }

    return (x % mod);
}

1
2017-10-27 22:11



如果rand_max是2 ^ 32-1怎么办? - Eamon Nerbonne
什么时候 RAND_MAX == INT_MAX (经常发生)。 RAND_MAX + 1  - >未定义的行为 - (也许 INT_MIN)。 - chux
我想你真的想要 R_MAX = (RAND_MAX / N) * N; 和 while (x >= R_MAX),否则你会产生更多零的偏见,因为 R_MAX % mod == 0。也 do { x = rand(); } while (x >= R_MAX) 在这里会更好,因为那样你就不会写作了 x = rand(); 两次。 - Todd Lehman


使用余数(%不是C中的“模”运算符)对于减小范围内的均匀随机数存在两个问题。首先是对较小数字(如上所述)存在轻微偏差,其次是典型PRNG在低阶位中往往较不随机。我似乎记得Knuth(计算机编程艺术,第二卷,数值算法)以及(从MIX转换为C之后)rand()%2是随机单位的不良来源。最好选择(rand()> RAND_MAX / 2)(或测试一个高位,如果RAND_MAX几乎是2的幂)

剩余部分应该足够好,可以在很短的时间内随意使用。避免用于模拟。实际上,对于大型模拟或“蒙特卡罗”计算,完全避免使用rand()。实现往往具有大约2 ^ 32或更小的周期。在2+ GHz处理器上进行超过40亿次试验并不难。


1
2017-10-27 22:42



典型的LCG(线性同余生成器)确实在较低位中的随机性较低,是的。例如,乘以奇数并加上奇数 总是 当你具有二次幂模数时,将最低有效位反转。但这并不意味着典型的PRNG有这个问题。所有人要做的就是运行LCG两次并进行位移和xor以便很好地混合或者其他技巧。任何提供a的C库 rand() 较低位的随机性较低,严重破坏。 - Todd Lehman
@ToddLehman:从C11规范,在rand()函数描述的脚注中:“295”无法保证产生的随机序列的质量,并且已知某些实现产生具有令人沮丧的非随机低序列的序列有特殊要求的应用应该使用已知足以满足其需求的发电机。“因此,ISO认为这样的rand()函数不会被严重破坏。令人痛苦,是的,但没有打破。 - Mike Housky
好点子!不幸的是,它被设计破坏了。 :( - Todd Lehman