c – “n *(rand()/ RAND_MAX)”是否产生倾斜的随机数分布？

如果你把数字从0到RAND_MAX,并尝试把它们分成10个堆,你真的只有三种可能性：

> RAND_MAX是10的倍数,桩甚至出来.
> RAND_MAX不是10的倍数,堆不均匀.
>你把它分成不均匀的群体开始,但把所有的“额外”都放在一起,使它变得不平衡.

你很少能控制RAND_MAX,而且它通常是一个素数.这真的只有2和3作为可能性.

第三个选项大致如下：
[编辑]经过一番思考,我修改了这个数字,产生范围为0 …(limit-1)的数字,以适应C和C中大多数事情的工作方式.这也简化了代码(一点点).

int rand_lim(int limit) {
/* return a random number in the range [0..limit)
 */

    int divisor = RAND_MAX/limit;
    int retval;

    do { 
        retval = rand() / divisor;
    } while (retval == limit);

    return retval;
}

对于任何人来说,这种方法是否可能会有一些偏差,我也写了一个相当不同的版本,纯粹用于测试.这个使用非常有限范围的非随机发生器,所以我们可以简单地遍历范围内的每个数字.看起来像这样：

#include <stdlib.h>
#include <stdio.h>

#define MAX 1009

int next_val() {
    // just return consecutive numbers
    static int v=0;

    return v++;
}

int lim(int limit) {
    int divisor = MAX/limit;
    int retval;

    do {
        retval = next_val() / divisor;
    } while (retval == limit);

    return retval;
}

#define LIMIT 10

int main() {

    // we'll allocate extra space at the end of the array:
    int buckets[LIMIT+2] = {0};
    int i;

    for (i=0; i<MAX; i++)
        ++buckets[lim(LIMIT)];

    // and print one beyond what *should* be generated
    for (i=0; i<LIMIT+1; i++)
        printf("%2d: %dn",i,buckets[i]);
}

所以,我们从0到1009(1009是素数)的数字开始,所以它不会是我们选择的任何范围的精确倍数.所以,我们从1009个数字开始,并将其分成10个桶.这应该在每个桶中给100个,剩下的9个剩饭(可以这么说)被do / while循环“吃掉”了.正如它现在写的,它分配和打印出一个额外的桶.当我运行它时,我在桶10中的每个桶0..9和0中都准确地得到了100个.如果我注释掉了do / while循环,我在桶10中看到了每个0..9和9中的100个.

只要确定,我已经重新运行测试与各种其他数字,所产生的范围(主要使用素数)和桶的数量.到目前为止,我无法让它在任何范围内产生倾斜的结果(当然,只要do / while循环启用).

另一个细节：有一个原因我在这个算法中使用除数而不是余数.有一个很好(甚至是体面的)rand()实现它是无关紧要的,但是当你使用除法将数字钳制到一个范围时,你保留输入的高位.当你用余数做的时候,你保留输入的低位.如发生的那样,使用典型的线性同余伪随机数发生器,较低位往往比较高位随机.合理的实施将会抛出一些最不重要的位,这使得这无关紧要.另一方面,有一些相当糟糕的rand的实现,并且大多数它们通过使用除法而不是余数来得到更好的输出质量.

我还应该指出,有大致相反的发生器 – 低位比高位更随机.至少在我的经验中,这些都是不常见的.高位更随机的是相当普遍的.