硬币翻转模拟，不超过15个正面连续出现的次数

Question

当我在模拟圣彼得堡悖论时，发现我的抛硬币代码从未记录超过15个连续正面的情况。我进行了一百万次模拟，结果应该是平均有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()函数怎么会出现这个问题呢？

- tpixel

---

我在不同的机器上运行了你的程序，通常得到的结果是25、26、27等。 - Yu Hao

生成并接收了24、26、24。怀疑你的rand()存在偏差。 - chux - Reinstate Monica

你跑了4次，得到的分别是25、26、23和28。你使用的是哪个平台和编译器？ - WiSaGaN

有趣的是，根据定义，RAND_MAX至少必须为32767。15个一位比特，嗯。不知道如果使用if ((rand()%2) == 0)会得到什么结果？ - chux - Reinstate Monica

@chux：生成器可能只有约15位的内部状态，因此在超过1亿次尝试中，您只会看到相同的输出序列重复多次。 - caf

Answer 1

您的代码没问题 - 问题在于您所使用的C库的rand()函数实现显然不够好。可能输出的低位比特之间存在相关性，或者内部状态非常小（因此您的100,000,000次试验实际上多次覆盖了生成器的整个输出序列）。

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

- caf

Answer 2

尝试为您的随机数生成器选择不同的种子值。虽然rand()是一个相当好的随机数生成器，但实际上它是伪随机数生成器。您可能需要阅读rand的man页面(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

- ChuckCottrill

---

谢谢！我对使用位移操作还不是很清楚，但我会尝试一下看看它是如何工作的，谢谢。我非常愿意去了解这部分是如何工作的，但当然，如果在这里有任何详细说明，那就更好了。rand() & (1<<13) - tpixel

表达式 (1<<13) 设置第 13 位（从 0 开始计数，即第 14 位）。按位与 '&' 仅从您的 int 中选择该位。尝试几个不同的位，看看您的系统是否会产生不同的结果。 - ChuckCottrill

Answer 3

令 X(i) 表示第 i 次抛硬币正面朝上的事件。令 E(i) = union { X(j) | i <= j < i + 16 } 表示从第 i 次开始连续出现 16 次正面朝上的事件。

你的分析假设事件 E(i) 是独立的。这是不正确的。如果事件 E(i) 不发生，那么直接前面的事件 E(i-1), E(i-2) 等的发生概率会大大降低。

只有当 |i - j| >= 16 时，才能说事件 E(i) 和 E(j) 是独立的。

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

- Timothy Shields

---

分析是错误的，但正确答案仍然远离0连胜。 - n. m.

@n.m. 是的，这就是我说“当其他人运行此代码时，他们会得到大约26个连续值”的原因。这意味着连续值的期望值大约为26。 - Timothy Shields

谢谢，这非常有见地。如果您有任何相关资源，我会更深入地研究数学。 - tpixel

程序的输出不是长度为16的连续序列的数量，而是记录的最长连续序列的长度。 - caf

不，26是最长的连胜。16连胜的数量大约是150左右（非常粗略估计）。 - n. m.