[解決済み] ランダムなブール値を生成する

質問

現在実装しているのは Ellerのアルゴリズム C++で、迷路のランダム性について、小さなディテールが気になっています。

今までは、以下のようなコードで、ランダムな bool :

bool randomBool()
{
    return 0 + (rand() % (1 - 0 + 1)) == 1;
}

// In main.cpp

time_t seconds;
time(&seconds);
srand((unsigned int) seconds);

しかし、デバッグしてみると、しばしば繰り返される true または false が発生し、最大で30回連続することもありました。

このアルゴリズムは本当にランダムなのでしょうか、それともC++でもっと良い方法があるのでしょうか？

どのように解決するのですか？

C++11のSTLには乱数生成の方法が組み込まれており、それは rand() . 0または1のランダムな整数を通して、ランダムなブーリアンをシミュレートすることができます。

#include <iostream>
#include <random>

int main(int argc, char *argv[]) {
    auto gen = std::bind(std::uniform_int_distribution<>(0,1),std::default_random_engine());
    const unsigned int N = 100;
    unsigned int numTrue = 0;
    unsigned int numFalse = 0;
    for (int i = 0; i < 100; ++i) {
        bool b = gen();
        if (b) ++ numTrue;
        else ++numFalse;
    }
    std::cout << numTrue << " TRUE, " << numFalse << " FALSE" << std::endl;
}

このライブラリの詳細については、C++の標準的なリファレンスに記載されています。例えば、quot;true" と "false" の値を半々以外の割合にしたい場合、0 から 1 の間のランダムな浮動小数点数を作成して、ある閾値より小さい値を true、それ以外を false と呼び出すことができます。

長いストリークが見られる理由、それは

このコードでは、なぜ "true" や "false" の値が30個も連続して表示されるのかについては、まだ説明していません。しかし rand() また、1や0を不必要に足したり引いたりすることがあるようですが、そのような問題はないはずです。しかし、ご質問の文章が曖昧であることに今更ながら気づきました。もし、あなたが30回連続でプログラムを実行し、終了しているのであれば、私のコードであっても、繰り返し値が表示されることを期待すべきです。ほとんどの乱数発生器は、実際には擬似乱数発生器です。あなたがプログラムを実行するたびに、それらは 同じ これは、結果の一貫性を保つために重要なことです。しかし、プログラムの実行中（例えば、あなたの randomBool() ループの中で、このような長さのストリークは、非常にあり得ないので、見るべきではありません。

長いストリークの発生しにくさ

真と偽のランダムブーレーンが30回連続することはありえない（真と偽が同じ確率の場合）という私の主張に反対するコメントをいただき、驚きました。確率についてよくある誤解は、「運は物事を均等にしようとする」というもので、コイン投げで何回か連続して表が出たら、宇宙はそれを修正して裏の可能性を高くしようとする、というものです。このような誤解があるため、人々は表と裏の両方が出る可能性を過小評価しており、この回答や本問のコメントの動機は、このよくある誤りを正すことにあったのだと思うのです。

しかし、そこには リアル 特に30回という長丁場は、ますますありえないことです。不公平のないランダムなコイン投げの言葉を使うと、各IID（独立同分布）コイン投げは、前のコインと同じになる確率は50％しかありません。したがって、長い連勝の確率は、連勝の長さに応じて指数関数的に減少する。長さLの連勝の場合、すべての表が連勝する確率は2^L分の1であり、いずれかのタイプの連勝の確率は2^L分の2または2^(L-1)分の1である。以下はデモのためのコードである。

#include <iostream>
#include <random>
#include <map>

bool randomBool() {
    static auto gen = std::bind(std::uniform_int_distribution<>(0,1),std::default_random_engine());
    return gen();
}

int main(int argc, char *argv[]) {

    const unsigned int N = 1e8;
    std::map<unsigned int,unsigned int> histogram;
    bool current = randomBool();
    unsigned int currentLength = 1;
    for (int i = 0; i < N; ++i) {
        bool b = randomBool();
        if (b == current) {
            ++currentLength;
        } else {
            auto it = histogram.find(currentLength);
            if (it != histogram.end())
                it->second += 1;
            else
                histogram.insert(std::make_pair(currentLength,1));
            currentLength = 1;
        }
        current = b;
    }

    for (auto pair : histogram) 
        std::cout << "STREAK LENGTH " << pair.first << " OCCURS " << pair.second << " TIMES" << std::endl;
}

出力されたヒストグラムは

STREAK LENGTH 1 OCCURS 25011106 TIMES
STREAK LENGTH 2 OCCURS 12503578 TIMES
STREAK LENGTH 3 OCCURS 6249056 TIMES
STREAK LENGTH 4 OCCURS 3125508 TIMES
STREAK LENGTH 5 OCCURS 1560812 TIMES
STREAK LENGTH 6 OCCURS 781206 TIMES
STREAK LENGTH 7 OCCURS 390143 TIMES
STREAK LENGTH 8 OCCURS 194748 TIMES
STREAK LENGTH 9 OCCURS 97816 TIMES
STREAK LENGTH 10 OCCURS 48685 TIMES
STREAK LENGTH 11 OCCURS 24327 TIMES
STREAK LENGTH 12 OCCURS 12176 TIMES
STREAK LENGTH 13 OCCURS 6149 TIMES
STREAK LENGTH 14 OCCURS 3028 TIMES
STREAK LENGTH 15 OCCURS 1489 TIMES
STREAK LENGTH 16 OCCURS 811 TIMES
STREAK LENGTH 17 OCCURS 383 TIMES
STREAK LENGTH 18 OCCURS 193 TIMES
STREAK LENGTH 19 OCCURS 104 TIMES
STREAK LENGTH 20 OCCURS 43 TIMES
STREAK LENGTH 21 OCCURS 20 TIMES
STREAK LENGTH 22 OCCURS 14 TIMES
STREAK LENGTH 23 OCCURS 4 TIMES
STREAK LENGTH 24 OCCURS 3 TIMES

長さLの筋が存在しうる区間は数多く重なっているので、反転回数Nで長さLの筋の期待数を計算することは困難である。しかし、このヒストグラムはほぼ指数関数的な分布をしており、各エントリーが直前のエントリーの約半分であることに注意してください。

最大ストリークは24である[注：旧バージョンではバグで23とカウントされていた]。24回投げてこの長さの連番が出る確率は2^(24-1)分の1、つまり約800万分の1である。1e8回のトスで、このような連鎖は約1e8/24〜430万回あるので、このような連鎖は少ないと予想され、ほぼ正しいと思われます（正確な期待値の計算は難しいという私の上記の注意点はありますが）。一方，長さ30の連番は，30回の独立した連番で5億3700万分の1の確率であり，長さ24の連番よりもはるかに低い確率である。