7

サンクトペテルブルクのパラドックスのシミュレーションに取り組んでいたときに、コイン投げのコードが 15 回を超える表が連続して記録されていないことに気付きました。シミュレーションを 100,000,000 回実行した結果、平均 1526回の頭の長さ 16のストリークが発生するはずでした。

(0.5^16) × 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

あなたのコードは問題ありません -rand()明らかにサブパーであるのはあなたの C ライブラリの実装です。おそらく、出力の下位ビット間に相関関係があるか、内部状態が非常に小さい可能性があります (そのため、実際には 1 億回の試行がジェネレーターの出力シーケンス全体を何回もカバーしています)。

最初のケース (相関出力ビット) では、ジェネレーターの出力を後処理して「白くする」ことができますが、2 番目のケースでは、Mersenne Twister などのより良い実装をプラグインする必要があります。

于 2013-11-06T05:22:20.497 に答える
4

乱数ジェネレーターに別のシード値を選択してみてください。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
于 2013-11-06T05:27:18.483 に答える