7

当我意识到我的掷硬币代码从未连续记录超过 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()被如此有趣地破坏以产生这个问题？

4

3 回答 3

4

您的代码很好 - 这是您的 C 库的rand()实现显然低于标准。可能输出的低位之间存在相关性，或者内部状态可能非常小（因此您的 100,000,000 次试验实际上多次覆盖了生成器的整个输出序列）。

在第一种情况下（相关输出位），您可以对生成器的输出进行后处理以“白化”它，但在第二种情况下，您需要插入更好的实现，例如 Mersenne Twister。

于 2013-11-06T05:22:20.497 回答
4

尝试为您的随机数生成器选择不同的种子值。尽管 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
于 2013-11-06T05:27:18.483 回答
2

设 X(i) 是第 i 次翻转有正面的事件。让 E(i) = union { X(j) | i <= j < i + 16 } 是从 i 开始连续 16 次正面朝上的事件。

您的分析假设事件 E(i) 是独立的。这是不正确的。如果 E(i) 没有发生，这会大大降低前面的 E(i-1)、E(i-2) 等发生的概率。

正确地说 E(i) 和 E(j) 是独立的，当且仅当 |i - j| >= 16。

可能是您的随机数生成器不是很好。由于rand()最终会产生确定性模式，因此随机生成器可能会产生一个永远不会连续给出 16 个偶数（或奇数）数的模式。

于 2013-11-06T05:07:54.020 回答