硬币翻转模拟永远不会超过15个头

Question

我正在研究圣彼得堡悖论的模拟,当时我意识到我的硬币翻转代码从未记录过连续超过15个头的任何条纹.我运行模拟100,000,000次,这应该导致平均1526条头长16条.

(0.5 ^ 16)x 100,000,000 = 1526

显然,出了点问题.

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

int main(int argc, char const *argv[])
{
srand(time(0));

int i, lim = 100000000, streak = 0, maxstreak = 0;
for (i = 0; i < lim; ++i)
{
    if (rand()%2) {
        streak++;
        if (streak > maxstreak) maxstreak = streak;
    }
    else streak = 0;
}

printf("Ran %d times, longest streak of %d\n", lim, maxstreak);
return 0;
}

每次都返回以下内容:

Ran 100000000 times, longest streak of 15

谢谢你的帮助!

编辑:在Windows 7 x64上运行GCC 4.6.2版.一般来说,编程是新的.

编辑2:谢谢大家的帮助!任何人都在附近,我想知道目前的实施情况会限制15个头？如何rand()有效地破解这个函数来产生这个问题？

Answer 1

尝试为随机数生成器选择不同的种子值。虽然 rand() 是一个非常好的随机数生成器，但它实际上是一个伪随机数生成器。您可能想阅读 rand 的手册页（man -s3 rand），其中明确指出您应该（对于某些实现）使用高阶位而不是低阶位......

NOTES
   The versions of rand() and srand() in the Linux C Library use the  same
   random number generator as random(3) and srandom(3), so the lower-order
   bits should be as random as the higher-order bits.  However,  on  older
   rand()  implementations,  and  on  current implementations on different
   systems, the lower-order bits are much less  random  than  the  higher-
   order  bits.   Do  not use this function in applications intended to be
   portable when good randomness is needed.  (Use random(3) instead.)

如果不了解有关您运行程序的系统的更多信息，我们无法知道这是否是您的问题。但尝试更改您的代码以使用与 2^0 位不同的位。

运行你的版本对我有用，

/coinflipsim 
Ran 100000000 times
head 50006650, streak 27
tail 49993350, streak 25

这是适合我的代码，使用与 0 位不同的位，

int main(int argc, char const *argv[])
{
    srand(time(0));

    int i, lim = 100000000;
    int head=0, tail=0;
    int hstreak=0, tstreak=0;
    int hstreakmax=0, tstreakmax=0;
    for (i = 0; i < lim; ++i)
    {
        //if (rand()%2)
        if( rand() & (1<<13) ) //pick a bit, try different bits
        {
            head++;
            if( ++hstreak>hstreakmax) hstreakmax=hstreak;
            tstreak=0;
        }
        else {
            tail++;
            if( ++tstreak>tstreakmax) tstreakmax=tstreak;
            hstreak=0;
        }
    }
    printf("Ran %d times\n",lim);
    printf("head %d, streak %d\n",head,hstreakmax);
    printf("tail %d, streak %d\n",tail,tstreakmax);
    return 0;
}

将 rand()%2 行更改为此并重新运行，

        if( rand() & (1<<13) ) //pick a bit, try different bits

不同的结果，

./coinflipsim 
Ran 100000000 times
head 50001852, streak 25
tail 49998148, streak 28