"n*(rand()/ RAND_MAX)"是否会产生偏斜的随机数分布？

Question

我想找到一种在C中获取随机数的无法解释的方法(尽管最多我会将其用于0-20的值,更可能只有0-8).我已经看过这个公式,但经过一些测试后,我不确定它是否有偏差.有帮助吗？

这是使用的完整功能:

int randNum() 
{ 
    return 1 + (int) (10.0 * (rand() / (RAND_MAX + 1.0)));
}

我使用以下方法播种:

unsigned int iseed = (unsigned int)time(NULL);
srand (iseed);

下面建议的那个拒绝为我工作我试过了

int greek; 
for (j=0; j<50000; j++) 
{ 
greek =rand_lim(5); 
printf("%d, " greek); 
greek =(int) (NUM * (rand() / (RAND_MAX + 1.0))); 
int togo=number[greek]; 
number[greek]=togo+1; 
}

当我注释掉printf时,它停止工作并给我相同的数字50000次.

Answer 1

是的,它是倾斜的,除非您的RAND_MAX恰好是10的倍数.

如果您将数字从0到RAND_MAX,并尝试将它们分成10堆,那么您实际上只有三种可能性:

1. RAND_MAX是10的倍数,并且堆积均匀.
2. RAND_MAX不是10的倍数,并且堆积不均匀.
3. 你把它分成不均匀的组开始,但扔掉所有会使它变得不均匀的"额外".

你几乎无法控制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: %d\n", i, buckets[i]);
}

所以,我们从0到1009的数字开始(1009是素数,因此它不会是我们选择的任何范围的精确倍数).所以,我们从1009个数字开始,然后将它分成10个桶.这应该在每个桶中给出100个,并且9个剩余物(可以这么说)被do/ whileloop "吃掉" .正如它现在所写,它分配并打印出一个额外的桶.当我运行它时,我在桶0中的每个桶中得到100个,在桶10中得到0.如果我注释掉do/ whileloop,我在0..9中看到100,在桶10中看到9.

可以肯定的是,我已经使用各种其他数字重新运行测试,包括产生的范围(主要是使用的素数)和桶的数量.到目前为止,我还没有能够让它为任何范围产生偏差结果(当然,只要启用了do/ whileloop).

另一个细节:我有一个原因,我在这个算法中使用除法而不是余数.凭借良好的(甚至像样的)实现的rand()是无关紧要的,但是当你用除法夹号码的范围,你保持上输入的比特.当您使用余数时,保留输入的低位.实际上,对于典型的线性同余伪随机数发生器,较低位往往比高位更不随机.一个合理的实现将抛出一些最不重要的位,使这无关紧要.另一方面,有一些非常糟糕的实现rand,并且大多数情况下,通过使用除法而不是余数,最终得到更好的输出质量.

我还要指出的是,有有发电机是做大致相反-低位比高位更随意.至少根据我的经验,这些都是非常罕见的.这与该高位比特是更加随机的是显着地更常见.